二叉树非递归遍历栈中存的是什么?

一、二叉树非递归遍历栈中存的是什么

二叉树非递归遍历栈中存的是看一眼代码就能知道, 传参传的是 node 地址, 压栈的自然也是node地址。栈的本质意义在于保存上下文环境，对于二叉树而言，递归的时候传入的值是节点。点本身才是需要储存的上下文环境，因此在非递归的时候应当把节点压入栈。以此类推，以后编写非递归代码时，递归的时候入参是什么，非递归的时候就把同样的对象压入栈即可。

部分代码：

//二叉树的存储结构

typedef struct BiTNode {

    ElemType data;

    struct BiTNode *lchild, *rchild;

} BiTNode, *BiTree;

//非递归中序遍历二叉树

void InOrder(BiTree) {

    InitStack(S);

    BiTree p = T;

    while (p || IsEmpty(S)) {

        if (p) {     //一路向左

            Push(S, p);

            p = p->lchild;

        } else {

            Pop(S, p);

            visit(p);

            p = p->rchild;

        }

    }

}

延伸阅读：

二、几个特殊的二叉树

（1）斜树

所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

（2）满二叉树棵高度为h，且含有2 h − 1 2^h-12h−1个结点的二叉树称为满二叉树，即树中的每层都含有非常多的结点。满二叉树的叶子结点都集中在二叉树的最下一层，并且除叶子结点之外的每个结点度数均为2 22。可以对满二叉树按层序编号:约定编号从根结点(根结点编号为1 11)起，自上而下，自左向右。这样，每个结点对应一个编号,对于编号为i的结点，若有双亲，则其双亲为i / 2 i/2i/2,若有左孩子，则左孩子为2 i 2i2i;若有右孩子，则右孩子为2 i + 1 2i+12i+1。