武漢軟件工程職業(yè)學(xué)院《數(shù)據(jù)結(jié)構(gòu)講義》第14講-2叉樹、樹和森林

1、武漢軟件工程職業(yè)學(xué)院 數(shù)據(jù)結(jié)構(gòu)講義第 14 講-2 叉樹、樹和森林第四章樹第十四講二叉樹、樹和森林1掌握樹的存儲(chǔ)結(jié)構(gòu)。2掌握樹森林與二叉樹的相互轉(zhuǎn)換，3. 樹的遍歷方法 。教學(xué)重點(diǎn)：樹森林與二叉樹的相互轉(zhuǎn)換教學(xué)難點(diǎn)：樹森林與二叉樹的相互轉(zhuǎn)換授課內(nèi)容4.5二叉樹、樹和森林樹的存儲(chǔ)結(jié)構(gòu)樹的存儲(chǔ)結(jié)構(gòu)有多種形式。 下面介紹三種常用的存儲(chǔ)結(jié)構(gòu)。1雙親數(shù)組表示發(fā)第四章樹這種存儲(chǔ)結(jié)構(gòu)是利用每個(gè)結(jié)點(diǎn)（除根結(jié)點(diǎn)外）只有唯一雙親的特點(diǎn)， 用一維數(shù)組來存儲(chǔ)一棵一般的樹。圖 451 便是一棵樹及其雙親表示的存儲(chǔ)結(jié)構(gòu)。 在這種結(jié)構(gòu)中， 尋找一個(gè)結(jié)點(diǎn)的雙親時(shí)，只要訪問它的 parent 域，便可立即得到它的雙親的存儲(chǔ)位置

2、； 但是，若要尋找一個(gè)結(jié)點(diǎn)的孩子時(shí)，則需遍歷整個(gè)數(shù)組。0A-1A1B0C0B2D0E1EFG3F1G3HJ4H5I55J5圖 451 樹的雙親2結(jié)點(diǎn)定長(zhǎng)的孩子鏈表表示法圖 451 所示的樹，它是一個(gè)三叉樹， 可用三叉鏈表來存儲(chǔ)。 其結(jié)點(diǎn)結(jié)構(gòu)為： 一個(gè)數(shù)據(jù)域和三個(gè)指針域。指針域用于指向該結(jié)點(diǎn)的各個(gè)孩子結(jié)點(diǎn)。該樹的三重鏈表如圖 4 52(a) 所示。3孩子兄弟二叉鏈表表示法第四章樹如果用孩子兄弟鏈表作為存儲(chǔ)結(jié)構(gòu)， 其結(jié)點(diǎn)結(jié)構(gòu)為：一個(gè)數(shù)據(jù)域和兩個(gè)指針域。 其中一個(gè)指針指向它的第一個(gè)孩子結(jié)點(diǎn)， 另一個(gè)指向它的兄弟結(jié)點(diǎn)。圖 451 中樹的孩子兄弟鏈表如圖 452（b）所示。AABDB DFF (a) 孩

3、子鏈(b) 孩子 兄圖452 樹的假設(shè)把圖 452（b）中指向兄弟的水平方向指針改為下斜 45°，不難發(fā)現(xiàn)它與一棵二叉樹的鏈表結(jié)構(gòu)十分相似。 由于二叉樹的結(jié)構(gòu)規(guī)范、簡(jiǎn)單，因此常將一般樹結(jié)構(gòu)轉(zhuǎn)換為二叉樹結(jié)構(gòu)，然后利用二叉樹已有的算法進(jìn)行處理。樹與二叉樹之間的轉(zhuǎn)換對(duì)于一般樹， 樹中孩子的次序并不重要， 只要雙親與孩子的關(guān)系正確即可。但在二叉樹中，左、右孩子的次序是嚴(yán)格區(qū)分的。 所以在討論二叉樹和一般樹之間的轉(zhuǎn)換時(shí)， 為不引起混淆， 就第四章樹約定按樹上現(xiàn)有結(jié)點(diǎn)次序進(jìn)行轉(zhuǎn)換。1一般樹轉(zhuǎn)換為二叉樹將一般樹轉(zhuǎn)化為二叉樹的思路， 主要根據(jù)樹的孩子兄弟存儲(chǔ)方式而來，具體步驟為：（ 1）加線。在各兄

4、弟結(jié)點(diǎn)之間用虛線相連?？衫斫鉃槊總€(gè)結(jié)點(diǎn)的兄弟指針指向它的一個(gè)兄弟。（ 2）抹線。對(duì)每個(gè)結(jié)點(diǎn)僅保留它與其最左孩子的連線，抹去該結(jié)點(diǎn)與其它孩子之間的連線?？衫斫鉃槊總€(gè)結(jié)點(diǎn)僅有一個(gè)孩子指針，讓它指向自己的第一個(gè)孩子。（ 3）旋轉(zhuǎn)。把虛線改為實(shí)線從水平方向向下旋轉(zhuǎn) 45°，成右斜下方向。 原書中實(shí)線成左斜下方向。這樣就形成一棵二叉樹。由于二叉樹中各結(jié)點(diǎn)的右孩子都是原一樹數(shù)中該結(jié)點(diǎn)的兄弟， 而一般樹的根結(jié)點(diǎn)又沒有兄弟結(jié)點(diǎn)，因此所生成的二叉樹的根結(jié)點(diǎn)沒有右子樹。在所生成的二叉樹中某一結(jié)點(diǎn)的左孩子仍是原來樹中該結(jié)點(diǎn)的長(zhǎng)子，并且是它的最左孩子。圖 453 是一個(gè)由一般樹轉(zhuǎn)為二叉樹的實(shí)例。第四章樹AA

5、AABBCDBCDBCDECBEFGEFGEFGFDHHHHG(a)(b)(c)(d)圖453 一般樹轉(zhuǎn)換為二叉樹2二叉樹還原為一般樹二叉樹還原為一般樹， 此時(shí)的二叉樹必須是由某一樹轉(zhuǎn)換而來的沒有右子樹的二叉樹。 其還原過程也分為三步：（ 1）加線。若某結(jié)點(diǎn) I 是雙親結(jié)點(diǎn)的左孩子，則將該結(jié)點(diǎn) I 的右孩子以及當(dāng)且 僅當(dāng)連續(xù)地沿著右孩子的右鏈不斷搜索到所有右孩子，都分別與結(jié)點(diǎn) I 的雙親結(jié)點(diǎn)用虛線連接。（ 2）抹線。把原二叉樹中所有雙親結(jié)點(diǎn)與其右孩子的連線抹去。這里的右孩子實(shí)質(zhì)上是原一般數(shù)中結(jié)點(diǎn)的兄弟，抹去的連線是兄弟間的關(guān)系。第四章樹（ 3）進(jìn)行整理。把虛線改為實(shí)線，把結(jié)點(diǎn)按層次排列。二叉樹

6、還原為一般樹的示例，如圖 45 4 所示。AAAABBBBDFHCDCCDCEGJEFEFEFIGHGHGHIJIJIJ圖 454二叉樹還森林與二叉樹的轉(zhuǎn)換森林是樹的有限集合，如圖 455（a）所示。1森林轉(zhuǎn)換為二叉樹森林轉(zhuǎn)換為二叉樹的步驟為：（ 1） 將森林中每棵子樹轉(zhuǎn)換成相應(yīng)的二叉樹，形成有若干二叉樹的森林。（ 2） 按森林中樹的先后次序，依次將后邊一棵二叉樹作為前邊一棵二叉樹根結(jié)點(diǎn)的右子樹， 這樣整個(gè)森林就生成第四章樹了一棵二叉樹。實(shí)際上第一棵樹的根結(jié)點(diǎn)便是生成后的二叉樹的根結(jié)點(diǎn)。圖 455 是森林轉(zhuǎn)化為二叉樹的示例。AFHAFHBDGIBJFKCF DK(a) 一 般(b) 二 叉BAHBAC GHJFC GFDKD IJ(c) 第二棵樹(d) 最K圖455森林轉(zhuǎn)換為二叉樹2二叉樹還原為森林將一棵由森林轉(zhuǎn)換得到的二叉樹還原為森里的步驟是：（ 1） 抹線。將二叉樹的根結(jié)點(diǎn)與其右孩子的連線以及當(dāng)且僅當(dāng)連續(xù)地沿著右鏈