二叉树的非递归实现

对二叉树进行先序、中序、后序遍历都是从根结点开始，且在遍历的过程中，经过的节点路线都是一样的，只不过访问的顺序不同。
先序遍历是深入时遇到结点就访问，中序遍历是深入时从左子树返回时遇到结点就访问，而后序遍历是从右子树反回时遇到根结点就访问，在这一过程中，反回结点的顺序与深入结点的顺序相反，即先深入再反回，这不禁让人联想到栈，而想要实现二叉树的非递归遍历，就需要用栈的思想来实现

先序遍历（DLR）

先序遍历的递归过程为

（1）访问根结点
（2）先序遍历根结点的左子树
（3）先序遍历根结点的右子树

而先序遍历的非递归过程为

先将根结点进栈，当栈不为空时，出栈并访问，然后依次将右左结点进栈（栈先进后出，所以先进栈右结点）

如图：

void PreOrder(Btnode *b)
{
    Btnode *p;    
    SqStack st;
    InitStack(st);
    if (b != NULL)      
    {
        Push(st, b);    //根结点入栈
        while (!StackEmpty(st))
        {
            Pop(st, p);                   //根结点出栈
            printf("%c",p->data);              //在此处用输出根接地那的值表示出栈
            if (p->right != NULL)         //当右子树非空
                Push(st, p->right);   //右孩子入栈
            if (p->left != NULL)          //当左子树非空
                Push(st, p->left);    //左孩子入栈
        }
        printf("\n");
    }
    DestroyStack(st);
}

aha,先补充到这里，剩下的明天再继续吧！

二叉树的非递归实现

原文：https://www.cnblogs.com/kangna/p/11846156.html