二叉树非递归遍历栈中存的是什么?
推荐
在线提问>>
一、二叉树非递归遍历栈中存的是什么
二叉树非递归遍历栈中存的是看一眼代码就能知道, 传参传的是 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。
