【文章內(nèi)容簡(jiǎn)介】 else{ if(!(BT=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW)； BTdata=ch。 ／／ 生成根結(jié)點(diǎn) CreateBiTree(BTlchild)。 ／／ 構(gòu)造左子樹 CreateBiTree(BTrchild)。 ／／ 構(gòu)造右于樹 } return OK； }／／ CreateBiTree A B C D A BT B C D ^ ^ ^ ^ ^ 遍歷二叉樹的 非遞歸算法： 我們先觀察一下三種遍歷行走的路線 A B C E F H G D I * * * * * * * * * 前序遍歷 NLR A B C E F H G D I 中序遍歷 LNR amp。 amp。 amp。 amp。 amp。 amp。 amp。 amp。 amp。 A B C E F H G D I 后序遍歷 LRN amp。 amp。 amp。 amp。 amp。 amp。 amp。 amp。 amp。 A B C E F H G D I * * * * * * * * * 三種遍歷的訪問(wèn)位置對(duì)比： 三種遍歷的路線完全一樣，只是訪問(wèn)時(shí)間不同； 前序：第一次經(jīng)過(guò) * 時(shí)訪問(wèn) 中序：第二次經(jīng)過(guò) 時(shí)訪問(wèn) 后序：第三次經(jīng)過(guò) amp。 時(shí)訪問(wèn) 遍歷線路的核心規(guī)則是：先左后右； 我們用一個(gè)棧 stack記錄走過(guò)的位置，以便返回； stack 中數(shù)據(jù)元素的類型： *BiTNode(或 BiTree) 函數(shù)： BiTree P。 push(S,p)。 pop(S,p)。 Boolean StackEmpty(S)。 下面給出基于邏輯 結(jié)構(gòu)的算法描述 非遞歸中序遍歷二叉樹的算法思想 建立棧 stack； 1. P指向根； 2. 當(dāng) p不空 且 stack 不空時(shí)反復(fù)做： 若 p不空 ,p 入 棧 。 p指向左子女； 否則 ： ? 出棧頂元素到 p中； ? 訪問(wèn) p； ? p指向右子女； 4. 結(jié)束 如何進(jìn)行前序遍歷？ Void lnorderTraverse(BiTree BT) { ／／ 采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，中序遍歷二叉樹 T的非遞歸算法 . InitStack(S)； p=BT； while(p||!StackEmpty(S)) { if(p) { push(S， p)； p=plchild； }//根指針進(jìn)棧，遍歷左子樹 else { ／／ 根指針退棧，訪問(wèn)根結(jié)點(diǎn)，遍歷右子樹 pop(S， p)； visit(p))。 p=prchild； }//else }／／ InOrderTraverse 非遞歸中序遍歷 BT的算法 : A B C D E F G p i amp。A (1) 例 A B C D E F G p i amp。A amp。B (2) 例 A B C D E F G p i amp。A amp。B amp。C (3) 例 p=NULL A B C D E F G i amp。A amp。B 訪問(wèn)： C (4) 例 p A B C D E F G i amp。A 訪問(wèn)： C B (5) 例 A B C D E F G i amp。A amp。D 訪問(wèn)： C B p (6) 例 A B C D E F G i amp。A amp。D amp。E 訪問(wèn)： C B p (7) 例 A B C D E F G i amp。A amp。D 訪問(wèn)： C B E p (8) 例 A B C D E F G i amp。A amp。D amp。G 訪問(wèn)： C B E P=NULL (9) 例 A B C D E F G i amp。A amp。D 訪問(wèn)： C B E G p (10) 例 A B C D E F G i amp。A 訪問(wèn)： C B E G D p (11) 例 A B C D E F G i amp。A amp。F 訪問(wèn)： C B E G D p (12) 例 A B C D E F G i amp。A 訪問(wèn)： C B E G D F p=NULL (13) 例 A B C D E F G i 訪問(wèn)： C B E G D F A p (14) 例 A B C D E F G i 訪問(wèn)： C B E G D F A p=NULL (15) 例 非遞歸后序遍歷二叉樹的算法思想 建立棧 stack； 1. P指向根； 2. 當(dāng) p不空 且 stack 不空時(shí)反復(fù)做： 若 p不空 ： (p,L) 入 棧 。 p指向左子女； 否則 ： ? 出棧頂元到 p和 tag中； ? 若 tag==R ,則訪問(wèn) p； p置空； ? 否則 （ p,R） 入棧； 并讓 p指向右子女； 4. 結(jié)束 后序遍歷時(shí)，訪問(wèn)一個(gè)結(jié)點(diǎn)的時(shí)間是： ?第 3次經(jīng)過(guò)時(shí)或 ?第 2次反回時(shí)或 ?從右邊返回時(shí)； 如何區(qū)分從 左 還是 右返回的呢？ P入棧時(shí)帶一標(biāo)記 : 向左走時(shí)帶 L 向左走時(shí)帶 R 非遞歸后序遍歷 BT的算法 非遞歸的后序遍歷 BT算法 :（ 基于二叉鏈表存儲(chǔ)結(jié)構(gòu)） void PostOrderTraverse (BiTree BT) { InitStack(S)； //建立棧 p=BT。 //指向根 while (p || !StackEmpty(S)) { if (p) { push((p, L))； // p帶 L入 棧 p=plchild。 } // p指向左子女 else { pop(p,e)。 //出棧頂元到 e中 p=。 tag=。 if (tag==‘R’) { visite(pdata)。 p=NULL。} //訪問(wèn) p else { push((p, R))。 p=prchild。 } // p指向右子女 } // else } // end of while } // end of postOrderTraverse (bt) 例 B E A C Start (A,L) 入棧 (A,L) (B,L) 入棧 (A,L)() ()退棧， (A,L) (B,R)入棧 (A,L) (B,R) (E,L)入棧 (A,L) (B,R) (E,L) (E,L)退棧 (A,L) (B,R) (E,R)入棧 (A,L) (B,R) (E,P) (E,R)退棧 (A,L) (B,R) 訪問(wèn) E (B,R)退棧 (A,L) 訪問(wèn) B (A,L)退棧 (A,R)入棧 (A,R) (C,L)入棧 (A,R) (C,L) (C,L)退棧 (A,R) (C,R)入棧 (A,R) (C,R) (C,R)退棧 (A,R) 訪問(wèn) C (A,R)退棧 訪問(wèn) A 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 課堂練習(xí) 前序遍歷序列： EDACBGFE 中序遍歷序列： ADCBEFHG 試畫出滿足以上序列的二叉樹 課堂練習(xí) 中序遍歷序列： ADCBHFEG 后序遍歷序列： ABCDEFGH 試畫出滿足以上序列的二叉樹 二、線索二叉樹 (Threaded Binary Tree) 目的 ：利用二叉樹的空指針保存遍歷序列的前驅(qū)和后繼。 n個(gè)結(jié)點(diǎn)的二叉樹 ,有 2n個(gè)指針 ,只用了 n1個(gè) ,有 n+1個(gè)是空指。 ? 用空的 左指針 指向某一遍歷序列的 前驅(qū) . ? 用空的 右指針 指向某一遍歷序列的 后繼 . 這 兩種指針 稱為 線索 (Thread)。 為了區(qū)分線索與真實(shí)指針，給結(jié)點(diǎn)增加兩個(gè)域 Ltag和 Rtag lchild Ltag data Rtag rchild Ltag=0: lchild 指向結(jié)點(diǎn)的左子女； Ltag=1: lchild 指向 某一遍歷序列 前驅(qū)； Rtag=0: rchild 指向結(jié)點(diǎn)的右子女； Rtag=1: rchild 指向 某一遍歷序列 后繼 ； 二、線索二叉樹 (Threaded Binary Tree) Typedef enum{Link,Thread} PointerTag。 Typedef struct BiThrNode { ElemType data。 struct BiThrNode *lchild, *rchild。 PointerTag Ltag, Rtag。 } BiThrNode, *BiThrTree。 lchild Ltag data Rtag rchild 二、線索二叉樹 (Threaded Binary Tree) 加了線索的二叉樹是 線索二叉樹 ； 給二叉樹加線索的過(guò)程是 線索化（穿線） ； 按前序遍歷序列穿線的二叉樹是 前序線索二叉樹 ； 按中序遍歷序列穿線的二叉樹是 中序線索二叉樹 ； 按后序遍歷序列穿線的二叉樹是 后序線索二叉樹 ； 中序線索 二叉樹簡(jiǎn)稱 線索二叉樹 ； 二、線索二叉樹 (Threaded Binary Tree) A B C D E A B D C E T 先序序列： ABCDE 先序線索二叉樹 0 0 0 0 1 1 1 1 ^ 1 1 二、 線索二叉樹 (Threaded Binary Tree) A B C D E A B D C E T 中序序列： BCAED 中序線索二叉樹 0 0 0 0 1 1 1 1 ^ 1 1 ^ 二、 線索二叉樹 (Threaded Binary Tree) A B C D E A B D C E T 后序序列： CBEDA 后序線索二叉樹 0 0 0 0 1 1 1 1 1 1 ^ 二、 線索二叉樹 (Threaded Binary Tree) D B F E A C NULL NULL 中序線索二叉樹 二、線索二叉樹 (Threaded Binary Tree) Void lnorderTraverse(BiTree BT) { ／／ 采