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

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

部分代碼：

//二叉樹的存儲(chǔ)結(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;

??????? }

??? }

}

延伸閱讀：

二、幾個(gè)特殊的二叉樹

（1）斜樹

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

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