【文章內(nèi)容簡(jiǎn)介】 右子樹(shù) ， 直到葉子處； } return(0)。 } 41 思路： 利用 前序 遍歷來(lái)建樹(shù) （ 結(jié)點(diǎn)值陸續(xù)從鍵盤(pán)輸入 ， 用 DLR為宜 ） status createBTree(Bintree amp。T){ scanf(“%c”,amp。ch)。 if(ch==’’)T=NULL。 else{ if(!(T=( BiTNode *)malloc(sizeof(BinTNode))))exit(overflow)。 Tdata=ch。 createBTpre(Tlchild)。 createBTpre(Trchild)。 } return OK。 } 建樹(shù) ——見(jiàn)教材 P131程序 42 習(xí)題討論： 1. 求二叉樹(shù)深度，或從 x結(jié)點(diǎn)開(kāi)始的子樹(shù)深度。 算法思路： 只查各結(jié)點(diǎn)后繼鏈表指針，若左 (右 )孩子的左 (右 )指針?lè)强?，則層次數(shù)加 1；否則函數(shù)返回。 2. 按層次輸出二叉樹(shù)中所有結(jié)點(diǎn)。 算法思路： 既然要求從上到下，從左到右，則 利用隊(duì)列 存放各子樹(shù)結(jié)點(diǎn)的指針是個(gè)好辦法，而不必拘泥于遞歸算法。 技巧： 當(dāng)根結(jié)點(diǎn)入隊(duì)后 ， 令其左 、 右孩子結(jié)點(diǎn)入隊(duì) ， 而左孩子出隊(duì)時(shí)又令它的左右孩子結(jié)點(diǎn)入隊(duì) ， …… 由此便可產(chǎn)生按層次輸出的效果 。 A B C D E 43 3 中序遍歷的非遞歸 (迭代 )算法 算法思路： 若不用遞歸，則要實(shí)現(xiàn)二叉樹(shù)遍歷的 “ 嵌套 ” 規(guī)則，必用堆棧。可直接用 while語(yǔ)句和 push/pop操作。 參見(jiàn)教材 P130131程序。 （即順序二叉樹(shù)）。 算法思路： 完全二叉樹(shù)的特點(diǎn)是：沒(méi)有左子樹(shù)空而右子樹(shù)單獨(dú)存在的情況 (前 k1層都是滿(mǎn)的，且第 k層左邊也滿(mǎn)） 。 技巧 :按層序遍歷方式 ， 先把所有結(jié)點(diǎn) （ 不管當(dāng)前結(jié)點(diǎn)是否有左右孩子 ） 都入隊(duì)列 .若為完全二叉樹(shù) ,則層序遍歷時(shí)得到的肯定是一個(gè)連續(xù)的不包含空指針的序列 .如果序列中出現(xiàn)了空指針 ， 則說(shuō)明不是完全二叉樹(shù) 。 44 特別討論： 若已知先序 /后序遍歷結(jié)果和中序遍歷結(jié)果，能否“恢復(fù)”出二叉樹(shù)？ 【 嚴(yán)題集 ④】 證明：由一棵二叉樹(shù)的先序序列和中序序列可唯一確定這棵二叉樹(shù)。 例： 已知一棵二叉樹(shù)的 中序序列 和 后序序列 分別是 BDCEAFHG 和 DECBHGFA，請(qǐng)畫(huà)出這棵二叉樹(shù)。 分析： ① 由后序遍歷特征 ， 根結(jié)點(diǎn)必在后序序列尾部 （ 即 A） ； ② 由中序遍歷特征 ， 根結(jié)點(diǎn)必在其中間 ， 而且其左部必全部是左子樹(shù)子孫 （ 即 BDCE） ， 其右部必全部是右子樹(shù)子孫 （ 即 FHG） ； ③ 繼而 ， 根據(jù)后序中的 DECB子樹(shù)可確定 B為 A的左孩子 ， 根據(jù) HGF子串可確定 F為 A的右孩子；以此類(lèi)推 。 45 中序遍歷： B D C E A F H G 后序遍歷： D E C B H G F A （ B D C E） （ F H G） A B F （ D C E） （ H G） C D E G H A B B FF 46 問(wèn)： 用二叉鏈表法（ l_child, r_child）存儲(chǔ)包含 n個(gè)結(jié)點(diǎn)的二叉樹(shù)，結(jié)點(diǎn)的指針區(qū)域中會(huì)有多少個(gè)空指針？ 分析： 用二叉鏈表存儲(chǔ)包含 n個(gè)結(jié)點(diǎn)的二叉樹(shù) ， 結(jié)點(diǎn)必有 2n個(gè)鏈域 （ 見(jiàn)二叉鏈表數(shù)據(jù)類(lèi)型說(shuō)明 ） 。 除根結(jié)點(diǎn)外 ， 二叉樹(shù)中每一個(gè)結(jié)點(diǎn) 有且僅有一個(gè)雙親（ 直接前驅(qū) ） ， 所以只會(huì)有 n－ 1個(gè)結(jié)點(diǎn)的鏈域存放指針 ， 指向非空子女結(jié)點(diǎn) （ 即直接后繼 ） 。 思考： 二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放有用的信息或線(xiàn)索？ ——我們可以用它來(lái)存放當(dāng)前結(jié)點(diǎn)的直接前驅(qū)和后繼等線(xiàn)索，以加快查找速度。 所以， 空指針數(shù)目＝ 2n－ (n1)=n+1個(gè) 。 n+1 47 遍歷二叉樹(shù)和線(xiàn)索二叉樹(shù) 一、 遍歷二叉樹(shù)（ Traversing Binary Tree） 二、線(xiàn)索二叉樹(shù)（ Threaded Binary Tree） 48 二、 線(xiàn)索二叉樹(shù) （ Threaded Binary Tree） 普通二叉樹(shù)只能找到結(jié)點(diǎn)的左右孩子信息， 而該結(jié)點(diǎn)的直接前驅(qū)和直接后繼只能在遍歷過(guò)程中獲得。 若將 遍歷后對(duì)應(yīng)的有關(guān)前驅(qū)和后繼預(yù)存 起來(lái)，則從 第一個(gè)結(jié)點(diǎn) 開(kāi)始就能很快“順藤摸瓜”而遍歷整個(gè)樹(shù)了。 兩種解決方法 增加兩個(gè)域： fwd和 bwd； 利用空鏈域（ n+1個(gè)空鏈域） 存放前驅(qū)指針 存放后繼指針 如何預(yù)存這類(lèi)信息？ 例如中序遍歷結(jié)果： B D C E A F H G，實(shí)際上 已將二叉樹(shù)轉(zhuǎn)為線(xiàn)性排列，顯然具有唯一前驅(qū)和唯一后繼！ 可能是根、或最左（右）葉子 49 規(guī) 定： 1）若結(jié)點(diǎn)有左子樹(shù)，則 lchild指向其左孩子； 否則， lchild指向其直接前驅(qū) (即線(xiàn)索 )； 2）若結(jié)點(diǎn)有右子樹(shù)，則 rchild指向其右孩子； 否則， rchild指向其直接后繼 (即線(xiàn)索 ) 。 為了避免混淆，增加兩個(gè)標(biāo)志域 ，如下圖所示： lchild LTag data RTag rchild 約定 : 當(dāng) Tag域?yàn)?0時(shí) ,表示 正常 情況 。 當(dāng) Tag域?yàn)?1時(shí) ,表示 線(xiàn)索 情況 . 50 有關(guān)線(xiàn)索二叉樹(shù)的幾個(gè)術(shù)語(yǔ)： 線(xiàn)索鏈表： 用上一頁(yè)結(jié)點(diǎn)結(jié)構(gòu)所構(gòu)成的二叉鏈表 線(xiàn) 索： 指向結(jié)點(diǎn)前驅(qū)和后繼的指針 線(xiàn)索二叉樹(shù)： 加上線(xiàn)索的二叉樹(shù) （圖形式樣） 線(xiàn) 索 化： 對(duì)二叉樹(shù)以 某種次序遍歷 使其變?yōu)榫€(xiàn)索二叉樹(shù)的過(guò)程 注： 在線(xiàn)索化二叉樹(shù)中，并不是每個(gè)結(jié)點(diǎn)都能直接找到其后繼的， 當(dāng)標(biāo)志為 0時(shí)，則需要通過(guò)一定運(yùn)算才能找到它的后繼 。 51 data A G E I D J H C F B ltag 0 0 1 1 1 1 0 1 0 1 rtag 0 0 0 1 0 1 0 1 1 1 A G E I D J H C F B 例 1： 帶了 兩個(gè)標(biāo)志 的某 先序遍歷 結(jié)果如表所示，請(qǐng)畫(huà)出對(duì)應(yīng)二叉樹(shù)。 52 A B C G E I D H F root 懸空？ 懸空？ 解： 該二叉樹(shù)中序遍歷結(jié)果為 : H, D, I, B, E, A, F, C, G 所以添加線(xiàn)索應(yīng)當(dāng)按如下路徑進(jìn)行： 例 2： 畫(huà)出以下二叉樹(shù)對(duì)應(yīng)的 中序 線(xiàn)索二叉樹(shù)。 為避免懸空態(tài)，應(yīng)增設(shè)一個(gè)頭結(jié)點(diǎn) 53 對(duì)應(yīng)的中序線(xiàn)索二叉樹(shù)存儲(chǔ)結(jié)構(gòu)如圖所示： 0 0 A 0 0 C 0 0 B 1 1 E 1 1 F 1 1 G 0 0 D 1 1 I 1 1 H 注：此圖中序遍歷結(jié)果為 : H, D, I, B, E, A, F, C, G 0 root 0 54 4.【 2022年計(jì)算機(jī)系考研題 】 給定如圖所示二叉樹(shù) T，請(qǐng)畫(huà)出與其對(duì)應(yīng)的中序線(xiàn)索二叉樹(shù)。 28 25 40 55 60 33 08 54 解 :因?yàn)橹行虮闅v序列是： 55 40 25 60 28 08 33 54 對(duì)應(yīng)線(xiàn)索樹(shù)應(yīng)當(dāng)按此規(guī)律連線(xiàn)，即 在原二叉樹(shù)中添加虛線(xiàn)。 NIL NIL 55 上堂課例題討論 問(wèn) : 設(shè)一棵完全二叉樹(shù)具有 1000個(gè)結(jié)點(diǎn)，則它有 個(gè)葉子結(jié)點(diǎn)，有 個(gè)度為 2的結(jié)點(diǎn)。 先計(jì)算樹(shù)的深度 k=?log2n?＋ 1 =10。 末層節(jié)點(diǎn)數(shù) =1000(291)=489 第 9層節(jié)點(diǎn)數(shù) =28=256 第 9層葉子節(jié)點(diǎn)數(shù) =(256*2489)/2=11 法 1： 先求全部葉子數(shù)。 n0＝ 489(末層 )＋ 11(第 9層 )=500個(gè)； 法 2： 先求 2度結(jié)點(diǎn)數(shù)。 n2=255(前 8層 )＋ 244(第 9層 )=499個(gè)； 法 3： 無(wú)需求樹(shù)深 k，便可快捷求出 完全二叉樹(shù)的葉子數(shù)： n0= ?n/2? // 取大于 n/2的最小整數(shù)值 可由二叉樹(shù)性質(zhì) 5輕松證明！ (編號(hào)為 i的結(jié)點(diǎn)，其孩子編號(hào)必為 2i和 2i+1) ① ② ④ ⑧ ⑤ ⑨ ③ ? ⑦ …… n n 已知最后一個(gè)結(jié)點(diǎn)編號(hào)為 n，則其雙親（ n/2或 (n1)/2)肯定是最后一個(gè)非葉子結(jié)點(diǎn)。其編號(hào)之后的全部結(jié)點(diǎn)都是葉子了！ 故， n0=nn/2或 n(n1)/2= ?n/2? 56 線(xiàn)索二叉樹(shù)的生成算法 （算法 , 見(jiàn)教材 P134） 目的： 在 依某種順序遍歷 二叉樹(shù)時(shí)修改空指針，添加前驅(qū)或后繼。 注解： 為方便添加結(jié)點(diǎn)的前驅(qū)或后繼，需要設(shè)置兩個(gè)指針： p指針 → 當(dāng)前結(jié)點(diǎn)之指針； pre指針 → 前驅(qū)結(jié)點(diǎn)之指針。 技巧： 當(dāng)結(jié)點(diǎn) p的左 /右域?yàn)榭?時(shí)，只改寫(xiě)它的左域（裝入前驅(qū)pre） ，而其右域（后繼）留給下一結(jié)點(diǎn)來(lái)填寫(xiě)。 或者說(shuō)，當(dāng)前結(jié)點(diǎn)的指針 p應(yīng)當(dāng)送到前驅(qū)結(jié)點(diǎn)的空右域中。 若 plchild＝ NULL,則 {pLtag=1。plchild＝ pre。} //p的前驅(qū)結(jié)點(diǎn)指針 pre存入左空域 若 prerchild＝ NULL, 則 {preRtag＝ 1。