先序遍历

代码

void PreOrder(BTNode *b)
{
    if(b)
    {
        //准备一个简单的栈
        BTNode* stack[MaxSize];
        int top = 0;
        BTNode* p = b;
        while(p != NULL || top)
        {
            while(p != NULL)
            {
                //打印本节点
                printf("%c ", p->data);    
                //栈这样设计是为了让top==0时表示栈空同时拿来当bool判断为否
                //存入栈里                
                stack[++top] = p;
                //访问左孩子
                p = p -> lchild;
            }
            //如果左节点不存在            
            if(top)
            {
                //找到这个左节点的兄弟右节点
                p = stack[top--];
                p = p -> rchild;
            }
        }
    }
}

思路

1）访问p节点，并将p节点入栈;
2）如果左节点存在，则让p指向左节点，循环1步骤
3）左节点不在了，则出栈一次，让栈顶元素等于目前节点的亲节点，借此让p指针指向这个左节点的兄弟。
4）如果右节点存在，就继续1，2，3步骤
5）如果右节点不存在，则再次出栈，栈顶元素等于该节点的亲节点的亲节点。
6）直到p指向空且栈空才结束。

中序遍历

代码

void InOrder(BTNode *b)
{
    if(b)
    {
        //准备一个简单的栈
        BTNode* stack[MaxSize];
        int top = 0;
        BTNode* p = b;
        while(p != NULL || top)
        {
            while(p != NULL)
            {
                //先序是在这里打印的!!!!
                //存入栈里                
                stack[++top] = p;
                //访问左孩子
                p = p -> lchild;
            }
            if(top)
            {
                printf("%c ", p->data);                    
                p = stack[top--];
                p = p -> rchild;
            }
        }
    }
}

思路

1）将p节点入栈;
2）如果左节点存在，则让p指向左节点，循环1步骤
3）左节点不在了，则打印该节点并出栈一次，让栈顶元素等于目前节点的亲节点，借此让p指针指向这个左节点的兄弟。
4）如果右节点存在，就继续1，2，3步骤
5）如果右节点不存在，则再次出栈，栈顶元素等于该节点的亲节点的亲节点。
6）直到p指向空且栈空才结束。

与先序唯一的不同就是打印的位置

后序遍历

代码

void PostOrder(BTNode *b)
{
    BTNode* stack[MaxSize];
    int top = 0;
    BTNode *p;    
    BTNode *pre = NULL;    
     stack[++top] = b;
    while (top)
    {
        p = stack[top];
        if((p->lchild==NULL&&p->rchild==NULL)||(pre!=NULL&&(pre==p->lchild||pre==p->rchild)))
        {
            printf("%c ", p->data);
            top--;
            pre = p;
        }
        else
        {
            if (p->rchild!=NULL)
            {
                stack[++top] = p->rchild;
            }
            if (p->lchild!=NULL)
            {
                stack[++top] = p->lchild;
            }
        }
    }
}