国产一区二区精品-国产一区二区精品久-国产一区二区精品久久-国产一区二区精品久久91-免费毛片播放-免费毛片基地

千鋒教育-做有情懷、有良心、有品質的職業教育機構

手機站
千鋒教育

千鋒學習站 | 隨時隨地免費學

千鋒教育

掃一掃進入千鋒手機站

領取全套視頻
千鋒教育

關注千鋒學習站小程序
隨時隨地免費學習課程

當前位置:首頁  >  技術干貨  > 二叉樹非遞歸遍歷棧中存的是什么?

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

來源:千鋒教育
發布人:xqq
時間: 2023-10-11 08:55:32 1696985732

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

二叉樹非遞歸遍歷棧中存的是看一眼代碼就能知道, 傳參傳的是 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??梢詫M二叉樹按層序編號:約定編號從根結點(根結點編號為1 11)起,自上而下,自左向右。這樣,每個結點對應一個編號,對于編號為i的結點,若有雙親,則其雙親為i / 2 i/2i/2,若有左孩子,則左孩子為2 i 2i2i;若有右孩子,則右孩子為2 i + 1 2i+12i+1。

聲明:本站稿件版權均屬千鋒教育所有,未經許可不得擅自轉載。
10年以上業內強師集結,手把手帶你蛻變精英
請您保持通訊暢通,專屬學習老師24小時內將與您1V1溝通
免費領取
今日已有369人領取成功
劉同學 138****2860 剛剛成功領取
王同學 131****2015 剛剛成功領取
張同學 133****4652 剛剛成功領取
李同學 135****8607 剛剛成功領取
楊同學 132****5667 剛剛成功領取
岳同學 134****6652 剛剛成功領取
梁同學 157****2950 剛剛成功領取
劉同學 189****1015 剛剛成功領取
張同學 155****4678 剛剛成功領取
鄒同學 139****2907 剛剛成功領取
董同學 138****2867 剛剛成功領取
周同學 136****3602 剛剛成功領取
相關推薦HOT