1、第六章第六章樹和二叉樹樹和二叉樹6.1 6.1 樹的定義和基本概念樹的定義和基本概念6.2 6.2 二叉樹二叉樹6.3 6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹6.4 6.4 樹和森林樹和森林6.6 6.6 哈夫曼樹及其應用哈夫曼樹及其應用 第六章第六章 樹和二叉樹樹和二叉樹6.1 樹的類型定義樹的類型定義第六章 樹6.1 樹的定義樹的定義定義定義v定義：樹定義：樹(tree)是是n(n=0)個結點的個結點的有限集有限集T，其，其中：中：ln=0 則稱為則稱為空樹空樹。l當當n0時，時，有且僅有一個特定的結點，稱為樹有且僅有一個特定的結點，稱為樹的的根根(root)l當當n1時，時

2、，其余結點可分為其余結點可分為m(m0)個互不相交個互不相交的的有限集有限集T1,T2,Tm，其中每一個集合本，其中每一個集合本身又是一棵身又是一棵樹樹，稱為根的，稱為根的子樹子樹(subtree)A只有根結點的樹只有根結點的樹ABCDEFGHIJKLM有子樹的樹有子樹的樹根根子樹子樹數據對象數據對象 D：D是具有相同特性的數據元素的集合。是具有相同特性的數據元素的集合。 若若D為空集，則稱為為空集，則稱為空樹空樹 。否則。否則: (1) 在在D中存在唯一的稱為中存在唯一的稱為根根的數據元素的數據元素root； (2) 當當n1時，其余結點可分為時，其余結點可分為m (m0)個互個互 不相交的

3、有限集不相交的有限集T1, T2, , Tm，其中每一，其中每一 棵子集本身又是一棵符合本定義的樹，棵子集本身又是一棵符合本定義的樹， 稱為根稱為根root的的子樹子樹。 數據關系數據關系 R：ADT Tree 基本操作：基本操作：查找類查找類；插入類插入類; 刪除類刪除類； ADT Tree基本術語基本術語v結點結點(node)表示樹中的表示樹中的元素元素，包括，包括數據數據元素及若干元素及若干指向其子樹的指向其子樹的分支分支v結點的度結點的度(degree)結點擁有的結點擁有的子樹數子樹數v葉子葉子(leaf)度為度為0的結點的結點v孩子孩子(child)結點子樹的根稱為該結點的結點子樹的

4、根稱為該結點的孩子孩子v雙親雙親(parents)孩子結點的孩子結點的上層結點上層結點叫該結點的叫該結點的v兄弟兄弟(sibling)同一雙親同一雙親的孩子的孩子v樹的度樹的度一棵樹中一棵樹中最大最大的結點度數的結點度數v結點的層次結點的層次(level)從根結點算起，從根結點算起，根為第一層根為第一層，它，它的孩子為第二層的孩子為第二層v深度深度(depth)樹中結點的樹中結點的最大層次最大層次數數v森林森林(forest)m(m 0)棵棵互不相交互不相交的樹的集合的樹的集合ABCDEFGHIJKLM結點結點A的的度度：3結點結點B的的度度：2結點結點M的的度度：0葉子葉子：K，L，F，G，

5、M，I，J結點結點A的的孩子孩子：B，C，D結點結點B的的孩子孩子：E，F結點結點I的的雙親雙親：D結點結點L的的雙親雙親：E結點結點B，C，D為為兄弟兄弟結點結點K，L為為兄弟兄弟樹的度：樹的度：3結點結點A的層次：的層次：1結點結點M的層次：的層次：4樹的深度：樹的深度：4結點結點F，G為為堂兄弟堂兄弟結點結點A是結點是結點F，G的的祖先祖先結點結點F,G是結點是結點A的子孫結點的子孫結點任何一棵非空樹是一個二元組任何一棵非空樹是一個二元組 Tree = (root，F)其中：其中：root 被稱為根結點被稱為根結點 F 被稱為子樹森林被稱為子樹森林森林：森林：是是m(m0)棵互棵互不相交

6、的樹的集合不相交的樹的集合ArootBCDEFGHIJMKLF趙老根趙老根趙躍進趙躍進趙小康趙小康趙改革趙改革趙開放趙開放趙解放趙解放趙抗美趙抗美趙衛兵趙衛兵趙永紅趙永紅 Root(T) / 求樹的根結點求樹的根結點 查找類：查找類：Value(T, cur_e) / 求當前結點的元素值求當前結點的元素值 Parent(T, cur_e) / 求當前結點的雙親結點求當前結點的雙親結點LeftChild(T, cur_e) / 求當前結點的最左孩子求當前結點的最左孩子 RightSibling(T, cur_e) / 求當前結點的右兄弟求當前結點的右兄弟TreeEmpty(T) / 判定樹是否為

7、空樹判定樹是否為空樹 TreeDepth(T) / 求樹的深度求樹的深度TraverseTree( T, Visit() ) / 遍歷遍歷InitTree(&T) / 初始化置空樹初始化置空樹 插入類：插入類：CreateTree(&T, definition) / 按定義構造樹按定義構造樹Assign(T, cur_e, value) / 給當前結點賦值給當前結點賦值InsertChild(&T, &p, i, c) / 將以將以c為根的樹為根的樹插入為結點插入為結點p的第的第i棵子樹棵子樹 ClearTree(&T) / 將樹清空將樹清空 刪除類：刪

8、除類：DestroyTree(&T) / 銷毀樹的結構銷毀樹的結構DeleteChild(&T, &p, i) / 刪除結點刪除結點p的第的第i棵子樹棵子樹ABCDEFGHIJMKLA( B(E, F(K, L), C(G), D(H, I, J(M) )T1T3T2樹根樹的廣義表表示法樹的廣義表表示法1、圖示法、圖示法2、廣義表法、廣義表法樹的幾種表示法樹的幾種表示法: :ABDCJIHMEFGKL有向樹有向樹：有序樹：有序樹：無序樹：無序樹：樹的基本分類：樹的基本分類：樹型結構樹型結構線性結構線性結構 線性結構線性結構 樹型結構樹型結構 ( (非線性結構非線性結構)

9、 )第一個數據元素第一個數據元素 ( (無前驅無前驅) ) 根結點根結點 ( (無前驅無前驅) )最后一個數據元素最后一個數據元素 (無后繼無后繼)多個葉子結點多個葉子結點 ( (無后繼無后繼) )其它數據元素其它數據元素( (一個前驅、一個前驅、 一個后繼一個后繼) )其它數據元素其它數據元素( (一個前驅、一個前驅、 多個后繼多個后繼) )6.1 6.1 樹的定義和基本概念樹的定義和基本概念6.2 6.2 二叉樹二叉樹6.3 6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹6.4 6.4 樹和森林樹和森林6.6 6.6 哈夫曼樹及其應用哈夫曼樹及其應用 第六章第六章 樹和二叉樹樹和二叉

10、樹6.2 6.2 二叉樹二叉樹6.2.1 二叉樹的定義二叉樹的定義6.2.2 二叉樹的性質二叉樹的性質6.2.3 二叉樹的存儲結構二叉樹的存儲結構6.2 6.2 二叉樹二叉樹6.2.1 二叉樹的定義二叉樹的定義v定義：二叉樹是定義：二叉樹是n(n 0)個結點的有限集，它或個結點的有限集，它或為為空樹空樹(n=0)，或由一個根結點和兩棵分別稱為或由一個根結點和兩棵分別稱為左子樹左子樹和和右子樹右子樹的的互不相交的互不相交的二叉樹構成二叉樹構成。v特點特點l每個結點至多有二棵子樹每個結點至多有二棵子樹l二叉樹的子樹有左、右之分，且其次序不能二叉樹的子樹有左、右之分，且其次序不能任意顛倒任意顛倒v基

11、本形態基本形態A只有根結點只有根結點的二叉樹的二叉樹 空二叉樹空二叉樹AB右子樹為空右子樹為空AB左子樹為空左子樹為空ABC左、右子樹左、右子樹均非空均非空查查 找找 類類插插 入入 類類刪刪 除除 類類 Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit(); InOrderTraverse(T, Visit()

12、; PostOrderTraverse(T, Visit(); LevelOrderTraverse(T, Visit();查找類：查找類：InitBiTree(&T);Assign(T, &e, value);CreateBiTree(&T, definition);InsertChild(T, p, LR, c); 插入類：插入類：ClearBiTree(&T); DestroyBiTree(&T);DeleteChild(T, p, LR);刪除類：刪除類：6.2.2 二叉樹的性質二叉樹的性質v性質性質1：在二叉樹的第：在二叉樹的第i層上至多有層上

13、至多有2i-1個節點個節點(i1)證明：用歸納法證明之證明：用歸納法證明之 i=1時，只有一個根結點，時，只有一個根結點， 是對的是對的。 假設對所有假設對所有j(1 ji)命題成立，即第命題成立，即第j層上至層上至多有多有 個結點個結點, 那么，第那么，第i-1層至多有層至多有 個結點個結點 又二叉樹每個結點的度至多為又二叉樹每個結點的度至多為2 第第i層上最大結點數是第層上最大結點數是第i-1層的層的2倍，即倍，即 故命題得證故命題得證12201i12j22i12222ii6.2.2 二叉樹的性質二叉樹的性質v性質性質2：深度為：深度為k的二叉樹至多有的二叉樹至多有 個結點個結點(k 1)

14、12 k證明：由性質證明：由性質1，可得深度為，可得深度為k 的二叉樹最大結點的二叉樹最大結點數是數是122)(111kkikiii層的最大結點數第v性質性質3：對任何一棵二叉樹：對任何一棵二叉樹T，如果其終端結點數為，如果其終端結點數為n0，度為，度為2的結點數為的結點數為n2，則，則n0=n2+1證明：證明：n1為二叉樹為二叉樹T中度為中度為1的結點數的結點數 因為：二叉樹中所有結點的度均小于或等于因為：二叉樹中所有結點的度均小于或等于2 所以：其結點總數所以：其結點總數n=n0+n1+n2 又二叉樹中，除根結點外，其余結點都只有一個又二叉樹中，除根結點外，其余結點都只有一個 分支進入分支

15、進入 設設B為分支總數，則為分支總數，則n=B+1 又：分支由度為又：分支由度為1和度為和度為2的結點射出，的結點射出， B=n1+2n2 于是，于是，n=B+1=n1+2n2+1=n0+n1+n2 n0=n2+1幾種特殊形式的二叉樹幾種特殊形式的二叉樹v滿二叉樹滿二叉樹l定義：定義：12個結點的二叉樹稱為且有一棵深度為kkl特點：每一層上的結點數都是最大結點數特點：每一層上的結點數都是最大結點數v完全二叉樹完全二叉樹l定義：深度為定義：深度為k，有，有n個結點的二叉樹當且僅當個結點的二叉樹當且僅當其每一個結點都與深度為其每一個結點都與深度為k的滿二叉樹中的滿二叉樹中編號從編號從1至至n的結點

16、一一對應的結點一一對應時，稱為時，稱為l特點特點u葉子結點只可能在層次最大的兩層上出現葉子結點只可能在層次最大的兩層上出現u對任一結點，若其右分支下子孫的最大層次對任一結點，若其右分支下子孫的最大層次為為l，則其左分支下子孫的最大層次必為，則其左分支下子孫的最大層次必為l 或或l+11231145891213671014151231145891267101234567123456性質性質4：證明：假設深度為證明：假設深度為k，則根據性質，則根據性質2和完全二和完全二叉樹的定義有叉樹的定義有 2 k-1-1n=2k-1或或2 k-1=n2k 于是于是k-1=log2n1，則其，則其雙親雙親是是

17、i/2 (2) 如果如果2in，則結點，則結點i無左孩子；如果無左孩子；如果2i n，則其，則其左左孩子是孩子是2i (3) 如果如果2i+1n，則結點，則結點i無右孩子；如果無右孩子；如果2i+1 n，則，則其其右孩子是右孩子是2i+1 i/2ii+12i2i+12(i+1)2i+3i+12(i+1)2i+3i2i2i+1圖圖6.11 6.11 完全二叉樹中結點完全二叉樹中結點i i和和i+1i+1(a)i(a)i和和i+1i+1結點在同一層結點在同一層 (b)i(b)i和和i+1i+1結點不在同一層結點不在同一層如圖如圖6.116.11所示為完全二叉樹上結點及其所示為完全二叉樹上結點及其左

18、右好在結點之間的關系。左右好在結點之間的關系。證明：證明： 可以從可以從(2)(2)和和(3)(3)推出推出(1)(1)，先證明，先證明(2)(2)和和(3)(3)。 科學歸納法：科學歸納法： 對于對于i i1 1，其左孩子是結點，其左孩子是結點2 2，若，若2n2n，即不存在，即不存在結點結點2 2，此時，結點，此時，結點i i無孩子。結點無孩子。結點i i的右孩子是結點的右孩子是結點3 3，若結點若結點3 3不存在，即不存在，即3n3n，此時結點，此時結點i i無右孩子。無右孩子。即即i=1,i=1,結論成立。結論成立。 對于對于i1i1，可分為兩種情況：，可分為兩種情況： (1)(1)設

19、第設第j j層的層的第一個結點第一個結點的編號為的編號為i i，由二叉樹的，由二叉樹的性質性質2 2和定義知和定義知i i2 2j-1j-1 結點結點i i的左孩子的左孩子必定為的必定為的j j1 1層的第一個結點，其層的第一個結點，其編號為編號為2 2j j2 22 2j-1j-12i2i。如果。如果2 2i inn，則無左孩子。，則無左孩子。 結點結點i i右孩子右孩子必定為第必定為第j j1 1層的第二個結點，編號層的第二個結點，編號為為2i2i1 1。若。若2i+1n2i+1n，則無右孩子。，則無右孩子。 (2)(2)假設第假設第j j層上的某個結點編號為層上的某個結點編號為i i(2

20、(2j-1j-1=i=2=i=2j j- -1),1),且且2i2i1n11時，如果時，如果i為左孩子，即為左孩子，即2(i/2)=i，則，則i/2是是i的雙親；如果的雙親；如果i為右孩子，為右孩子，i2p+1，i的雙親應為的雙親應為p， p(i1)/2=i/2. 證畢證畢。6.2.3 二叉樹的存儲結構二叉樹的存儲結構二、二叉樹的鏈式存儲表示二、二叉樹的鏈式存儲表示一、一、 二叉樹的順序存儲表示二叉樹的順序存儲表示#define MAX_TREE_SIZE 100 / 二叉樹的最大結點數二叉樹的最大結點數typedef TElemType SqBiTreeMAX_TREE_SIZE; / 0號

21、單元存儲根結點號單元存儲根結點SqBiTree bt;一、一、 二叉樹的順序存儲表示二叉樹的順序存儲表示二叉樹的存儲結構二叉樹的存儲結構v順序存儲結構順序存儲結構l實現：按滿二叉樹的結點層次編號，依次存放實現：按滿二叉樹的結點層次編號，依次存放二叉樹中的數據元素二叉樹中的數據元素l特點：特點：u結點間關系蘊含在其存儲位置中結點間關系蘊含在其存儲位置中u浪費空間，適于存滿二叉樹和完全二叉樹浪費空間，適于存滿二叉樹和完全二叉樹 (比如深度為比如深度為k的右單支樹，需要的右單支樹，需要2k-1個結點，有效結點為個結點，有效結點為k)abcdefga b c d e 0 0 0 0 f g 1 2 3

22、 4 5 6 7 8 9 10 11二、二叉樹的鏈式存儲表示二、二叉樹的鏈式存儲表示1. 1. 二叉鏈表二叉鏈表2三叉鏈表三叉鏈表3 3雙親鏈表雙親鏈表4線索鏈表線索鏈表ADEBCF rootlchild data rchild結點結構結點結構:1. 1. 二叉鏈表二叉鏈表v鏈式存儲結構鏈式存儲結構l二叉鏈表二叉鏈表typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode , *BiTree;lchild data rchild ABCDEFG性質性質6：在在n個結點的二叉鏈表中，有個結點的二

23、叉鏈表中，有n+1個空指針域個空指針域 AB C D E F GADEBCF root 2三叉鏈表三叉鏈表parent lchild data rchild結點結構結點結構:l三叉鏈表三叉鏈表typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild, *parent; BiTNode , *BiTree;lchild data parent rchildABCDEFG A B C D E F G0123456B2C0A -1D2E3F4 data parent結點結構結點結構:3 3雙親鏈表雙親鏈表LRTagL

24、RRRLABCDFE typedef struct BPTNode / 結點結構結點結構 TElemType data; int *parent; / 指向雙親的指針指向雙親的指針 char LRTag; / 左、右孩子標志域左、右孩子標志域 BPTNode typedef struct BPTree / 樹結構樹結構 BPTNode nodesMAX_TREE_SIZE; int num_node; / 結點數目結點數目 int root; / 根結點的位置根結點的位置 BPTree6.1 6.1 樹的定義和基本概念樹的定義和基本概念6.2 6.2 二叉樹二叉樹6.3 6.3 遍歷二叉樹和線

25、索二叉樹遍歷二叉樹和線索二叉樹6.4 6.4 樹和森林樹和森林6.6 6.6 哈夫曼樹及其應用哈夫曼樹及其應用 第六章第六章 樹和二叉樹樹和二叉樹6.3.1 遍歷二叉樹遍歷二叉樹問題的提出問題的提出先序遍歷先序遍歷中序遍歷中序遍歷后序遍歷后序遍歷中序遍歷的非遞歸算法中序遍歷的非遞歸算法遍歷算法的應用舉例遍歷算法的應用舉例6.3.2 線索二叉樹線索二叉樹何謂線索二叉樹？何謂線索二叉樹？線索鏈表的遍歷算法線索鏈表的遍歷算法如何建立線索鏈表如何建立線索鏈表6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹遍歷二叉樹是指按遍歷二叉樹是指按一定的規律一定的規律對二叉樹中的每個結對二叉樹中的每個結點點均

26、被訪問一次均被訪問一次，而且，而且僅被訪問一次僅被訪問一次。 “訪問訪問”的含義可以很廣，如：輸出結點的信息或的含義可以很廣，如：輸出結點的信息或判定節點滿足某些條件等。判定節點滿足某些條件等。“遍歷遍歷”是任何類型均有的操作，對線性結構而言是任何類型均有的操作，對線性結構而言，只有一條搜索路徑，只有一條搜索路徑( (因為每個結點均只有一個后繼因為每個結點均只有一個后繼) )，故不需要另加討論。而二叉樹是樹型結構，故不需要另加討論。而二叉樹是樹型結構，每個結每個結點有兩個后繼點有兩個后繼，則，則存在如何遍歷存在如何遍歷，即按什么樣的，即按什么樣的搜索搜索路徑路徑遍歷的問題。遍歷的問題。一、問題

27、的提出（一、問題的提出（尋找某個結點尋找某個結點）6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹 對對“二叉樹二叉樹”而言，可以有三條搜索路徑：而言，可以有三條搜索路徑：1 1先上后下先上后下的按層次遍歷；的按層次遍歷；2 2先左先左（子樹）（子樹）后右后右（子樹）的遍歷；（子樹）的遍歷；3 3先右先右（子樹）（子樹）后左后左（子樹）的遍歷。（子樹）的遍歷。先左后右的遍歷算法先左后右的遍歷算法(左子樹總是先于右子樹左子樹總是先于右子樹)DLRLDR、LRD、DLRRDL、RLD、DRLv方法方法l先序先序(根根)遍歷：遍歷：(1)訪問訪問根結點根結點；(2)先序遍歷左子樹；先序遍歷左子樹

28、；(3)先序遍歷右子樹；先序遍歷右子樹；l中序中序(根根)遍歷：遍歷：(1)中序遍歷左子樹；中序遍歷左子樹；(2)訪問訪問根結點根結點；(3)中序遍歷右子樹；中序遍歷右子樹；l后序后序(根根)遍歷：遍歷：(1)后序遍歷左子樹后序遍歷左子樹; (2)后序遍歷右子樹；后序遍歷右子樹；(3)訪問訪問根結點根結點;l按層次遍歷：從上到下、從左到右訪問各結點按層次遍歷：從上到下、從左到右訪問各結點ADBCD L RAD L RD L RBDCD L R先序遍歷序列：先序遍歷序列：A B D C先序遍歷先序遍歷:ADBCL D RBL D RL D RADCL D R中序遍歷序列：中序遍歷序列：B D A

29、 C中序遍歷中序遍歷: :ADBC L R DL R DL R DADCL R D后序遍歷序列：后序遍歷序列： D B C A后序遍歷后序遍歷:B-+/a*b-efcd先序遍歷：先序遍歷：中序遍歷：中序遍歷：后序遍歷：后序遍歷：層次遍歷：層次遍歷：- - + + a a * * b b - - c c d d / / e e f f- -+ +a a* *b b- -c cd d/ /e ef f- -+ + a a* *b b- -c cd d/ /e ef f- -+ +a a* *b b- -c c d d/ /e e f f主程序主程序Pre( T )返回返回返回返回返回返回返回返回A

30、CBDTBvisit(B);pre(T L);BTAvisit(A);pre(T L);ATDvisit(D);pre(T L);DTCvisit(C);pre(T L);C返回返回T左是空返回左是空返回pre(T R);T左是空返回左是空返回T右是空返回右是空返回T左是空返回左是空返回T右是空返回右是空返回pre(T R);先序序列：先序序列：A B D Cstatus PreOrderTraversal(BiTree T ) if(T) visit(T-data); PreOrderTraversal(T-lchild); PreOrderTraversal(T-rchild); retu

31、rn OK; v算法：遞歸算法算法：遞歸算法先序遍歷先序遍歷:pre(T R);pre(T R);status InOrderTraversal(BiTree T ) if(T) InOrderTraversal(T-lchild); visit(T-data); InOrderTraversal(T-rchild); return OK; status PostOrderTraversal(BiTree T ) if(T) PostOrderTraversal(T-lchild); PostOrderTraversal(T-rchild); visit(T-data); return OK;

32、 中序遍歷中序遍歷:后序遍歷后序遍歷:l非遞歸算法非遞歸算法(中序中序)ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(2)ABCDEFGpiP-AP-BP-C(3)p=NULLABCDEFGiP-AP-B訪問：訪問：C(4)pABCDEFGiP-A訪問：訪問：C B(5)ABCDEFGiP-AP-D訪問：訪問：C Bp(6)ABCDEFGiP-AP-DP-E訪問：訪問：C Bp(7)ABCDEFGiP-AP-D訪問：訪問：C B Ep(8)ABCDEFGiP-AP-DP-G訪問：訪問：C B EP=NULL(9)ABCDEFGiP-A訪問：訪問：C B E G Dp(11)AB

33、CDEFGiP-AP-F訪問：訪問：C B E G Dp(12)ABCDEFGiP-AP-D訪問：訪問：C B E Gp(10)ABCDEFGiP-A訪問：訪問：C B E G D Fp=NULL(13)ABCDEFGi訪問：訪問：C B E G D F Ap(14)ABCDEFGi訪問：訪問：C B E G D F Ap=NULL(15)思考：思考：訪問的第一個結點的特點訪問的第一個結點的特點 前序，后序棧的操前序，后序棧的操 作作 層次遍歷？層次遍歷？四、中序遍歷算法的非遞歸描述四、中序遍歷算法的非遞歸描述Status InOrderTraverse(BiTree T, Status(*

34、Visit)(TElemType e) InitStack(S); Push(S,T) /根指針進棧根指針進棧 while (!StackEmpt(S) while(GetTop(S,p)& p) Push(S,p-lchild); Pop(S,p); /空指針退棧空指針退棧 if (!StackEmpty(S) Pop(S,p); if(!Visit(p-data) return ERROR; Push(S, p-rchild); /if /while return OK; /InOrderTraverse四、中序遍歷算法的非遞歸描述四、中序遍歷算法的非遞歸描述BiTNode *Go

35、FarLeft(BiTree T,Stack *S) / T為樹根結點的指針為樹根結點的指針 if (!T ) return NULL; while (T-lchild ) Push(S, T); T = T-lchild; return T; /得到樹得到樹T最左葉子結點的指針最左葉子結點的指針void InorderTree(BiTree T, void (*visit) (TelemType& e) Stack *S; BiTree t,p; p=T-lchild; t = GoFarLeft(p, S); / / 找到最左下的結點找到最左下的結點 while(t) visit(

36、t-data); if (t-rchild) t = GoFarLeft(t-rchild, S); else if ( !StackEmpty(S ) /棧不空時退棧棧不空時退棧 t = Pop(S); else t = NULL; /棧空表明遍歷結束棧空表明遍歷結束 / while / InorderTree 說明：說明：由一棵給定的二叉樹可以獲得三種遍歷序列，由一棵給定的二叉樹可以獲得三種遍歷序列，同樣，也可以由這些遍歷序列來重新構造二同樣，也可以由這些遍歷序列來重新構造二叉樹。叉樹。單用一個遍歷序列是無法構造二叉樹的，因單用一個遍歷序列是無法構造二叉樹的，因為無法從遍歷序列中區分二叉樹

37、的左、右子為無法從遍歷序列中區分二叉樹的左、右子樹。樹。利用中序遍歷序列，并結合先序遍歷序列或利用中序遍歷序列，并結合先序遍歷序列或后序遍歷序列就能重新構造二叉樹后序遍歷序列就能重新構造二叉樹。 本章實驗內容本章實驗內容 編寫一個程序，輸入先序遍歷序列和中序編寫一個程序，輸入先序遍歷序列和中序遍歷序列遍歷序列 ，由先序遍歷和中序遍歷序列，由先序遍歷和中序遍歷序列構造出構造出一棵二叉樹一棵二叉樹，然后用，然后用后序遍歷后序遍歷輸出該二叉樹。輸出該二叉樹。先序遍歷序列和中序遍歷序列的結點分布特點：先序遍歷序列和中序遍歷序列的結點分布特點：先序遍歷序列：先序遍歷序列： 中序遍歷序列：中序遍歷序列：

38、二叉樹的構造步驟：二叉樹的構造步驟： 1 1）從先序遍歷序列中取出第一個結點從先序遍歷序列中取出第一個結點，該結，該結點一定是二叉樹的點一定是二叉樹的根根。然后在。然后在中序遍歷序列中序遍歷序列中中找到根結點，根結點前面的結點序列就是找到根結點，根結點前面的結點序列就是左子左子樹樹的中序遍歷序列，根結點后面的結點序列就的中序遍歷序列，根結點后面的結點序列就是是右子樹右子樹的中序遍歷序列。的中序遍歷序列。 2 2）對根的左子樹先序遍歷序列和中序遍歷序）對根的左子樹先序遍歷序列和中序遍歷序列及右子樹的先序遍歷序列和中序遍歷序列，列及右子樹的先序遍歷序列和中序遍歷序列，再再執行第一步執行第一步，直到

39、得出所有葉子結點為止。，直到得出所有葉子結點為止。 a b c d e f gc b d a e g f例如例如: :aab bccddeeffggabcdefg先序序列中序序列main() 輸入先序序列輸入先序序列=preod 輸入中序序列輸入中序序列=inod PreInOd(preod,1,n,inod,1,n,&root);void PreInOd(char preod, int i, int j, char inod, int k,int h,BiTree *t) 申請結點空間申請結點空間=t; t-data=preodi; 查找查找t-data在在inod中的位置中的位置=

40、m if (m=k) t-lchild=Null; else PreInOd(preod, i+1,i+m-k,inod,k,m-1,&(t-lchild); /遞歸建立左子樹遞歸建立左子樹 if (m=h) t-rchild=NULL; else PreInOd(preod,i+m-k+1,j inod,m+1,h &(t-rchild);練習 如圖所示二叉樹的中序遍歷序列是如圖所示二叉樹的中序遍歷序列是（ ）。）。 A AabcdgefabcdgefB Bdfebagcdfebagc C Cdbaefcgdbaefcg D Ddefbagcdefbagc練習1)已知一棵二叉

41、樹的先根序列為已知一棵二叉樹的先根序列為ABDGCFK，中，中根序列為根序列為DGBAFCK，則結點的后根序列為，則結點的后根序列為（ ）。）。 AACFKDBGBGDBFKCACKCFAGDBDABCDFKG 2)已知某二叉樹的后序遍歷序列是已知某二叉樹的后序遍歷序列是dabec，中，中序遍歷序列是序遍歷序列是debac，它的前序遍歷序列是，它的前序遍歷序列是（ ）。）。AacbedBdecab CdeabcDcedba利用中序遍歷序列，并結合先序遍歷序列或后利用中序遍歷序列，并結合先序遍歷序列或后序遍歷序列重新構造二叉樹。序遍歷序列重新構造二叉樹。 例一例一 先序：先序：ABCDEFGHI

42、J 中序：中序：CBDEAFHIGJ 例二例二 中序：中序：ABCDJEFHGI 后序：后序：BCJDAHIGFE 練習練習五五、遍歷算法的應用舉例遍歷算法的應用舉例2 2、統計二叉樹中葉子結點的個數、統計二叉樹中葉子結點的個數( (先序遍歷先序遍歷) )3 3、求二叉樹的深度、求二叉樹的深度( (后序遍歷后序遍歷) )1 1、按先序遍歷序列建立二叉樹的二叉鏈表、按先序遍歷序列建立二叉樹的二叉鏈表 以字符串的形式以字符串的形式 根根 左子樹左子樹 右子樹右子樹定義一棵二叉樹定義一棵二叉樹例如例如: :ABCD以空白字符以空白字符“ ”“ ”表示表示A(B( ,C( , ),D( , )空樹空樹

43、只含一個根結點只含一個根結點的二叉樹的二叉樹A以字符串以字符串“A ” ”表示表示以下列字符串表示以下列字符串表示遍歷算法應用遍歷算法應用按先序遍歷序列建立二叉樹的二叉鏈表，已知先序序列為：按先序遍歷序列建立二叉樹的二叉鏈表，已知先序序列為： A B C D E G F ABCDEFG A B C D E F G status CreateBitree(BiTree&T) scanf(&ch); if(ch= |ch=n) T=NULL; else if(!(T=(BiTnode*)malloc(sizeof(BiTnode) exit(overflow); T-data=ch

44、; CreateBitree(T-lchild); CreateBitree(T-rchild); return OK; A B C D A BCD上頁算法執行過程舉例如下：上頁算法執行過程舉例如下：ATBCD2 2、統計二叉樹中葉子結點的個數、統計二叉樹中葉子結點的個數算法基本思想算法基本思想: : 先序先序( (或中序或后序或中序或后序) )遍歷二叉樹，在遍歷遍歷二叉樹，在遍歷過程中查找葉子結點，并計數。過程中查找葉子結點，并計數。需在遍歷算法中增添一個需在遍歷算法中增添一個“計數計數”的參數，的參數，并將算法中并將算法中“訪問結點訪問結點”的操作改為：若是的操作改為：若是葉子，則計數器增

45、葉子，則計數器增1 1。void CountLeaf (BiTree T, int& count) if ( T ) if (!T-lchild)& (!T-rchild) count+; / 對葉子結點計數對葉子結點計數 CountLeaf( T-lchild, count); CountLeaf( T-rchild, count); / if / CountLeaf統計二叉樹中葉子結點個數算法統計二叉樹中葉子結點個數算法ABCDEFGint BitreeLeafCount(BiTree T) if (T=NULL) return 0; else if (T-lchild=N

46、ULL &T-rchild=NULL) return 1; else return BitreeLeafCount(T-lchild)+ BitreeLeafCount(T-rchild); ABCDEFGl統計二叉樹中結點個數算法統計二叉樹中結點個數算法int BitreeCount(BiTree T) if (T=NULL) return 0; else return BitreeCount(T-lchild)+ BitreeCount(T-rchild)+ 1; l求二叉樹深度算法求二叉樹深度算法int BitreeDepth(BiTree T) if (T=NULL) dept

47、h=0; else ldepth=BitreeDepth(T-lchild); rdepth=BitreeDepth(T-rchild); depth=1+(ldepthrdepth?ldepth:rdepth); return depth; ABCDEFG線索二叉樹線索二叉樹 何謂線索二叉樹？何謂線索二叉樹？ 線索鏈表的遍歷算法線索鏈表的遍歷算法 如何建立線索鏈表？如何建立線索鏈表？一、一、何謂線索二叉樹？何謂線索二叉樹？遍歷二叉樹的結果是，求得結點的一個遍歷二叉樹的結果是，求得結點的一個線線性序列性序列。ABCDEFGHK例如例如: :先序序列先序序列: : A B C D E F G H

48、 K中序序列中序序列: : B D C A H G K F E后序序列后序序列: : D C B H K G F E A指向該線性序列中的指向該線性序列中的“前驅前驅”和和 “后繼后繼” 的指針，稱作的指針，稱作“線索線索”與其相應的二叉樹，稱與其相應的二叉樹，稱作作 “線索二叉樹線索二叉樹”包含包含 “線索線索” 的存儲結構，的存儲結構，稱作稱作 “線索鏈表線索鏈表”A B C D E F G H K D C B E 對對線索鏈表線索鏈表中結點的約定：中結點的約定： 在二叉鏈表的結點中在二叉鏈表的結點中增加兩個標志域增加兩個標志域：若該結點的左子樹不空，若該結點的左子樹不空，則則Lchild

49、域的指針指向其左子樹，且左標志域的指針指向其左子樹，且左標志域的值為域的值為“指針指針 Link”； 否則，否則，Lchild域的指針指向其域的指針指向其“前驅前驅”，且，且左標志的值為左標志的值為“線索線索 Thread” . lchild Ltag data Rtag rchild 若該結點的右子樹不空，若該結點的右子樹不空，則則rchild域的指針指向其右子樹，且右標志域域的指針指向其右子樹，且右標志域的值為的值為 “指針指針 Link”；否則，否則，rchild域的指針指向其域的指針指向其“后繼后繼”，且右，且右標志的值為標志的值為“線索線索 Thread”。 如此定義的二叉樹的存儲結

50、構稱作如此定義的二叉樹的存儲結構稱作“線索鏈線索鏈表表”。typedef struct BiThrNod TElemType data; struct BiThrNode *lchild, *rchild; / 左右指針左右指針 PointerThr LTag, RTag; / 左右標志左右標志 BiThrNode, *BiThrTree;線索鏈表線索鏈表的類型描述：的類型描述： typedef enum PointerTag Link, Thread ; / Link=0:指針，指針，Thread=1:線索線索 lchild Ltag data Rtag rchild ABCDE A B D

51、 C ET00001111 11typedef struct BiThrNode TElemType data; struct BiThrNode *lchild, *rchild; PointTag Ltag , Rtag; BiThrNode ,*BiThrTree; lchild Ltag data Rtag rchild 結點定義：結點定義：Typedef enum PointerTag Link, Thread ;先序序列：先序序列：ABCDE先序線索二叉樹先序線索二叉樹ABCDE A B D C ET0000111111中序序列：中序序列：BCAED中序線索二叉樹中序線索二叉樹AB

52、CDE A B D C ET0000111111后序序列：后序序列：CBEDA后序線索二叉樹后序線索二叉樹二、線索鏈表的遍歷算法二、線索鏈表的遍歷算法 for ( p = firstNode(T); p; p = Succ(p) ) Visit (p);由于在線索鏈表中添加了遍歷中得到的由于在線索鏈表中添加了遍歷中得到的“前前驅驅”和和“后繼后繼”的信息，從而簡化了遍歷的的信息，從而簡化了遍歷的算法。算法。例如例如: 對中序線索化鏈表的遍歷算法對中序線索化鏈表的遍歷算法 中序遍歷的第一個結點中序遍歷的第一個結點 ？ 在中序線索化鏈表中結點的后繼在中序線索化鏈表中結點的后繼 ？左子樹上處于左子樹

53、上處于“最左下最左下”（沒有左子樹）的（沒有左子樹）的結點。結點。若若無右子樹，無右子樹，則為則為后繼線索所指結點；后繼線索所指結點；否則為否則為對其右子樹進行中序遍歷時訪問對其右子樹進行中序遍歷時訪問的第一個結點。的第一個結點。void InOrderTraverse_Thr(BiThrTree T, void (*Visit)(TElemType e) p = T-lchild; / p指向根結點指向根結點 while (p != T) / 空樹或遍歷結束時，空樹或遍歷結束時，p=T while (p-LTag=Link) p = p-lchild; / 第一個結點第一個結點 while

54、(p-RTag=Thread & p-rchild!=T) p = p-rchild; Visit(p-data); / 訪問后繼結點訪問后繼結點 p = p-rchild; / p進至其右子樹根進至其右子樹根 / InOrderTraverse_Thr在中序遍歷過程中修改結點的左、右指在中序遍歷過程中修改結點的左、右指針域，以保存當前訪問結點的針域，以保存當前訪問結點的“前驅前驅”和和“后繼后繼”信息。信息。遍歷過程中，附設指針遍歷過程中，附設指針pre, 并始終保持并始終保持指針指針pre指向當前訪問的、指針指向當前訪問的、指針p所指結點所指結點的的前驅前驅。三、如何建立線索鏈表？

55、三、如何建立線索鏈表？void InThreading(BiThrTree p) if (p) / 對以對以p為根的非空二叉樹進行線索化為根的非空二叉樹進行線索化 InThreading(p-lchild); / 左子樹線索化左子樹線索化 if (!p-lchild) / 建前驅線索建前驅線索 p-LTag = Thread; p-lchild = pre; if (!pre-rchild) / 建后繼線索建后繼線索 pre-RTag = Thread; pre-rchild = p; pre = p; / 保持保持 pre 指向指向 p 的前驅的前驅 InThreading(p-rchild

56、); / 右子樹線索化右子樹線索化 / if / InThreadingStatus InOrderThreading(BiThrTree &Thrt, BiThrTree T) / 構建中序線索鏈表構建中序線索鏈表 if (!(Thrt = (BiThrTree)malloc( sizeof( BiThrNode) exit (OVERFLOW); Thrt-LTag = Link; Thrt-RTag =Thread; Thrt-rchild = Thrt; / 添加頭結點添加頭結點 return OK; / InOrderThreading if (!T) Thrt-lchild

57、 = Thrt; else Thrt-lchild = T; pre = Thrt; InThreading(T); pre-rchild = Thrt; / 處理最后一個結點處理最后一個結點 pre-RTag = Thread; Thrt-rchild = pre; 6.1 6.1 樹的定義和基本概念樹的定義和基本概念6.2 6.2 二叉樹二叉樹6.3 6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹6.4 6.4 樹和森林樹和森林6.6 6.6 哈夫曼樹及其應用哈夫曼樹及其應用 第六章第六章 樹和二叉樹樹和二叉樹6.4 樹和森林樹和森林 6.4.1 樹的存儲結構樹的存儲結構 6.4.2

58、 森林與二叉樹的轉換森林與二叉樹的轉換 6.4.3 樹和森林的遍歷樹和森林的遍歷6.4.1 樹的三種存儲結構樹的三種存儲結構一、雙親表示法一、雙親表示法二、孩子鏈表表示法二、孩子鏈表表示法三、樹的二叉鏈表三、樹的二叉鏈表(孩子孩子-兄弟）存儲表示法兄弟）存儲表示法ABCDEFG0 A -11 B 02 C 03 D 04 E 2 5 F 26 G 5r=0n=6data parent一、雙親表示法一、雙親表示法 typedef struct PTNode Elem data; int parent; / 雙親位置域雙親位置域 PTNode; data parent#define MAX_TRE

59、E_SIZE 100結點結構結點結構:C語言的類型描述語言的類型描述:typedef struct PTNode nodes MAX_TREE_SIZE; int r, n; / 根結點的位置和結點個數根結點的位置和結點個數 PTree;樹結構樹結構:abcdefhgi6012345789acdefghibdata fc 2 3 4 5 9 7 8 6如何找雙親結點如何找雙親結點l孩子鏈表：每個結點的孩子結點用孩子鏈表：每個結點的孩子結點用單鏈表存儲單鏈表存儲，再，再用含用含n n個元素的個元素的結構數組結構數組指向每個孩子鏈表指向每個孩子鏈表二、孩子鏈表表示法二、孩子鏈表表示法l帶雙親的孩子

60、鏈表帶雙親的孩子鏈表612345789acdefghibdatafc 2 3 4 5 9 7 8 6012235551parentabcdefhgitypedef struct CTNode int child; struct CTNode *next; *ChildPtr;孩子結點結構孩子結點結構: child nextC C語言的類型描述語言的類型描述: : typedef struct Elem data; ChildPtr firstchild; / 孩子鏈的頭指針 CTBox;雙親結點結構雙親結點結構 data firstchildtypedef struct CTBox nodesMAX_TREE_SIZE; int n, r; / 結點數和根結點的位置 CTree;樹結構樹結構:三、孩子兄弟表示法三、孩子兄弟表示法(二叉樹表示法二叉樹表示法)l實現：用二叉