數(shù)據(jù)結(jié)構(gòu)樹(shù)_二叉樹(shù)的定義和二叉樹(shù)性質(zhì)與存儲(chǔ)本

1、第六章 樹(shù)和二叉樹(shù)（一）6.1 樹(shù)的類型定義樹(shù)的類型定義6.2 二叉樹(shù)的類型定義二叉樹(shù)的類型定義6.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)6.4 二叉樹(shù)的遍歷二叉樹(shù)的遍歷6.5 線索二叉樹(shù)線索二叉樹(shù)6.6 樹(shù)和森林的表示方法樹(shù)和森林的表示方法6.7 樹(shù)和森林的遍歷樹(shù)和森林的遍歷6.8 哈夫曼樹(shù)與哈夫曼編碼哈夫曼樹(shù)與哈夫曼編碼數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。 若若D為空集，則稱為空樹(shù)為空集，則稱為空樹(shù) 。 否則否則: (1) 在在D中存在唯一的稱為根的數(shù)據(jù)元素中存在唯一的稱為根的數(shù)據(jù)元素root； (2) 當(dāng)當(dāng)n1時(shí)，其余結(jié)點(diǎn)可分為時(shí)，其余結(jié)點(diǎn)

2、可分為m (m0)個(gè)互個(gè)互 不相交的有限集不相交的有限集T1, T2, , Tm，其中，其中每一每一 棵子集本身又是一棵符合本定義的樹(shù)，棵子集本身又是一棵符合本定義的樹(shù)， 稱為根稱為根root的子樹(shù)。的子樹(shù)。 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R：樹(shù)的類型定義樹(shù)的類型定義 基本操作：基本操作：查查 找找 類類 插插 入入 類類刪刪 除除 類類 Root(T) / 求樹(shù)的根結(jié)點(diǎn)求樹(shù)的根結(jié)點(diǎn) 查找類：查找類：Value(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)的元素值求當(dāng)前結(jié)點(diǎn)的元素值 Parent(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)求當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)LeftChild(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)的最

3、左孩子求當(dāng)前結(jié)點(diǎn)的最左孩子 RightSibling(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)的右兄弟求當(dāng)前結(jié)點(diǎn)的右兄弟TreeEmpty(T) / 判定樹(shù)是否為空樹(shù)判定樹(shù)是否為空樹(shù) TreeDepth(T) / 求樹(shù)的深度求樹(shù)的深度TraverseTree( T, Visit() ) / 遍歷遍歷InitTree(&T) / 初始化置空樹(shù)初始化置空樹(shù) 插入類：插入類：CreateTree(&T, definition) / 按定義構(gòu)造樹(shù)按定義構(gòu)造樹(shù)Assign(&T, cur_e, value) / 給當(dāng)前結(jié)點(diǎn)賦值給當(dāng)前結(jié)點(diǎn)賦值InsertChild(&T, &am

4、p;p, i, c) / 將以將以c為根的樹(shù)插入為結(jié)點(diǎn)為根的樹(shù)插入為結(jié)點(diǎn)p的第的第i棵子樹(shù)棵子樹(shù) ClearTree(&T) / 將樹(shù)清空將樹(shù)清空 刪除類：刪除類：DestroyTree(&T) / 銷毀樹(shù)的結(jié)構(gòu)銷毀樹(shù)的結(jié)構(gòu)DeleteChild(&T, &p, i) / 刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)p的第的第i棵子樹(shù)棵子樹(shù)基基 本本 術(shù)術(shù) 語(yǔ)語(yǔ)樹(shù)（Tree)：是n個(gè)結(jié)點(diǎn)的有限集（n=0)。在任意一棵非空樹(shù)中，有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)（root) ；當(dāng)n1時(shí)，其余結(jié)點(diǎn)可分為m（m0)個(gè)互不相交的有限集T1,T2,Tm,其中每個(gè)集合Ti本身又是一棵符合本定義的樹(shù)，并且稱

5、為根root的子樹(shù)。ABCDEFGHIJMKLA( B(E, F(K, L), C(G), D(H, I, J(M) )T1T3T2樹(shù)根例如例如: :1 1、結(jié)點(diǎn)、結(jié)點(diǎn): :2 2、結(jié)點(diǎn)的度、結(jié)點(diǎn)的度: :3 3、樹(shù)的度、樹(shù)的度: :4 4、葉子結(jié)點(diǎn)、葉子結(jié)點(diǎn): :5 5、分支結(jié)點(diǎn)、分支結(jié)點(diǎn): :數(shù)據(jù)元素+ +若干指向子樹(shù)的分支分支的個(gè)數(shù)樹(shù)中所有結(jié)點(diǎn)的度的最大值度為零的結(jié)點(diǎn)度大于零的結(jié)點(diǎn)DHIJM（終端結(jié)點(diǎn)）（終端結(jié)點(diǎn)）（非終端結(jié)點(diǎn)）（非終端結(jié)點(diǎn)）6、(從根到結(jié)點(diǎn)的)路徑：路徑：7、孩子孩子結(jié)點(diǎn)、雙親雙親結(jié)點(diǎn)兄弟兄弟結(jié)點(diǎn)、堂兄弟堂兄弟結(jié)點(diǎn)祖先祖先結(jié)點(diǎn)、子孫子孫結(jié)點(diǎn)8、結(jié)點(diǎn)的層次結(jié)點(diǎn)的層次: :

6、9、樹(shù)的深度：樹(shù)的深度： 由從根根到該結(jié)點(diǎn)所經(jīng)分支和結(jié)點(diǎn)構(gòu)成ABCDEFGHIJMKL假設(shè)根結(jié)點(diǎn)的層次為1，依次加1樹(shù)中葉子結(jié)點(diǎn)所在的最大層次樹(shù)的示意圖：根結(jié)點(diǎn)葉子結(jié)點(diǎn)分支結(jié)點(diǎn)子樹(shù)子樹(shù)子樹(shù)Level 1Level 2Level 3Level 4結(jié)點(diǎn)的層次任何一棵非空樹(shù)是一個(gè)二元組 Tree = （root，F(xiàn)）其中：root 被稱為根結(jié)點(diǎn) F 被稱為子樹(shù)森林10、森林：、森林：是m（m0）棵互不相交的樹(shù)的集合。ArootBCDEFGHIJMKLF( () ) 有確定的根；有確定的根；( () ) 樹(shù)根和子樹(shù)根之間為有向關(guān)系。樹(shù)根和子樹(shù)根之間為有向關(guān)系。有向樹(shù)：有向樹(shù)：有序樹(shù)：有序樹(shù)：樹(shù)中結(jié)點(diǎn)的

7、各子樹(shù)之間的先后次序是有意義的，不能互換，樹(shù)中結(jié)點(diǎn)的各子樹(shù)之間的先后次序是有意義的，不能互換，否則就成為另一棵樹(shù)了。子樹(shù)之間存在確定的否則就成為另一棵樹(shù)了。子樹(shù)之間存在確定的次序次序關(guān)系。關(guān)系。無(wú)序樹(shù)：無(wú)序樹(shù)：樹(shù)中結(jié)點(diǎn)的各子樹(shù)之間的先后次序無(wú)意義，可樹(shù)中結(jié)點(diǎn)的各子樹(shù)之間的先后次序無(wú)意義，可以互換。子樹(shù)之間不存在確定的次序關(guān)系。以互換。子樹(shù)之間不存在確定的次序關(guān)系。二叉樹(shù)的類型定義二叉樹(shù)的類型定義二叉樹(shù)是樹(shù)的基礎(chǔ)，一般的樹(shù)可以二叉樹(shù)是樹(shù)的基礎(chǔ)，一般的樹(shù)可以轉(zhuǎn)化為二叉樹(shù)來(lái)處理。轉(zhuǎn)化為二叉樹(shù)來(lái)處理。1、二叉樹(shù)的定義二叉樹(shù)的定義： 二叉樹(shù)或?yàn)榭諛?shù)空樹(shù)，或是由一個(gè)根結(jié)點(diǎn)根結(jié)點(diǎn)加上兩棵兩棵分別稱為左子樹(shù)左

8、子樹(shù)和右子樹(shù)的、互不相交的互不相交的二叉樹(shù)二叉樹(shù)組成（即左、右子樹(shù)次序不能顛倒）。ABCDEFGHK根結(jié)點(diǎn)左子樹(shù)右子樹(shù)2 2、二叉樹(shù)的五種基本形態(tài)：、二叉樹(shù)的五種基本形態(tài)：N空樹(shù)空樹(shù)只含根結(jié)點(diǎn)只含根結(jié)點(diǎn)NNNLRR右子樹(shù)為空樹(shù)右子樹(shù)為空樹(shù)L左子樹(shù)為空樹(shù)左子樹(shù)為空樹(shù)左右子左右子樹(shù)均不樹(shù)均不為空樹(shù)為空樹(shù) 二叉樹(shù)的主要基本操作二叉樹(shù)的主要基本操作：查查 找找 類類插插 入入 類類刪刪 除除 類類 Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(

9、T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit(); InOrderTraverse(T, Visit(); PostOrderTraverse(T, Visit(); LevelOrderTraverse(T, Visit(); InitBiTree(&T); Assign(&T, &e, value); CreateBiTree(&T, definition); InsertChild(&T, p, LR, c);ClearBiTree(&T); Destroy

10、BiTree(&T);DeleteChild(&T, p, LR);二叉樹(shù)的重要特性二叉樹(shù)的重要特性 性質(zhì)性質(zhì)1 ：在二叉樹(shù)的第在二叉樹(shù)的第i層上至多有層上至多有2i-1 個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。 (i1)用歸納法證明用歸納法證明： 歸納基歸納基： 歸納假設(shè)：歸納假設(shè)： 歸納證明：歸納證明：i = 1 層時(shí)，只有一個(gè)根結(jié)點(diǎn)： 2i-1 = 20 = 1；假設(shè)對(duì)所有的 j，1 j i，命題成立；由歸納假設(shè)知：第i-1層上至多有2i-2個(gè)結(jié)點(diǎn)。又因?yàn)槎鏄?shù)上每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)，則第 i 層的結(jié)點(diǎn)數(shù) = 2i-2 2 = 2i-1 。性質(zhì)性質(zhì)2 ： 深度為深度為i的二叉樹(shù)上至多有的二叉樹(shù)

11、上至多有2i-1個(gè)結(jié)點(diǎn)（個(gè)結(jié)點(diǎn)（i1）。）。證明：證明： 基于上一條性質(zhì)，深度為 i 的二叉樹(shù)上的結(jié)點(diǎn)數(shù)至多為 20+21+ +2i-1 = 2i-1 。 性質(zhì)性質(zhì)3 ： 對(duì)任何一棵二叉樹(shù)，若它含有對(duì)任何一棵二叉樹(shù)，若它含有n0 個(gè)葉子結(jié)點(diǎn)、個(gè)葉子結(jié)點(diǎn)、n2 個(gè)個(gè)度為度為 2 的結(jié)點(diǎn)，則必存在關(guān)系式：的結(jié)點(diǎn)，則必存在關(guān)系式：n0 = n2+1。證明：證明：設(shè)設(shè) 二叉樹(shù)上結(jié)點(diǎn)總數(shù) n = n0 + n1 + n2又又 二叉樹(shù)上分支總數(shù) b = n0 *0+n1+2n2 而 b = n-1 = n0 + n1 + n2 - 1由此，由此， n0 = n2 + 1 。兩類兩類特殊形態(tài)特殊形態(tài)的二叉樹(shù)

12、：的二叉樹(shù)：滿二叉樹(shù)滿二叉樹(shù)：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)。完全二叉樹(shù)完全二叉樹(shù)：樹(shù)中所含的 n 個(gè)結(jié)點(diǎn)和滿二叉樹(shù)中編號(hào)編號(hào)為為 1 至至 n 的結(jié)點(diǎn)的結(jié)點(diǎn)一一對(duì)應(yīng)。123456789 10 11 12 13 14 15abcdefghij 性質(zhì)性質(zhì)4 ： 具有具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為為 log2n +1 。證明證明：設(shè)設(shè)完全二叉樹(shù)的深度為 k ，則由性質(zhì)2和完全二叉樹(shù)的定義知：深度為k-1的二叉樹(shù)應(yīng)該是一棵滿二叉樹(shù)，故結(jié)點(diǎn)數(shù)為2k-1-1；深度為k的完全二叉樹(shù)當(dāng)為滿二叉樹(shù)時(shí)結(jié)點(diǎn)數(shù)最多為2k 1。所以得 2k-1-1 n 2k 1 2k-1 n 2

13、k 即 k-1 log2 n n，則該結(jié)點(diǎn)無(wú)左孩子， 否則，編號(hào)為 2i 的結(jié)點(diǎn)為其左孩子左孩子結(jié)點(diǎn)；(3) 若 2i+1n，則該結(jié)點(diǎn)無(wú)右孩子結(jié)點(diǎn)， 否則，編號(hào)為2i+1 的結(jié)點(diǎn)為其右孩子右孩子結(jié)點(diǎn)。6.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二、二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)表示二、二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)表示一、一、 二叉樹(shù)的順序存儲(chǔ)表示二叉樹(shù)的順序存儲(chǔ)表示（適合存儲(chǔ)（適合存儲(chǔ)完全二叉樹(shù)）即用一組地址連續(xù)的存儲(chǔ)單元依次即用一組地址連續(xù)的存儲(chǔ)單元依次從上至下從上至下，從，從左至左至右右存儲(chǔ)完全二叉樹(shù)上的結(jié)點(diǎn)元素。也就是說(shuō)，將完全存儲(chǔ)完全二叉樹(shù)上的結(jié)點(diǎn)元素。也就是說(shuō)，將完全二叉樹(shù)上編號(hào)為二叉樹(shù)上編號(hào)為i的結(jié)點(diǎn)存放在數(shù)組

14、下標(biāo)為（的結(jié)點(diǎn)存放在數(shù)組下標(biāo)為（i-1)的分的分量中。量中。若要存儲(chǔ)一棵一般的二叉樹(shù)，結(jié)點(diǎn)的存放應(yīng)與完全二若要存儲(chǔ)一棵一般的二叉樹(shù)，結(jié)點(diǎn)的存放應(yīng)與完全二叉樹(shù)上的結(jié)點(diǎn)對(duì)照，存儲(chǔ)在數(shù)組的相應(yīng)分量中。用叉樹(shù)上的結(jié)點(diǎn)對(duì)照，存儲(chǔ)在數(shù)組的相應(yīng)分量中。用“0”表示不存在該結(jié)點(diǎn)。可能會(huì)浪費(fèi)很多存儲(chǔ)空間，表示不存在該結(jié)點(diǎn)?？赡軙?huì)浪費(fèi)很多存儲(chǔ)空間，單支樹(shù)單支樹(shù)就是一個(gè)就是一個(gè)極端極端情況。情況。一、一、 二叉樹(shù)的順序存儲(chǔ)表示二叉樹(shù)的順序存儲(chǔ)表示完全二叉樹(shù)的數(shù)組表示完全二叉樹(shù)的數(shù)組表示 一般二叉樹(shù)的數(shù)組表示一般二叉樹(shù)的數(shù)組表示數(shù)組表示數(shù)組表示順序存儲(chǔ)的C語(yǔ)言描述#define MAX_TREE_SIZE 100 /

15、 二叉樹(shù)的最大結(jié)點(diǎn)數(shù)typedef TElemType SqBiTreeMAX_TREE_SIZE; / 0號(hào)單元存儲(chǔ)根結(jié)點(diǎn)ADEBCF rootlchild data rchild結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu)1. 1. 二叉鏈表二叉鏈表二、二、 二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)表示二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)表示二叉鏈表的C語(yǔ)言描述typedef struct BiTNode / 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu) TElemType data; struct BiTNode *lchild, *rchild; /左右孩子指針 BiTNode, *BiTree;lchild data rchild結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):ADEBCF root 2 2三叉鏈表三叉鏈表parent lchild data rchil