1、第第6 6章章 樹和二叉樹樹和二叉樹樹是一類重要的非線性數據結構，是以分支樹是一類重要的非線性數據結構，是以分支關系定義的層次結構關系定義的層次結構6.1 樹的定義和基本術語樹的定義和基本術語一、樹的定義一、樹的定義 樹是有樹是有 n (n 0) 個結點的有限集合。如果個結點的有限集合。如果 n=0，稱，稱為為空樹空樹；如果；如果 n 0，則：，則：有且僅有一個特定的稱之為有且僅有一個特定的稱之為根根(Root)的結點，它的結點，它只有直接后繼，但沒有直接前驅；只有直接后繼，但沒有直接前驅；當當n 1，除根以外的其它結點劃分為，除根以外的其它結點劃分為 m (m 0) 個互不相交的有限集個互不

2、相交的有限集 T1, T2 , Tm，其中每個集合，其中每個集合本身又是一棵樹，并且稱為根的本身又是一棵樹，并且稱為根的子樹子樹(SubTree)。例如例如:A只有根結點的樹只有根結點的樹其中：其中：A是根；其余結點分成三個互不相交的子集，是根；其余結點分成三個互不相交的子集，T1=B,E,F,K,L； T2=C,G； T3=D,H,I,J,M,T1,T2,T3都是根都是根A的的子樹，且本身也是一棵樹子樹，且本身也是一棵樹有有13個結點的樹個結點的樹ACGBDEFKLHMIJ子樹樹結構的四種表示方法：樹結構的四種表示方法：2)括號表示法：括號表示法：(A(B(E(K,L),F),C(G),D(

3、H(M),I,J)FKLEBMHIJDGCA3)嵌套集合表示法嵌套集合表示法ABEKLFCGDHMIJ4)凹入表示法凹入表示法ACGBDEFKLHMIJ1)倒立樹表示法倒立樹表示法二、樹的基本術語二、樹的基本術語樹的結點樹的結點:包含一個數據元素及若干指向其子樹的分支包含一個數據元素及若干指向其子樹的分支孩子結點孩子結點:結點的子樹的根稱為該結點的孩子結點的子樹的根稱為該結點的孩子雙親結點雙親結點:B結點是結點是A結點的孩子結點的孩子,則則A結點是結點是B結點的雙親結點的雙親兄弟結點兄弟結點:同一雙親的孩子結點同一雙親的孩子結點堂兄結點堂兄結點:同一層上，不同一雙親的結點同一層上，不同一雙親的

4、結點結點層結點層:根結點的層定義為根結點的層定義為1,根的孩子為第根的孩子為第2層結點層結點樹的高度（深度）樹的高度（深度）:樹中結點的最大層次數樹中結點的最大層次數結點的度結點的度:結點的子樹個數結點的子樹個數樹的度樹的度: 樹中各結點的度的最大值樹中各結點的度的最大值葉子結點葉子結點:也叫終端結點，是度為也叫終端結點，是度為0的結點的結點分枝結點分枝結點:度不為度不為0的結點；的結點；森林森林:互不相交的樹集合；互不相交的樹集合；有序樹有序樹:子樹從左到右有序子樹從左到右有序,(即左右子樹不能互換即左右子樹不能互換)無序樹無序樹:不考慮子樹的左右順序；不考慮子樹的左右順序；結點結點A的度：

5、的度：結點結點B的度：的度：結點結點M的度：的度：葉子：葉子：結點結點A的孩子：的孩子：結點結點B的孩子：的孩子：結點結點I的雙親：的雙親：結點結點L的雙親：的雙親：結點結點B，C，D為兄弟為兄弟結點結點K，L為兄弟為兄弟樹的度：樹的度：結點結點A的層次：的層次：結點結點M的層次：的層次：樹的深度：樹的深度：結點結點F，G為堂兄弟為堂兄弟結點結點A是結點是結點F，G的祖先的祖先320B,C,DE,F314K，L，F，G，M，I，JDE4ACGBDEFKLHMIJ 1）InitTree(&T); 2）DestroyTree(&T); 3）CreateTree(&T, de

6、finition); 4）ClearTree(&T); 5）TreeEmpty(T); 6）TreeDepth(T); 7） Root(T); 8） Value(T, &cur_e); 9） Assign(T, cur_e, value); 10）Parent(T, cur_e); 11）LeftChild(T, cur_e); 12）RightSibling(T, cur_e); 13）InsertChild(&T, &p, i, c); 14）DeleteChild(&T,&p, i); 15）TraverseTree(T, Visit( )

7、;三、樹的基本操作三、樹的基本操作62175 438910 11 12五種基本形態：五種基本形態：一棵二叉樹是結點的一個有限集合，該集合或者為空，一棵二叉樹是結點的一個有限集合，該集合或者為空，或者是由一個根結點加上兩棵分別稱為左子樹和右子樹或者是由一個根結點加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成的、互不相交的二叉樹組成LLRR6.2 二叉樹二叉樹一、定義一、定義每個結點至多有二棵子樹每個結點至多有二棵子樹( (即不存在度大于即不存在度大于2 2的結點的結點) )二叉樹的子樹有左、右之分，且其次序不能任意顛倒二叉樹的子樹有左、右之分，且其次序不能任意顛倒特點特點：1、滿二叉樹、

8、滿二叉樹 (Full Binary Tree) 一棵深度為一棵深度為k且有且有2k-1個結點的二叉樹個結點的二叉樹二、兩種特殊形態的二叉樹二、兩種特殊形態的二叉樹621754389 10 1113 14 1512滿二叉樹滿二叉樹2、完全二叉樹、完全二叉樹 (Complete Binary Tree) 若設二叉樹的高度為若設二叉樹的高度為h，則共有，則共有h層，除第層，除第 h 層外，層外，其它各層其它各層 (1 h-1) 的結點數都達到最大個數，第的結點數都達到最大個數，第 h 層從右向左層從右向左連續連續缺若干結點缺若干結點 每個結點都與深度為每個結點都與深度為k的滿二叉樹中編號從的滿二叉樹

9、中編號從1到到n結結點一一對應點一一對應621754389 10 11 12完全二叉樹完全二叉樹215436 7216543非完全二叉樹非完全二叉樹性質性質1 在二叉樹的第在二叉樹的第 i 層上至多有層上至多有 2i-1個結點。個結點。(i 1) 證明用歸納法證明用歸納法證明：證明：當當i=1時，只有根結點，時，只有根結點，2i-1=20=1假設對所有假設對所有j，ij 1，命題成立，即第，命題成立，即第j層上至多有層上至多有2j-1 個結點個結點由歸納假設第由歸納假設第i-1 層上至多有層上至多有 2i-2個結點個結點由于二叉樹的每個結點的度至多為由于二叉樹的每個結點的度至多為2，故在第，故

10、在第i層上的最層上的最大結點數為第大結點數為第i-1層上的最大結點數的層上的最大結點數的2倍，即倍，即2*2i-2= 2i-16.2.2 6.2.2 二叉樹的性質二叉樹的性質性質性質2 深度為深度為 k 的二叉樹至多有的二叉樹至多有 2k-1個結點個結點(k 1)kii112 20 + 21 + + 2k-1 = 2k-1kii1(層上的最大結點數）第證明：證明：由性質由性質1可見，深度為可見，深度為k的二叉樹的最大結點數的二叉樹的最大結點數性質性質3 對任何一棵二叉樹對任何一棵二叉樹T, 如果其葉子結點數為如果其葉子結點數為n0, 度為度為2的結點數為的結點數為 n2,則則n0n21.證明證

11、明:若度為若度為1的結點有的結點有 n1 個，個，結點個數為，結點個數為 n，則：則：n = n0 + n1 + n2 若總邊數為若總邊數為 e e，則根據二叉樹的定義有：，則根據二叉樹的定義有：e = 2n2 + n1 = n - 1因此，有因此，有 2n2 + n1 = n0 + n1 + n2 - 1 n2 = n0 - 1 n0 = n2 + 1 證明：證明：設完全二叉樹的深度為設完全二叉樹的深度為 k，則根據性質，則根據性質2和完全和完全二叉樹的定義有二叉樹的定義有2k-1 - 1 n 2k- 1或或 2k-1 n 2k取對數取對數 k-1 log2n 1，則其雙親是結點，則其雙親是

12、結點 i/2 2)如果如果2in，則結點，則結點i為葉子結點，無左孩子；為葉子結點，無左孩子； 否則，其左孩子是結點否則，其左孩子是結點2i3)如果如果2i1n，則結點，則結點i無右孩子；無右孩子； 否則，其右孩子是結點否則，其右孩子是結點2i162175438910 11 12練習：練習：1、設樹、設樹T的度為的度為4，其中度為，其中度為1,2,3,4的結點個數分的結點個數分別為別為4,2,1,1。T有多少個葉子葉子結點？有多少個葉子葉子結點？2、設一棵完全二叉樹有、設一棵完全二叉樹有1000個結點。問該完全二個結點。問該完全二叉樹有多少個葉子結點？有多少個度為叉樹有多少個葉子結點？有多少個

13、度為2的結點？的結點？有多少個度為有多少個度為1的結點？若完全二叉樹有的結點？若完全二叉樹有1001個結個結點，再回答上述問題，并說明理由。點，再回答上述問題，并說明理由。 1、解：各結點射出的分支總數為：、解：各結點射出的分支總數為： 4*1+2*2+1*3+4*1=15即樹中總結點為：即樹中總結點為：15+1=16由條件可知非葉子結點數為：由條件可知非葉子結點數為：4+2+1+1=8即葉子結點個數為：即葉子結點個數為：16-8=82、解：若完全二叉樹中結點總數為偶數，則：、解：若完全二叉樹中結點總數為偶數，則：n1=1,n0=n2+1;即此題中：即此題中：n0=500,n1=1,n2=49

14、9若完全二叉樹中結點總數為奇數，則：若完全二叉樹中結點總數為奇數，則： n1=0,n0=n2+1;即此題中：即此題中：n0=501,n1=0,n2=500完全二叉樹完全二叉樹 的順序表示的順序表示6.2.36.2.3 、二叉樹的存儲結構、二叉樹的存儲結構12489 105673一、順序表示一、順序表示1 2 3 4 5 6 7 8 9 10第第i個結點的左右孩子一定個結點的左右孩子一定保存在第保存在第2i和和2i+1號單元里號單元里缺點缺點:浪費空間。最壞的情況下，深度為浪費空間。最壞的情況下，深度為k且只有且只有k個個結點的單支樹，卻需要長度為結點的單支樹，卻需要長度為2k-1的一維數組的一

15、維數組9123654789 10一般二叉樹的順序表示一般二叉樹的順序表示1090000876504321二、鏈表表示二、鏈表表示含兩個指針域的結點結含兩個指針域的結點結構構lChild data rChild含三個指針域的結點結含三個指針域的結點結構構lChild data parent rChild二叉鏈表二叉鏈表 data lChildrChild三叉鏈表三叉鏈表parent data lChildrChildlchild data rchild ABCDEFG AB C D E F Gtypedef struct BiTNode TElemType data; struct BiTNod

16、e *lchild , *rchild ; BiTNode , *BiTree ;1、二叉鏈表的存儲表示、二叉鏈表的存儲表示在在n個結點的二叉鏈表中有個結點的二叉鏈表中有n+1個空鏈域個空鏈域lchild data parent rchild A B C D E F Gtypedef struct BiTNode TElemType data; struct BiTNode *lchild , *rchild, *parent ; BiTNode , *BiTree ;2、三叉鏈表的存儲表示、三叉鏈表的存儲表示ABCDEFG遍歷：遍歷：按某種搜索路徑訪問二叉樹的每個結點，而且按某種搜索路徑訪問

17、二叉樹的每個結點，而且每個結點僅被訪問一次每個結點僅被訪問一次訪問：訪問：含義很廣，可以是對結點的各種處理，如修改含義很廣，可以是對結點的各種處理，如修改結點數據、輸出結點數據結點數據、輸出結點數據二叉樹是非線性結構，每個結點可能有兩個后繼，如何二叉樹是非線性結構，每個結點可能有兩個后繼，如何訪問二叉樹的每個結點，而且每個結點僅被訪問一次？訪問二叉樹的每個結點，而且每個結點僅被訪問一次？6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹遍歷是各種數據結構最基本的操作，許多其他的操作遍歷是各種數據結構最基本的操作，許多其他的操作可以在遍歷基礎上實現可以在遍歷基礎上實現對于線性結構由于每個結點只

18、有一個直接后繼，遍歷對于線性結構由于每個結點只有一個直接后繼，遍歷是很容易的事是很容易的事一、二叉樹的遍歷方法一、二叉樹的遍歷方法令令:L:遍歷左子樹遍歷左子樹 D:訪問根結點訪問根結點 R:遍歷右子樹遍歷右子樹有六種遍歷方法有六種遍歷方法: DLR，LDR，LRD,DRL，RDL，RLD先左后右先左后右,有三種遍歷方法：有三種遍歷方法： DLR、LDR、LRD ，分別稱為分別稱為先序遍歷、中序遍歷、后序遍歷先序遍歷、中序遍歷、后序遍歷二叉樹的遍歷可以分解為二叉樹的遍歷可以分解為:訪問根，遍歷左子樹和遍訪問根，遍歷左子樹和遍歷右子樹歷右子樹 A A B B D D C C E E F F G

19、G1、先序遍歷（、先序遍歷（DLR）若二叉樹非空若二叉樹非空 (1)訪問根結點；訪問根結點； (2)先序遍歷左子樹；先序遍歷左子樹； (3)先序遍歷右子樹；先序遍歷右子樹； 先序遍歷序列：先序遍歷序列：A B D E G C F例例:先序遍歷右圖所示的二叉樹先序遍歷右圖所示的二叉樹 （1）訪問根結點）訪問根結點A （2）先序遍歷左子樹）先序遍歷左子樹 （3）先序遍歷右子樹）先序遍歷右子樹 A A B B D D C C E E F F G G2、中序遍歷（、中序遍歷（LDR）若二叉樹非空若二叉樹非空(1)中序遍歷左子樹中序遍歷左子樹(2)訪問根結點訪問根結點(3)中序遍歷右子樹中序遍歷右子樹

20、中序遍歷序列：中序遍歷序列： D B G E A C F例例:中序遍歷右圖所示的二叉樹中序遍歷右圖所示的二叉樹 （1）中序遍歷左子樹）中序遍歷左子樹 （2）訪問根結點）訪問根結點A （3）中序遍歷右子樹）中序遍歷右子樹 A A B B D D C C E E F F G G3、后序遍歷（、后序遍歷（LRD）若二叉樹非空若二叉樹非空(1)后序遍歷左子樹后序遍歷左子樹(2)后序遍歷右子樹后序遍歷右子樹(3)訪問根結點訪問根結點 后序遍歷序列：后序遍歷序列： D G E B F C A例：例：后序遍歷右圖所示的二叉樹后序遍歷右圖所示的二叉樹 （1）后序遍歷左子樹）后序遍歷左子樹 （2）后序遍歷右子樹

21、）后序遍歷右子樹 （3）訪問根結點）訪問根結點A A A B B D D C C E E F F G G 先序遍歷序列：先序遍歷序列：例例:用二叉樹表示表達式用二叉樹表示表達式 a+b*(c-d)-e/f- + a * b c d / e f 前綴式前綴式(波蘭式波蘭式)中序遍歷序列：中序遍歷序列：a + b * c d e / f 中綴式中綴式后序遍歷序列：后序遍歷序列：a b c d - * + e f / - 后綴式后綴式(逆波蘭式逆波蘭式) 若二叉樹非空若二叉樹非空 （1）訪問根結點；）訪問根結點； （2）先序遍歷左子樹）先序遍歷左子樹 （3）先序遍歷右子樹；）先序遍歷右子樹；二、遍歷

22、的遞歸算法二、遍歷的遞歸算法 上面介紹了三種遍歷方法，顯然可以用遞歸的方式實現上面介紹了三種遍歷方法，顯然可以用遞歸的方式實現三種遍歷方法，以先序為例：三種遍歷方法，以先序為例：先序遍歷的定義：先序遍歷的定義：先序遍歷遞歸算法先序遍歷遞歸算法void PreOrderTraverse(BiTree T) if (T) printf(T-data)； PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); A A B B D D C C E E F F G G H H I I J J K K L L三、三、 遍歷的非遞歸算法遍歷的非遞歸算法

23、(以中序遍歷為例以中序遍歷為例)中序遍歷序列：中序遍歷序列： H D K I L B E J A F C G A A B B D D C C E E F F G G H H I I J J K K L Lvoid InOrderTraverse(BiTree T) InitStack(S); t=T; while (t) Push(S,t); t=t-lchild; if (!StackEmpty(S) Pop(S,t); printf(t-data); t=t-rchild; while(t | !StackEmpty(S) A A B B D D C C E E F F G G H H I

24、 I J J K K L Lvoid InOrderTraverse(BiTree T) InitStack(S); p=T; while(p|!StackEmpty(S) if(p) Push(S,p); p=p-lchild; else Pop(S,p);printf(p-data); p=p-rchild; A A B B D D C C E E F F G G H H I I J J K K L Lvoid InOrderTraverse(BiTree T) InitStack(S); Push(S,T); while(!StackEmpty(S) while(GetTop(S,p)&

25、amp;p) Push(S,p-lchild); Pop(S,p); if(!StackEmpty(S) Pop(S,p); printf(p-data); Push(S,p-rchild); A A B B D D C C E E F F G G H H I I J J K K L L四、二叉樹的建立四、二叉樹的建立基本思想：基本思想：輸入輸入在空子樹處添加在空子樹處添加*的二叉樹的的二叉樹的先序序列先序序列設每個元素是一個字符，按先序遍歷的順序，建立二叉設每個元素是一個字符，按先序遍歷的順序，建立二叉鏈表的所有結點，并完成相應結點的鏈接。鏈表的所有結點，并完成相應結點的鏈接。 D D A

26、A BB C C EE FFT T* * * * * * * *(在空子樹處添加在空子樹處添加*的二叉樹的的二叉樹的)先序序列：先序序列：A B D * F * * * C E * * * A A B B D D C C E E F F先序序列：先序序列：A B D F C E A A B B D D C C E E F FStatus CreateBiTree(BiTree &T) scanf (&ch); if (ch= = * ) T=NULL; else if (! (T=(BiTNode * )malloc(sizeof(BiTNode) exit(OVERFLOW)

27、; T-date = ch; CreateBiTree(T-lchild); CreateBiTree(T-rchild); return OK; D D A A BB C C EE FFT T輸入：輸入：A B D * F * * * C E * * *五、利用中序、先序法或中序、后序法求二叉樹五、利用中序、先序法或中序、后序法求二叉樹1、利用中序、先序法求二叉樹、利用中序、先序法求二叉樹步驟步驟: (1)利用先序順序可知：第一個是根利用先序順序可知：第一個是根(2)利用中序順序，配合步驟利用中序順序，配合步驟(1)所找到的根作對所找到的根作對應，可分成左右兩子樹應，可分成左右兩子樹(3)再

28、分別按再分別按(1)(2)步驟處理左、右子樹，找到其步驟處理左、右子樹，找到其他的根和終端結點他的根和終端結點例例:中序序列中序序列: D C E F B H G A K J L I M 先序序列先序序列: A B C D E F G H I J K L M2、利用中序、后序法求二叉樹、利用中序、后序法求二叉樹步驟步驟: (1)利用后序順序可知：最后一個一定是根利用后序順序可知：最后一個一定是根(2)利用中序順序，配合步驟利用中序順序，配合步驟(1)所找到的根作對所找到的根作對應，可分成左右兩子樹應，可分成左右兩子樹(3)再分別按再分別按(1)(2)步驟來處理左、右子樹步驟來處理左、右子樹例例

29、:中序序列中序序列: D C E F B H G A K J L I M 后序序列后序序列: D F E C H G B K L J M I A練習：練習：1、已知中序序列、已知中序序列:DCEBAKJF 后序序列后序序列:DECBKJFA2、已知中序序列、已知中序序列:A-B*C+D/E*F 先序序列先序序列:/+-A*BCD*EF3、已知中序序列、已知中序序列:CBEDFAHJKIG 后序序列后序序列:CEFDBKJIHGAJ計算二叉樹的結點個數計算二叉樹的結點個數J求二叉樹中葉子結點的個數求二叉樹中葉子結點的個數J求二叉樹的高度求二叉樹的高度J按層次遍歷二叉樹按層次遍歷二叉樹六、線索二叉

30、樹六、線索二叉樹 (Threaded Binary Tree)1 1、基本概念、基本概念前驅與后繼：在二叉樹的先序、中序或后序遍歷前驅與后繼：在二叉樹的先序、中序或后序遍歷序列中，兩個相鄰的結點互稱為序列中，兩個相鄰的結點互稱為前驅與后繼。前驅與后繼。線索：指向前驅或后繼結點的指針。線索：指向前驅或后繼結點的指針。線索二叉樹：加上線索的二叉鏈表表示的二叉樹。線索二叉樹：加上線索的二叉鏈表表示的二叉樹。即加上結點前趨、后繼信息的二叉樹。即加上結點前趨、后繼信息的二叉樹。線索化：對二叉樹按某種遍歷次序使其變為線索線索化：對二叉樹按某種遍歷次序使其變為線索二叉樹的過程。二叉樹的過程。有有n個結點的二

31、叉鏈表，有個結點的二叉鏈表，有n+1個空指針域，故可個空指針域，故可利用這些的空指針域存放結點的前趨和后繼指針，利用這些的空指針域存放結點的前趨和后繼指針，以這種結點構成的二叉鏈表稱為以這種結點構成的二叉鏈表稱為線索鏈表。線索鏈表。在線索二叉樹的結點中增加兩個標志域在線索二叉樹的結點中增加兩個標志域：Ltag=0, lchild指向其左孩子指向其左孩子1, lchild指向其前驅指向其前驅Rtag= 0, rchild指向其右孩子指向其右孩子1, rchild指向其后繼指向其后繼2、實現、實現結點結構結點結構LtagRtag線索鏈表的類型說明線索鏈表的類型說明typedef enum link

32、 , thread PointerTag; typedef struct BiThrNode TElemType data; Struct BiThrNode *lchild, *rchild; PointerTag Ltag, Rtag; BiThrNode，*BiThrTreeABCDE A B D C ET先序序列：ABCDE0000111111LtagRtag1）先序線索二叉樹先序線索二叉樹 A B D C ET中序序列：BCAED0000111111ABCDE2）中）中序線索二叉樹序線索二叉樹 A B D C ET后序序列：CBEDA0000111111ABCDE3）后）后序線索二叉

33、樹序線索二叉樹1、雙親表示：、雙親表示：通過保存每個結點的雙親結點的位置，通過保存每個結點的雙親結點的位置，表示樹中結點之間的結構關系表示樹中結點之間的結構關系6.4 樹和森林樹和森林一、樹的存儲結構一、樹的存儲結構typedef struct PTNode TElemType data; int parent; PTNode;parentdata存儲實現時，以一組連續空間存儲樹的結點，同時在結存儲實現時，以一組連續空間存儲樹的結點，同時在結點中附設一個指針，存放雙親結點在鏈表中的位置。點中附設一個指針，存放雙親結點在鏈表中的位置。用雙親表示實現的樹定義用雙親表示實現的樹定義#define M

34、AX_TREE_SIZE 100typedef struct PTNode nodesMAX_TREE_SIZE; int r,n;/根位置，結點數根位置，結點數PTree; 如何找孩子結點如何找孩子結點?特點：特點：找結點的雙親容易，找結點的孩子難找結點的雙親容易，找結點的孩子難7 70 0T.nT.rABCDEFG3G1F1E0D0C0B-1Adata parent01234562、孩子表示法、孩子表示法通過保存每個結點的孩子結點的位置通過保存每個結點的孩子結點的位置,表示樹中結點之間表示樹中結點之間的結構關系的結構關系與雙親表示法相反與雙親表示法相反,孩子表示法適合實現涉及孩子的操作孩子

35、表示法適合實現涉及孩子的操作方法一方法一 ：多重鏈表（類似二叉鏈表）：多重鏈表（類似二叉鏈表）兩種方式：定長結點兩種方式：定長結點 不定長結點不定長結點1、定長結點定長結點等數量的鏈域等數量的鏈域 data child1child2child3childdABCDEFGABCDEFG 空鏈域空鏈域n(k-1)+1個個 data degree child1child2childd2、不定長結點不定長結點IACBDHGFE方法二：孩子鏈表方法二：孩子鏈表對樹的每個結點用線性鏈表存貯它的孩子結點對樹的每個結點用線性鏈表存貯它的孩子結點 1 3 2 8 7 6 4 5 IHGFE DC B A 0 1

36、 2 3 4 5 6 7 8 9 90 0T.nT.r樹的孩子鏈表類型定義樹的孩子鏈表類型定義typedef struct CTNode int child; struct CTNode * next; * ChildPtr; typedef struct TElemType data; ChildPtr firstchild; CTBox; typedef struct CTBox nodesMAX_TREE_SIZE; int n, r;CTree;0 1 2 3 4 5 6 7 8 9 90 0T.nodesT.nT.rIHGF E DC B A 1 3 2 8 7 6 4 5 特點：特

37、點：找結點的孩子容易，找結點的雙親難找結點的孩子容易，找結點的雙親難方法三：帶雙親的孩子鏈表方法三：帶雙親的孩子鏈表將雙親表示和孩子表示聯合起來。將雙親表示和孩子表示聯合起來。0 1 2 3 4 5 6 7 833211000-1 IHGF E DC B A 1 3 2 8 7 6 4 5 IACBDHGFE特點：特點：找結點的雙親和孩子都容易。找結點的雙親和孩子都容易。ABRECDFGHKP137圖圖6.14(b)方法四：孩子兄弟表示法方法四：孩子兄弟表示法用二叉鏈鏈表作為樹的存貯結構用二叉鏈鏈表作為樹的存貯結構結點結構：結點結構： datafirstchildnextsiblingtype

38、def struct CSNode ElemType data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;結構定義：結構定義：ABCDEFG空鏈域空鏈域n+1個個A BE F G D C 特點：特點：操作容易操作容易破壞了樹的層次破壞了樹的層次例如：例如：二叉樹與樹都可用二叉鏈表存貯，以二叉鏈表作中介，二叉樹與樹都可用二叉鏈表存貯，以二叉鏈表作中介，可導出樹與二叉樹之間的轉換可導出樹與二叉樹之間的轉換樹樹根根結點結點X的第一個孩子的第一個孩子結點結點X緊鄰的右兄弟緊鄰的右兄弟二叉樹二叉樹 根根 結點結點X的左孩子的左孩子

39、 結點結點X的右孩子的右孩子二、樹與二叉樹的轉換二、樹與二叉樹的轉換I IA AC CD DH HG GF FE E樹樹B B二叉樹二叉樹F FI IA AB BH HG GE EC CD DA BE CG D H I F 樹與二叉樹的轉換樹與二叉樹的轉換I IA AC CD DH HG GF FE E樹樹B B二叉樹二叉樹F FI IA AB BH HG GE EC CD D樹轉換成的二叉樹其右子樹一定為空樹轉換成的二叉樹其右子樹一定為空森林：樹的集合森林：樹的集合 將森林中樹的根看成兄弟，可用樹的孩子兄弟表示將森林中樹的根看成兄弟，可用樹的孩子兄弟表示法來存儲森林；用樹與二叉樹的轉換方法，

40、進行森林與法來存儲森林；用樹與二叉樹的轉換方法，進行森林與二叉樹轉換；可用樹的遍歷方法對森林進行遍歷二叉樹轉換；可用樹的遍歷方法對森林進行遍歷包含兩棵樹的森林包含兩棵樹的森林I IA AC CD DH HG GF FE EB B J J K K M M N N L L O O P PT1 T2 T3FGAB C DEHIJKABCEDHIKJFG森林的二叉樹表示森林的二叉樹表示森林與二叉樹的轉換森林與二叉樹的轉換ABCDEFGHIKJ樹根相連樹根相連三、樹的遍歷三、樹的遍歷先根次序遍歷先根次序遍歷后根次序遍歷后根次序遍歷對應二叉樹先序遍歷對應二叉樹先序遍歷 ABEFCGDHI樹的先根遍歷結果與

41、其對應二叉樹樹的先根遍歷結果與其對應二叉樹表示的先序遍歷結果相同表示的先序遍歷結果相同1、樹的先根次序遍歷、樹的先根次序遍歷I IA AC CB BD DH HG GF FE E當樹非空時當樹非空時 訪問根結點訪問根結點 依次先根遍歷根的各棵子樹依次先根遍歷根的各棵子樹樹先根遍歷樹先根遍歷 ABEFCGDHIF FI IA AB BD DH HG GC CE E二叉樹二叉樹2、樹的后根次序遍歷、樹的后根次序遍歷:對應二叉樹中序遍歷對應二叉樹中序遍歷 EFBGCHIDA樹的后根遍歷結果與其對應二叉樹樹的后根遍歷結果與其對應二叉樹表示的中序遍歷結果相同表示的中序遍歷結果相同當樹非空時當樹非空時依次

42、后根遍歷根的各棵子樹依次后根遍歷根的各棵子樹訪問根結點訪問根結點I IA AC CB BD DH HG GF FE E樹后根遍歷樹后根遍歷 EFBGCHIDAF FI IA AB BD DH HG GC CE E二叉樹二叉樹四、森林的遍歷四、森林的遍歷先序遍歷先序遍歷中序遍歷中序遍歷對應二叉樹先序遍歷對應二叉樹先序遍歷 ABCDEFGHIKJ1、森林的先序遍歷、森林的先序遍歷當森林非空時當森林非空時 訪問森林中第一棵樹的根結點訪問森林中第一棵樹的根結點 先序遍歷第一棵樹中根結點的子樹森林先序遍歷第一棵樹中根結點的子樹森林先序遍歷除第一棵樹外剩余的樹構成的森林先序遍歷除第一棵樹外剩余的樹構成的森

43、林T1 T2 T3FGAB C DEHIJKABCEDHIKJFG森林先序遍歷森林先序遍歷 ABCDEFGHIKJ對應二叉樹中序遍歷對應二叉樹中序遍歷 BCEDAGFKIJH2、森林的中序遍歷、森林的中序遍歷當森林非空時當森林非空時中序遍歷森林中第一棵樹的根結點的子樹森林中序遍歷森林中第一棵樹的根結點的子樹森林訪問森林中第一棵樹的根結點訪問森林中第一棵樹的根結點中序遍歷除第一棵樹外剩余的樹構成的森林中序遍歷除第一棵樹外剩余的樹構成的森林T1 T2 T3FGAB C DEHIJKABCEDHIKJFG森林中序遍歷森林中序遍歷BCEDAGFKIJH練習：練習：1、對以下兩棵二叉樹分別畫出它們的順序

44、存儲結構、對以下兩棵二叉樹分別畫出它們的順序存儲結構ABDEFCGIJKABDEFCIJABDEFCGH2、對右邊的樹，分別畫出、對右邊的樹，分別畫出孩子鏈表和孩子兄弟鏈表孩子鏈表和孩子兄弟鏈表存儲結構存儲結構3、分別畫出下列樹對應的二叉樹、分別畫出下列樹對應的二叉樹ABCABCABDEFCGHIJK4、將下列森林轉化為相應的二叉樹、將下列森林轉化為相應的二叉樹121415139101113245867ABD5、畫出下列二叉樹對應的森林、畫出下列二叉樹對應的森林ABDEFCGHIJKMJ路徑路徑:樹中一個結點到另一結點間的分支樹中一個結點到另一結點間的分支J路徑長度路徑長度(Path Leng

45、th):路徑上的分支數路徑上的分支數J樹的外部路徑長度樹的外部路徑長度:各葉結點各葉結點(外結點外結點)到根結點的路到根結點的路 徑長度之和徑長度之和 (EPL)J樹的內部路徑長度樹的內部路徑長度:各非葉結點各非葉結點(內結點內結點)到根結點的到根結點的 路徑長度之和路徑長度之和 (IPL)J樹的路徑長度樹的路徑長度:從根到每個葉子結點的路徑長度之和從根到每個葉子結點的路徑長度之和 PL = EPL + IPL6.5 哈夫曼樹哈夫曼樹及其應用及其應用一、最優二叉樹一、最優二叉樹(哈夫曼樹哈夫曼樹)12345678234567813*1+2*3 = 91*1+2*1+3*1+4*1 = 10EP

46、L =EPL =J樹的帶權路徑長度樹的帶權路徑長度 (Weighted Path Length) 樹的各葉子結點所帶的權值與該結點到根的路徑長度樹的各葉子結點所帶的權值與該結點到根的路徑長度的乘積的和的乘積的和10niiilwWPLJ結點的權結點的權:結點上被賦予的一定意義的實數結點上被賦予的一定意義的實數7*2+5*2+2*2+4*2=36帶權路徑長度帶權路徑長度達到最小達到最小abcd7524abcd4275abcd75244*1+2*2+7*3+5*3=447*1+5*2+2*3+4*3=35WPL=WPL=WPL=權值大的結點離根最近權值大的結點離根最近F : 7 5 2 4J哈夫曼樹哈夫曼樹(最優二叉樹最優二叉樹):帶權路徑長度帶權路徑長度WPL最小的二最小的二叉樹叉樹abcd7524二、哈夫曼樹的建立二、哈夫曼樹的建立1、編制一個將百分制轉換成五級分制的程序、編制一個將百分制轉換成五級分制的程序60?70?80?90?0.050.150.400.300.10NNNNYYYY80以上的數據需要以上的數據需要3次或次或3次以上比較才能