300元3小时服务不限次数-400块钱3小时无限次快餐,500一晚同城约茶,风楼阁交友平台

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

二叉树非递归遍历栈中存的是看一眼代码就能知道, 传参传的是 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。

上一篇

单链表和双链表的区别是什么?

下一篇

aspice2级与3级差异具体在哪里?