二叉樹非遞歸遍歷棧中存的是什么?

一、二叉樹非遞歸遍歷棧中存的是什么

二叉樹非遞歸遍歷棧中存的是看一眼代碼就能知道, 傳參傳的是 node 地址, 壓棧的自然也是node地址。棧的本質(zhì)意義在于保存上下文環(huán)境，對于二叉樹而言，遞歸的時候傳入的值是節(jié)點。點本身才是需要儲存的上下文環(huán)境，因此在非遞歸的時候應當把節(jié)點壓入棧。以此類推，以后編寫非遞歸代碼時，遞歸的時候入?yún)⑹鞘裁?，非遞歸的時候就把同樣的對象壓入棧即可。

部分代碼：

//二叉樹的存儲結(jié)構(gòu)

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）斜樹

所有的結(jié)點都只有左子樹的二叉樹叫左斜樹。所有結(jié)點都是只有右子樹的二叉樹叫右斜樹。這兩者統(tǒng)稱為斜樹。

（2）滿二叉樹棵高度為h，且含有2 h ? 1 2^h-12h?1個結(jié)點的二叉樹稱為滿二叉樹，即樹中的每層都含有非常多的結(jié)點。滿二叉樹的葉子結(jié)點都集中在二叉樹的最下一層，并且除葉子結(jié)點之外的每個結(jié)點度數(shù)均為2 22?？梢詫M二叉樹按層序編號:約定編號從根結(jié)點(根結(jié)點編號為1 11)起，自上而下，自左向右。這樣，每個結(jié)點對應一個編號,對于編號為i的結(jié)點，若有雙親，則其雙親為i / 2 i/2i/2,若有左孩子，則左孩子為2 i 2i2i;若有右孩子，則右孩子為2 i + 1 2i+12i+1。