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

1、第十四講二叉樹、樹和森林1. 掌握樹的存儲結(jié)構(gòu)。2. 掌握樹/森林與二叉樹的相互轉(zhuǎn)換,3. 樹的遍歷方法。教學(xué)重點(diǎn)：樹/森林與二叉樹的相互轉(zhuǎn)換教學(xué)難點(diǎn)：樹/森林與二叉樹的相互轉(zhuǎn)換授課內(nèi)容4.5二叉樹、樹和森林樹的存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu)有多種形式。下面介紹三種常用的存儲結(jié)構(gòu)。1. 雙親數(shù)組表示發(fā)這種存儲結(jié)構(gòu)是利用每個結(jié)點(diǎn)（除根結(jié)點(diǎn)外）只有唯一雙親的特點(diǎn)，用一維數(shù)組來存儲 一棵一般的樹。圖4 5 1便是一棵樹及其雙親表示的存儲結(jié)構(gòu)。在這種結(jié)構(gòu)中，尋找一個結(jié)點(diǎn)的雙親時，只要訪問它的pare nt域，便可立即得到它的雙親的存儲位置；但是，若要尋找一個結(jié)點(diǎn)的孩子時，則需遍歷整個數(shù)組。A-1B0C0D0E1

2、F1G3H5I5J50123456789圖4 5 1樹的雙親表示法2. 結(jié)點(diǎn)定長的孩子鏈表表示法圖4 5 1所示的樹，它是一個三叉樹，可用三叉鏈表來存儲。其結(jié)點(diǎn)結(jié)構(gòu)為：一個數(shù)據(jù)域和三個指針域。指針域用于指向該結(jié)點(diǎn)的各個孩子結(jié)點(diǎn)。該樹的三重鏈表如圖4- 52(a)所示。3. 孩子-兄弟二叉鏈表表示法如果用孩子-兄弟鏈表作為存儲結(jié)構(gòu)， 其結(jié)點(diǎn)結(jié)構(gòu)為：一個數(shù)據(jù)域和兩個指針域。其中 一個指針指向它的第一個孩子結(jié)點(diǎn)， 另一個指向它的兄弟結(jié)點(diǎn)。 圖45 1中樹的孩子一兄 弟鏈表如圖4 5 2 ( b)所示。A(b)孩子-兄弟鏈表表示法(a)孩子鏈表表示法圖4 5 2樹的鏈表表示法假設(shè)把圖4 5 2 ( b

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

4、它的 一個兄弟。(2) 抹線。對每個結(jié)點(diǎn)僅保留它與其最左孩子的連線，抹去該結(jié)點(diǎn)與其它孩子之間 的連線?？衫斫鉃槊總€結(jié)點(diǎn)僅有一個孩子指針，讓它指向自己的第一個孩子。(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)的長子，并且是它的最左孩子。 圖4 5 3是一個由一般樹轉(zhuǎn)為二叉樹的實(shí)例。ACBDGEFACDGEF(c)AECFGH(d)圖4 5 3

5、 般樹轉(zhuǎn)換為二叉樹2. 二叉樹還原為一般樹二叉樹還原為一般樹，此時的二叉樹必須是由某一樹轉(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)按層次排列。二叉樹還原為一般樹的示例，如圖4 5-4所示。AEFGHIGIACABDCEFGHIF圖4 5 4 二叉樹還原為一般樹4.

6、5.3 森林與二叉樹的轉(zhuǎn)換森林是樹的有限集合，如圖 4 5 5 (a)所示。1 森林轉(zhuǎn)換為二叉樹森林轉(zhuǎn)換為二叉樹的步驟為：(1) 將森林中每棵子樹轉(zhuǎn)換成相應(yīng)的二叉樹，形成有若干二叉樹的森林。(2) 按森林中樹的先后次序， 依次將后邊一棵二叉樹作為前邊一棵二叉樹根結(jié)點(diǎn)的 右子樹，這樣整個森林就生成了一棵二叉樹。 實(shí)際上第一棵樹的根結(jié)點(diǎn)便是生成后的二叉樹 的根結(jié)點(diǎn)。圖4 55是森林轉(zhuǎn)化為二叉樹的示例。A(c)第二棵樹并入第一棵圖 4 - 5 -(d)最終結(jié)5森林轉(zhuǎn)換為二叉樹2.二叉樹還原為森林將一棵由森林轉(zhuǎn)換得到的二叉樹還原為森里的步驟是：(1) 抹線。將二叉樹的根結(jié)點(diǎn)與其右孩子的連線以及當(dāng)且僅當(dāng)連續(xù)地沿著右鏈