第06章 樹和二叉樹

1、第六章第六章 樹和二叉樹樹和二叉樹數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu): 線性結(jié)構(gòu)線性結(jié)構(gòu)(線性表線性表, 棧棧,隊(duì)列等隊(duì)列等) 非線性結(jié)構(gòu)非線性結(jié)構(gòu): 至少存在一個(gè)數(shù)據(jù)元素有不至少存在一個(gè)數(shù)據(jù)元素有不止一個(gè)直接前驅(qū)或后繼止一個(gè)直接前驅(qū)或后繼(樹樹,圖等圖等)第六章第六章 樹和二叉樹樹和二叉樹6.1 6.1 樹的定義樹的定義 樹是樹是n n個(gè)數(shù)據(jù)元素的有限集個(gè)數(shù)據(jù)元素的有限集( (記為記為T)T)，對(duì)，對(duì)任意一棵樹任意一棵樹T T有：有： 存在唯一一個(gè)稱為存在唯一一個(gè)稱為根根 的數(shù)據(jù)元素；的數(shù)據(jù)元素； 當(dāng)當(dāng)n n1 1時(shí)，其它數(shù)據(jù)元素可分為時(shí)，其它數(shù)據(jù)元素可分為m(mm(m0) 0) 個(gè)互不相交的有限集個(gè)互不相交

2、的有限集T T1 1,T,T2 2,T,Tm m，其中每個(gè)，其中每個(gè)集合集合T Ti i(i=1,2,(i=1,2,m),m)本身又是一棵樹，并稱本身又是一棵樹，并稱樹樹 T Ti i是根的是根的子樹子樹. .第六章第六章 樹和二叉樹樹和二叉樹樹的表示法樹的表示法1. 1. 分支圖表示法分支圖表示法2. 2. 嵌套集合表示法嵌套集合表示法3. 廣義表表示法(A(B(D),C)第六章第六章 樹和二叉樹樹和二叉樹樹的基本術(shù)語(yǔ)樹的基本術(shù)語(yǔ)1. 1. 樹的結(jié)點(diǎn)樹的結(jié)點(diǎn): :包含一個(gè)包含一個(gè)DEDE和指向其子樹的所有分支和指向其子樹的所有分支; ;2. 2. 結(jié)點(diǎn)的度結(jié)點(diǎn)的度: :一個(gè)結(jié)點(diǎn)擁有的子樹的個(gè)

3、數(shù)一個(gè)結(jié)點(diǎn)擁有的子樹的個(gè)數(shù), ,度為零度為零的結(jié)點(diǎn)稱為的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)葉結(jié)點(diǎn); ;3. 3. 樹的度樹的度: :樹中所有結(jié)點(diǎn)的度的最大值樹中所有結(jié)點(diǎn)的度的最大值Max(D(I)Max(D(I) 含義含義: :樹中最大分支數(shù)為樹的度樹中最大分支數(shù)為樹的度; ;4. 4. 結(jié)點(diǎn)的層次及樹的深度結(jié)點(diǎn)的層次及樹的深度: :根為第一層根為第一層, ,根的孩子根的孩子為第二層為第二層, ,若某結(jié)點(diǎn)為第若某結(jié)點(diǎn)為第k k層層, ,則其孩子為則其孩子為k+1k+1層層. . 樹中結(jié)點(diǎn)的最大層次稱為樹的深度或高度樹中結(jié)點(diǎn)的最大層次稱為樹的深度或高度5.5.森林森林: :是是m(m=0)m(m=0)棵互不相的樹的

4、集合棵互不相的樹的集合 森林與樹概念相近森林與樹概念相近, ,相互很容易轉(zhuǎn)換相互很容易轉(zhuǎn)換. .第六章第六章 樹和二叉樹樹和二叉樹6.2 6.2 樹的基本運(yùn)算樹的基本運(yùn)算 初始化操作初始化操作INITIATE(T)INITIATE(T)：創(chuàng)建一棵空樹。：創(chuàng)建一棵空樹。 求根函數(shù)求根函數(shù)ROOT(T)ROOT(T)：求樹：求樹T T的根；的根；ROOT(X)ROOT(X)：求：求結(jié)點(diǎn)結(jié)點(diǎn)x x所在樹的根。所在樹的根。 求雙親函數(shù)求雙親函數(shù)PARENT(T,x)PARENT(T,x)：在樹：在樹T T中求中求x x的雙親。的雙親。 求第求第i i個(gè)孩子函數(shù)個(gè)孩子函數(shù)CHILD(T,x,i)CHIL

5、D(T,x,i)：在樹：在樹T T中求結(jié)中求結(jié)點(diǎn)點(diǎn)x x的第的第i i個(gè)孩子。個(gè)孩子。 求兄弟函數(shù)：在求兄弟函數(shù)：在T T中求中求x x的左兄弟的左兄弟LSIBLING(T,x)LSIBLING(T,x)；在樹在樹T T中求中求x x的右兄弟的右兄弟RSIBLING(T,x)RSIBLING(T,x)。第六章第六章 樹和二叉樹樹和二叉樹 建樹函數(shù)建樹函數(shù)CRT-TREE(x,F)CRT-TREE(x,F)：建立以結(jié)點(diǎn)：建立以結(jié)點(diǎn)x x為根，為根，森林森林F F為子樹的樹。為子樹的樹。 插入子樹操作插入子樹操作INS-CHILD(y,i,x)INS-CHILD(y,i,x)：將：將x x作為作為

6、y y的的第第i i根子樹。根子樹。 刪除子樹操作刪除子樹操作DEL-CHILD(x,i)DEL-CHILD(x,i)：刪除：刪除x x的第的第i i棵棵子樹。子樹。 遍歷樹操作遍歷樹操作TRAVERSE(T)TRAVERSE(T)：按順序訪問樹：按順序訪問樹T T中各中各個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。 置空樹操作置空樹操作CLEAR(T)CLEAR(T)：將樹：將樹T T置為空樹。置為空樹。第六章第六章 樹和二叉樹樹和二叉樹6.3 6.3 二叉樹概念及性質(zhì)二叉樹概念及性質(zhì)一一. . 二叉樹概念二叉樹概念 二叉樹是結(jié)點(diǎn)數(shù)為二叉樹是結(jié)點(diǎn)數(shù)為0 0或每個(gè)結(jié)點(diǎn)最多只有或每個(gè)結(jié)點(diǎn)最多只有左右兩棵子樹的樹。二叉樹是一

7、種特殊的樹，左右兩棵子樹的樹。二叉樹是一種特殊的樹，它的特點(diǎn)是：它的特點(diǎn)是：每個(gè)結(jié)點(diǎn)最多只有兩棵子樹，即不存結(jié)點(diǎn)每個(gè)結(jié)點(diǎn)最多只有兩棵子樹，即不存結(jié)點(diǎn)度大于度大于2 2的結(jié)點(diǎn)；的結(jié)點(diǎn)；子樹有左右之分，不能顛倒。子樹有左右之分，不能顛倒。6.3 二叉樹二叉樹二二. . 二叉樹性質(zhì)二叉樹性質(zhì)性質(zhì)性質(zhì)1.1. 在二叉樹的第在二叉樹的第i i層上至多有層上至多有2 2i-1i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)( (i1)i1)。性質(zhì)性質(zhì)2.2. 深度為深度為k k的二叉樹至多有的二叉樹至多有2 2k k-1-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)( (k)k)。（深度一定，二叉樹的最大結(jié)點(diǎn)數(shù)也確定）（深度一定，二叉樹的最大結(jié)點(diǎn)數(shù)也確定）性質(zhì)性質(zhì)

8、3.3. 二叉樹中二叉樹中, ,終端結(jié)點(diǎn)數(shù)終端結(jié)點(diǎn)數(shù)n n0 0與度為與度為2 2的結(jié)點(diǎn)數(shù)的結(jié)點(diǎn)數(shù)n n2 2有如下關(guān)系有如下關(guān)系: : n n0=0=n n2 2+1+16.3 二叉樹二叉樹滿二叉樹滿二叉樹: :深度為深度為k k，且有，且有2 2k k-1-1個(gè)結(jié)點(diǎn)的二叉樹。個(gè)結(jié)點(diǎn)的二叉樹。特點(diǎn)：（特點(diǎn)：（1 1）每一層上結(jié)點(diǎn)數(shù)都達(dá)到最大）每一層上結(jié)點(diǎn)數(shù)都達(dá)到最大 （2 2）度為）度為1 1的結(jié)點(diǎn)的結(jié)點(diǎn)n n1 1=0=0 結(jié)點(diǎn)層序編號(hào)方法：從根結(jié)點(diǎn)起從上到下逐層結(jié)點(diǎn)層序編號(hào)方法：從根結(jié)點(diǎn)起從上到下逐層（層內(nèi)從左到右）對(duì)二叉樹的結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)。（層內(nèi)從左到右）對(duì)二叉樹的結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)。

9、1237654K=3n=23-1=7 滿二叉樹 6.3 二叉樹二叉樹完全二叉樹完全二叉樹: :深度為深度為k k，結(jié)點(diǎn)數(shù)為，結(jié)點(diǎn)數(shù)為n n的二叉樹，當(dāng)?shù)亩鏄?，?dāng)且僅當(dāng)每個(gè)結(jié)點(diǎn)的編號(hào)都與相同深度的滿二叉樹且僅當(dāng)每個(gè)結(jié)點(diǎn)的編號(hào)都與相同深度的滿二叉樹中從中從1 1到到n n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為完全二叉樹。的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為完全二叉樹。452136.3 二叉樹二叉樹完全二叉樹的特點(diǎn)完全二叉樹的特點(diǎn): :（1 1）每個(gè)結(jié)點(diǎn)）每個(gè)結(jié)點(diǎn)i i的左子樹的深度的左子樹的深度LhLhi i- -其結(jié)點(diǎn)其結(jié)點(diǎn)i i的右的右子樹的深度子樹的深度RhRhi i等于等于0 0或或1 1，即葉結(jié)點(diǎn)只可能出現(xiàn)在，即葉

10、結(jié)點(diǎn)只可能出現(xiàn)在層次最大或次最大的兩層上。層次最大或次最大的兩層上。（2 2）完全二叉樹結(jié)點(diǎn)數(shù)）完全二叉樹結(jié)點(diǎn)數(shù)n n滿足滿足2 2k-1k-1-1-1n2n2k k-1 -1 （3 3）滿二叉樹一定是完全二叉樹，反之不成立。）滿二叉樹一定是完全二叉樹，反之不成立。452136.3 二叉樹二叉樹LHLH2 2=0=0RHRH2 2=1=11324653241LH1=3RH1=1LH1 -RH1=2 非完全二叉樹非完全二叉樹 非完全二叉樹非完全二叉樹LH2-RH2=0-1=-16.3 二叉樹二叉樹性質(zhì)性質(zhì)4.4. 結(jié)點(diǎn)數(shù)為結(jié)點(diǎn)數(shù)為n n的完全二叉樹，其深度為的完全二叉樹，其深度為 loglog2

11、 2n n + 1+ 16.3 二叉樹二叉樹性質(zhì)性質(zhì)5.5. 在按層序編號(hào)的在按層序編號(hào)的n n個(gè)結(jié)點(diǎn)的完全二叉樹中，個(gè)結(jié)點(diǎn)的完全二叉樹中，任意一結(jié)點(diǎn)任意一結(jié)點(diǎn)i(1in)i(1in)有：有： i=1 i=1時(shí)，結(jié)點(diǎn)時(shí)，結(jié)點(diǎn)i i是樹的根；否則是樹的根；否則(i1)(i1)，結(jié)點(diǎn)，結(jié)點(diǎn)i i的的雙親為結(jié)點(diǎn)雙親為結(jié)點(diǎn)i/2i/2。 2i 2in n時(shí)，結(jié)點(diǎn)時(shí)，結(jié)點(diǎn)i i無(wú)左孩子，為葉結(jié)點(diǎn)；否則，無(wú)左孩子，為葉結(jié)點(diǎn)；否則，結(jié)點(diǎn)結(jié)點(diǎn)i i的左孩子為結(jié)點(diǎn)的左孩子為結(jié)點(diǎn)2 2i i。 2i+1 2i+1n n時(shí)，結(jié)點(diǎn)時(shí)，結(jié)點(diǎn)i i無(wú)右孩子；否則，結(jié)點(diǎn)無(wú)右孩子；否則，結(jié)點(diǎn)i i的的右孩子為結(jié)點(diǎn)右孩子為結(jié)點(diǎn)

12、2 2i+1i+1。6.3 二叉樹二叉樹 完全二叉樹完全二叉樹DCGFEBA三、二叉樹的存儲(chǔ)結(jié)構(gòu)三、二叉樹的存儲(chǔ)結(jié)構(gòu) 順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu) 用一組地址連續(xù)的存儲(chǔ)單元，以層序順序存放二叉樹用一組地址連續(xù)的存儲(chǔ)單元，以層序順序存放二叉樹的數(shù)據(jù)元素，的數(shù)據(jù)元素， 結(jié)點(diǎn)的相對(duì)位置蘊(yùn)含著結(jié)點(diǎn)之間的關(guān)系。結(jié)點(diǎn)的相對(duì)位置蘊(yùn)含著結(jié)點(diǎn)之間的關(guān)系。 bt3的雙親為的雙親為3/23/2=1， 即在即在b t1中；中； 其左孩子在其左孩子在bt2i=bt6中；中； 其右孩子在其右孩子在bt2i+1=bt7中。中。1 2 3 4 5 6 7 8 9 10 11 A B C D E F G 0 0 0 06.3 二叉

13、樹二叉樹 這種存儲(chǔ)結(jié)構(gòu)適合于完全二叉樹，既不浪費(fèi)存這種存儲(chǔ)結(jié)構(gòu)適合于完全二叉樹，既不浪費(fèi)存儲(chǔ)空間，又能很快確定結(jié)點(diǎn)的存放位置、以及結(jié)點(diǎn)儲(chǔ)空間，又能很快確定結(jié)點(diǎn)的存放位置、以及結(jié)點(diǎn)的雙親和左右孩子的存放位置，但對(duì)一般二叉樹，的雙親和左右孩子的存放位置，但對(duì)一般二叉樹，可能造成存儲(chǔ)空間的浪費(fèi)?？赡茉斐纱鎯?chǔ)空間的浪費(fèi)。D 二叉樹CGFEBA1 2 3 4 5 6 7 8 9 10 11 A B C D E 0 0 0 0 F G 0 0 0 0 一般二叉樹也按完全二叉樹形式存儲(chǔ),沒結(jié)點(diǎn)處用0表示。6.3 二叉樹二叉樹例如，深度為例如，深度為k k，且只有，且只有k k個(gè)結(jié)點(diǎn)的右單枝樹個(gè)結(jié)點(diǎn)的右單枝樹

14、(每個(gè)每個(gè)非葉結(jié)點(diǎn)只有右孩子非葉結(jié)點(diǎn)只有右孩子) )，需，需2 2k k-1-1個(gè)單元，即有個(gè)單元，即有2 2k k-1-k-1-k個(gè)單元被浪費(fèi)。個(gè)單元被浪費(fèi)。1k6.3 二叉樹二叉樹 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 設(shè)計(jì)不同的結(jié)點(diǎn)結(jié)構(gòu)，可以構(gòu)成不同的鏈?zhǔn)酱嬖O(shè)計(jì)不同的結(jié)點(diǎn)結(jié)構(gòu)，可以構(gòu)成不同的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。常用的有：儲(chǔ)結(jié)構(gòu)。常用的有： 二叉鏈表二叉鏈表 三叉鏈表三叉鏈表 線索鏈表線索鏈表 用空鏈域存放指向前驅(qū)或后繼的線索用空鏈域存放指向前驅(qū)或后繼的線索 6.3 二叉樹二叉樹二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu) lchild data rchildD 二叉樹二叉樹CEBAACBDE二叉鏈表二叉鏈表6.3

15、 二叉樹二叉樹 三叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)三叉鏈表的結(jié)點(diǎn)結(jié)構(gòu) lchild data parent rchildD 二叉樹二叉樹CEBAACBDE三叉鏈表三叉鏈表6.3 二叉樹二叉樹性質(zhì)性質(zhì)6.6. 含有含有n n個(gè)結(jié)點(diǎn)的二叉鏈表中，有個(gè)結(jié)點(diǎn)的二叉鏈表中，有n+1n+1個(gè)空鏈域。個(gè)空鏈域。6.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹一、遍歷二叉樹一、遍歷二叉樹 遍歷二叉樹是指遍歷二叉樹是指按一定的規(guī)律按一定的規(guī)律對(duì)二叉樹的每個(gè)結(jié)對(duì)二叉樹的每個(gè)結(jié)點(diǎn)，點(diǎn)，訪問訪問且僅訪問一次的處理過(guò)程。且僅訪問一次的處理過(guò)程。 訪問訪問是一種抽象操作，是對(duì)結(jié)點(diǎn)的某種處理，例如是一種抽象操作，是對(duì)結(jié)點(diǎn)的某種處理，例

16、如可以是求結(jié)點(diǎn)的度、或?qū)哟?、打印結(jié)點(diǎn)的信息，或做可以是求結(jié)點(diǎn)的度、或?qū)哟巍⒋蛴〗Y(jié)點(diǎn)的信息，或做其他任何工作。其他任何工作。 一次遍歷后，使樹中結(jié)點(diǎn)的非線性排列，按訪問的一次遍歷后，使樹中結(jié)點(diǎn)的非線性排列，按訪問的先后順序變?yōu)槟撤N線性排列。先后順序變?yōu)槟撤N線性排列。 遍歷的次序遍歷的次序：若設(shè)二叉樹根為：若設(shè)二叉樹根為D D，左子樹為，左子樹為L(zhǎng) L，右子，右子樹為樹為R R，并限定先左后右，則有以下三種遍歷次序：，并限定先左后右，則有以下三種遍歷次序：LDR LDR 中序遍歷中序遍歷；LRD LRD 后序遍歷后序遍歷；DLR DLR 先序遍歷先序遍歷6.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線

17、索二叉樹1.1.中序遍歷二叉樹中序遍歷二叉樹算法思想算法思想: : 若二叉樹非空，則：若二叉樹非空，則：1）中序遍歷左子樹）中序遍歷左子樹2）訪問根結(jié)點(diǎn)）訪問根結(jié)點(diǎn)3）中序遍歷右子樹）中序遍歷右子樹算法描述算法描述:PROC inorder (bt：bitreptr)；bt為BT根結(jié)點(diǎn)指針I(yè)F btNIL THEN inorder (btlchild) ; visit (bt data)； inorder (btrchild) ; ENDP; inorder6.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹2.2.后序遍歷二叉樹后序遍歷二叉樹算法思想算法思想: : 若二叉樹非空，則：若二叉樹

18、非空，則：1）后序遍歷左子樹）后序遍歷左子樹2）后序遍歷右子樹）后序遍歷右子樹3）訪問根結(jié)點(diǎn)）訪問根結(jié)點(diǎn)算法描述算法描述:PROC postorder (bt：bitreptr)；bt為BT根結(jié)點(diǎn)指針I(yè)F btNIL THEN postorder (btlchild) ; postorder (btrchild) ; visit (bt data)； ENDP; postorder6.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹3.3.先序遍歷二叉樹先序遍歷二叉樹算法思想算法思想: : 若二叉樹非空，則：若二叉樹非空，則：1）訪問根結(jié)點(diǎn)）訪問根結(jié)點(diǎn)2) 先序遍歷左子樹先序遍歷左子樹3）先序

19、遍歷右子樹）先序遍歷右子樹算法描述算法描述:PROC preorder (bt：bitreptr)；bt為為BT根結(jié)點(diǎn)指針根結(jié)點(diǎn)指針I(yè)F btNIL THEN visit (btdata)； preorder (btlchild) ; preorder (btrchild) ; ENDP; preorder6.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹例：表達(dá)式例：表達(dá)式a+b (c-d)-e/facdefb+遍歷結(jié)果遍歷結(jié)果:中序中序: a+b c d e /f后序后序: abcd +ef / 先序先序: +a b cd /ef6.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹三種遍

20、歷過(guò)程示意圖例三種遍歷過(guò)程示意圖例 acbab*c-ba*-cab*c-abc 虛線表示執(zhí)行過(guò)程虛線表示執(zhí)行過(guò)程: 向下表示更深層的遞歸調(diào)用向下表示更深層的遞歸調(diào)用; 向上表示遞歸調(diào)用返回向上表示遞歸調(diào)用返回; 沿虛線記下各類符號(hào)沿虛線記下各類符號(hào),便得到遍歷的結(jié)果便得到遍歷的結(jié)果.6.4 遍歷二叉樹和遍歷二叉樹和線索二叉樹線索二叉樹PROCPROC inorder(bt:bitreptr)；中序遍歷非遞歸算法中序遍歷非遞歸算法,s,s為存儲(chǔ)二叉樹結(jié)點(diǎn)指針棧為存儲(chǔ)二叉樹結(jié)點(diǎn)指針棧 INISTACK(s)； push(s,bt)； WHILEWHILE NOT EMPTY(s) DODO WHI

21、LEWHILE GETTOP(s)NIL DODO PUSH(s,GETTOP(s).lchild)； p:=POP(s)； IFIF NOT EMPTY(s) THENTHEN visit(GETTOP(s).data)； p:=POP(s)； PUSH(s, p.rchild)ENDPENDP；inorder 根結(jié)點(diǎn)先進(jìn)棧，根結(jié)點(diǎn)先進(jìn)棧， 左結(jié)點(diǎn)緊跟根后面左結(jié)點(diǎn)緊跟根后面進(jìn)棧進(jìn)棧,右結(jié)點(diǎn)在根右結(jié)點(diǎn)在根出棧后入棧出棧后入棧 每個(gè)結(jié)點(diǎn)都要進(jìn)每個(gè)結(jié)點(diǎn)都要進(jìn)一次和出一次棧，一次和出一次棧， 并且總是訪問棧頂并且總是訪問棧頂元素，元素， 因此，因此， 算算法正確，法正確， 時(shí)間復(fù)時(shí)間復(fù)雜度為雜度為

22、O(n)。6.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹二、線索二叉樹二、線索二叉樹 問題的提出問題的提出：通過(guò)遍歷二叉樹可得到結(jié)點(diǎn)：通過(guò)遍歷二叉樹可得到結(jié)點(diǎn)的一個(gè)線性序列，在線性序列中，就存在結(jié)點(diǎn)的一個(gè)線性序列，在線性序列中，就存在結(jié)點(diǎn)和前驅(qū)和后繼，但是在二叉樹上只能找到結(jié)點(diǎn)和前驅(qū)和后繼，但是在二叉樹上只能找到結(jié)點(diǎn)的左孩子、右孩子，結(jié)點(diǎn)的前驅(qū)和后繼只有在的左孩子、右孩子，結(jié)點(diǎn)的前驅(qū)和后繼只有在遍歷過(guò)程中才能得到，那么，能否通過(guò)結(jié)點(diǎn)的遍歷過(guò)程中才能得到，那么，能否通過(guò)結(jié)點(diǎn)的兩個(gè)鏈域查找出任一結(jié)點(diǎn)的前驅(qū)和后繼兩個(gè)鏈域查找出任一結(jié)點(diǎn)的前驅(qū)和后繼? ?6.4 遍歷二叉樹和線索二叉樹遍歷二叉樹和

23、線索二叉樹2. 2. 分析分析： n n個(gè)結(jié)點(diǎn)有個(gè)結(jié)點(diǎn)有n-1n-1個(gè)前驅(qū)和個(gè)前驅(qū)和n-1n-1個(gè)后繼；個(gè)后繼； 一共有一共有2n2n個(gè)鏈域，其中：個(gè)鏈域，其中：n+1n+1個(gè)空鏈域，個(gè)空鏈域，n-1n-1個(gè)指針域；個(gè)指針域； 因此因此, , 必須用空鏈域來(lái)存放結(jié)點(diǎn)的前驅(qū)必須用空鏈域來(lái)存放結(jié)點(diǎn)的前驅(qū)和后繼。線索二叉樹就是利用和后繼。線索二叉樹就是利用n+1n+1個(gè)空鏈域個(gè)空鏈域來(lái)存放結(jié)點(diǎn)的前驅(qū)和后繼結(jié)點(diǎn)的信息。來(lái)存放結(jié)點(diǎn)的前驅(qū)和后繼結(jié)點(diǎn)的信息。6.4 遍歷二叉樹和遍歷二叉樹和線索二叉樹線索二叉樹3. 3. 線索二叉樹線索二叉樹： 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu)在二叉鏈表中增加在二叉鏈表中增加 ltag lt

24、ag 和和 rtag rtag 兩個(gè)標(biāo)志域兩個(gè)標(biāo)志域 lchild ltag data rtag rchild 若結(jié)點(diǎn)有左子樹，則左鏈域若結(jié)點(diǎn)有左子樹，則左鏈域lchildlchild指示其左孩子指示其左孩子（ltag=0ltag=0）；否則，令左鏈域指示其前驅(qū)（）；否則，令左鏈域指示其前驅(qū)（ltag=1ltag=1）；）； 若結(jié)點(diǎn)有右子樹，則右鏈域若結(jié)點(diǎn)有右子樹，則右鏈域rchildrchild指示其右孩子指示其右孩子（rtag=0rtag=0）；否則，令右鏈域指示其后繼（）；否則，令右鏈域指示其后繼（rtag=1rtag=1）；）；6.4 遍歷二叉樹和遍歷二叉樹和線索二叉樹線索二叉樹 稱這

25、種結(jié)點(diǎn)結(jié)構(gòu)為稱這種結(jié)點(diǎn)結(jié)構(gòu)為線索鏈表線索鏈表； 其中指示前驅(qū)和后繼的鏈域稱為其中指示前驅(qū)和后繼的鏈域稱為線索線索； 加上線索的二叉樹稱為加上線索的二叉樹稱為線索二叉樹線索二叉樹； 對(duì)二叉樹以對(duì)二叉樹以某種次序某種次序遍歷使其變?yōu)榫€索二叉樹遍歷使其變?yōu)榫€索二叉樹的過(guò)程稱為的過(guò)程稱為線索化線索化。 按中序遍歷得到的線索二叉樹稱為按中序遍歷得到的線索二叉樹稱為中序線索二中序線索二叉樹叉樹；按先序遍歷得到的線索二叉樹稱為；按先序遍歷得到的線索二叉樹稱為先序線先序線索二叉樹索二叉樹；按后序遍歷得到的線索二叉樹稱為；按后序遍歷得到的線索二叉樹稱為后后序線索二叉樹序線索二叉樹；6.4 遍歷二叉樹和遍歷二叉樹

26、和線索二叉樹線索二叉樹（2 2）整體結(jié)構(gòu)）整體結(jié)構(gòu) 增設(shè)一個(gè)頭結(jié)點(diǎn)，令其增設(shè)一個(gè)頭結(jié)點(diǎn)，令其lchildlchild指向二叉樹的根指向二叉樹的根結(jié)點(diǎn)，結(jié)點(diǎn)，ltag=0ltag=0、rtag=1rtag=1； 并將該結(jié)點(diǎn)作為遍歷訪問的第一個(gè)結(jié)點(diǎn)的前驅(qū)并將該結(jié)點(diǎn)作為遍歷訪問的第一個(gè)結(jié)點(diǎn)的前驅(qū)和最后一個(gè)結(jié)點(diǎn)的后繼；和最后一個(gè)結(jié)點(diǎn)的后繼； 最后用頭指針指示該頭結(jié)點(diǎn)。最后用頭指針指示該頭結(jié)點(diǎn)。acb0 10 01 c 10 01 b 11 a 16.4 遍歷二叉樹和遍歷二叉樹和線索二叉樹線索二叉樹4. 4. 遍歷線索二叉樹遍歷線索二叉樹： 有了線索二叉樹，就容易遍歷二叉樹了有了線索二叉樹，就容易遍歷二

27、叉樹了只要只要（）先找要遍歷的第一個(gè)結(jié)點(diǎn)；（）先找要遍歷的第一個(gè)結(jié)點(diǎn)；（）然后依次找結(jié)點(diǎn)的后繼；（）然后依次找結(jié)點(diǎn)的后繼；（）重復(fù)（）直到其后繼為頭結(jié)點(diǎn)（）重復(fù)（）直到其后繼為頭結(jié)點(diǎn) 所有問題歸為如何在線索二叉樹中找結(jié)所有問題歸為如何在線索二叉樹中找結(jié)點(diǎn)的后繼？點(diǎn)的后繼？6.4 遍歷二叉樹和遍歷二叉樹和線索二叉樹線索二叉樹1 1）遍歷中序線索二叉樹）遍歷中序線索二叉樹（1 1）中序線索二叉樹中，找結(jié)點(diǎn)的后繼算法）中序線索二叉樹中，找結(jié)點(diǎn)的后繼算法算法思想算法思想: : 對(duì)任意結(jié)點(diǎn)對(duì)任意結(jié)點(diǎn)p p，若，若rtag=1rtag=1，則，則rchildrchild指向該結(jié)點(diǎn)的后繼；若指向該結(jié)點(diǎn)的后繼

28、；若rtag=0rtag=0，則，則rchildrchild指向該指向該結(jié)點(diǎn)的右孩子，此時(shí)，應(yīng)從右孩子開始，沿左指結(jié)點(diǎn)的右孩子，此時(shí)，應(yīng)從右孩子開始，沿左指針前進(jìn)，直到找到?jīng)]有左孩子的結(jié)點(diǎn)針前進(jìn)，直到找到?jīng)]有左孩子的結(jié)點(diǎn)s s（ltag=1ltag=1）, ,則則s s就是就是p p的后繼，即后繼是中序遍的后繼，即后繼是中序遍歷右子樹時(shí)，訪問的第一個(gè)結(jié)點(diǎn)；歷右子樹時(shí)，訪問的第一個(gè)結(jié)點(diǎn)；6.4 遍歷二叉樹和遍歷二叉樹和線索二叉樹線索二叉樹中序線索二叉樹中，找結(jié)點(diǎn)的后繼中序線索二叉樹中，找結(jié)點(diǎn)的后繼算法算法FUNCFUNC in_next(p,thrt:thlinktp):thlinktp；在以t

29、hrt為頭指針的中序線索二叉樹上,查找指針p所指結(jié)點(diǎn)的后繼 s:=p.rchild； IFIF p.rtag=0 THEN THEN WHILE WHILE s.ltag=0 DODO s:= s.lchild； RETURN(s)ENDIFENDIF；in_nextp1sp010s6.4 遍歷二叉樹和遍歷二叉樹和線索二叉樹線索二叉樹（2 2）遍歷中序線索二叉樹算法）遍歷中序線索二叉樹算法PROCPROC thrt_inorder(thrt:thlinktp)；遍歷以遍歷以thrtthrt為頭指針的中序線索二叉樹為頭指針的中序線索二叉樹 p:=thrt.lchild； WHILE p.lchi

30、ldthrt DO p:= p.lchild; 定位要遍歷的第一個(gè)結(jié)點(diǎn)定位要遍歷的第一個(gè)結(jié)點(diǎn). WHILEWHILE pthrt DODO visit(p.data)； p:=in_next(p,thrt)ENDPENDP；thrt_inorder p.ltag=0 6.4 遍歷二叉樹和遍歷二叉樹和線索二叉樹線索二叉樹2 2）遍歷后序線索二叉樹）遍歷后序線索二叉樹（1 1）后序線索二叉樹中，找結(jié)）后序線索二叉樹中，找結(jié)點(diǎn)的后繼算法點(diǎn)的后繼算法算法思想算法思想: : 對(duì)任意結(jié)點(diǎn)對(duì)任意結(jié)點(diǎn)p p， 若若p p為二叉樹的根，則無(wú)后繼為二叉樹的根，則無(wú)后繼; ; 若若p p是雙親的右孩子、或是獨(dú)是雙親

31、的右孩子、或是獨(dú)生左孩子，則后繼為雙親；生左孩子，則后繼為雙親； 若若p p是有兄弟的左孩子，則后是有兄弟的左孩子，則后繼為雙親的右子樹上按后序遍歷繼為雙親的右子樹上按后序遍歷時(shí)，訪問的第一個(gè)結(jié)點(diǎn)時(shí)，訪問的第一個(gè)結(jié)點(diǎn)( (葉結(jié)點(diǎn)葉結(jié)點(diǎn)) )；spspsps6.4 遍歷二叉樹和遍歷二叉樹和線索二叉樹線索二叉樹后序線索二叉樹中，找結(jié)點(diǎn)的后繼后序線索二叉樹中，找結(jié)點(diǎn)的后繼算法算法FUNCFUNC post_next(p,thrt:thlinktp):thlinktp；在以在以thrtthrt為頭指針的后序線索二叉樹上為頭指針的后序線索二叉樹上, ,查找指針查找指針p p所指所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)的后繼

32、s:=parent（thrt，p）；在在thrtthrt上查找上查找p p的雙親的雙親 IF s=thrt THEN RETURN(thrt)； IFIF s.rchild=p OR s.rtag=1 THEN THEN RETURN(s)； WHILEWHILE s.rtag=0 DODO s:= s.rchild； WHILEWHILE s.ltag=0 DO DO s:= s.lchild； RETURN(s)ENDIFENDIF；post_next6.4 遍歷二叉樹和遍歷二叉樹和線索二叉樹線索二叉樹（2 2）遍歷后序線索二叉樹算法）遍歷后序線索二叉樹算法PROCPROC thrt_po

33、storder(thrt:thlinktp)；遍歷以遍歷以thrtthrt為頭指針的后序線索二叉樹為頭指針的后序線索二叉樹 IFIF thrtthrt.lchild THENTHEN p:=thrt.lchild； search:=true； WHILEWHILE search DODO WHILEWHILE p.ltag=0 DODO p:= p.lchild； IFIF p.rtag=0 THENTHEN p:= p.rchild ELSEELSE search:=false； WHILEWHILE pthrt DODO visit(p.data)； p:=post_next(p,thrt

34、)ENDPENDP；thrt_postorder6.4 遍歷二叉樹和遍歷二叉樹和線索二叉樹線索二叉樹3 3）遍歷先序線索二叉樹）遍歷先序線索二叉樹（1 1）先序線索二叉樹中，找結(jié)點(diǎn)的后繼算法）先序線索二叉樹中，找結(jié)點(diǎn)的后繼算法算法思想算法思想: : 對(duì)任意結(jié)點(diǎn)對(duì)任意結(jié)點(diǎn)p:p: 若若p p有左孩子，則后繼為左孩子有左孩子，則后繼為左孩子; ; 若若p p無(wú)左孩子無(wú)左孩子, ,有右孩子，則后繼為右孩子；有右孩子，則后繼為右孩子； 若若p p無(wú)左孩子無(wú)左孩子, ,也無(wú)右孩子，則后繼為右線索；也無(wú)右孩子，則后繼為右線索；6.4 遍歷二叉樹和遍歷二叉樹和線索二叉樹線索二叉樹先序線索二叉樹中，找結(jié)點(diǎn)的后

35、繼先序線索二叉樹中，找結(jié)點(diǎn)的后繼算法算法FUNCFUNC pre_next(p,thrt:thlinktp):thlinktp；在以在以thrtthrt為頭指針的先序線索二叉樹上為頭指針的先序線索二叉樹上, ,查找指針查找指針p p所指所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)的后繼 IFIF p.ltag=0 THEN THEN RETURN(p.lchild)； ELSEELSE RETURN(p.rchild)ENDIFENDIF;pre_next6.4 遍歷二叉樹和遍歷二叉樹和線索二叉樹線索二叉樹（2 2）遍歷先序線索二叉樹算法）遍歷先序線索二叉樹算法PROCPROC thrt_preorder(thrt:t

36、hlinktp)；遍歷以遍歷以thrtthrt為頭指針的先序線索二叉樹為頭指針的先序線索二叉樹 p:=thrt.lchild； WHILEWHILE pthrt DODO visit(p.data)； p:=pre_next(p,thrt)ENDPENDP;thrt_preorder6.樹和森林樹和森林一樹的存儲(chǔ)結(jié)構(gòu)一樹的存儲(chǔ)結(jié)構(gòu)雙親表示法雙親表示法 用一組地址連續(xù)的存儲(chǔ)單元來(lái)存放樹的結(jié)點(diǎn)，用一組地址連續(xù)的存儲(chǔ)單元來(lái)存放樹的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)有兩個(gè)域：每個(gè)結(jié)點(diǎn)有兩個(gè)域：datadata域域-存放結(jié)點(diǎn)的信息；存放結(jié)點(diǎn)的信息；parentparent域域-存放該結(jié)點(diǎn)雙親結(jié)點(diǎn)的位置存放該結(jié)點(diǎn)雙親結(jié)點(diǎn)的位

37、置 data parent特點(diǎn)：求結(jié)點(diǎn)特點(diǎn)：求結(jié)點(diǎn)的雙親很容易，的雙親很容易，但求結(jié)點(diǎn)的孩但求結(jié)點(diǎn)的孩子需要遍歷整子需要遍歷整個(gè)向量。個(gè)向量。6.樹和森林樹和森林孩子表示法孩子表示法 每個(gè)結(jié)點(diǎn)的孩子用單鏈表存儲(chǔ)，稱為孩子鏈表。每個(gè)結(jié)點(diǎn)的孩子用單鏈表存儲(chǔ)，稱為孩子鏈表。 n n個(gè)結(jié)點(diǎn)可以有個(gè)結(jié)點(diǎn)可以有n n個(gè)孩子鏈表（葉結(jié)點(diǎn)的孩子鏈個(gè)孩子鏈表（葉結(jié)點(diǎn)的孩子鏈表為空表）。表為空表）。 n n個(gè)孩子鏈表的頭指針用一個(gè)向量表示。個(gè)孩子鏈表的頭指針用一個(gè)向量表示。如圖：頭指針向量孩子鏈表如圖：頭指針向量孩子鏈表特點(diǎn)：與相反，求孩子易，求特點(diǎn)：與相反，求孩子易，求雙親難。雙親難。6.樹和森林樹和森林雙親孩

38、子表示法雙親孩子表示法 在孩子表示法的頭指針向量中，增加一項(xiàng)，用來(lái)在孩子表示法的頭指針向量中，增加一項(xiàng)，用來(lái)表示該結(jié)點(diǎn)的雙親。表示該結(jié)點(diǎn)的雙親。如圖：頭指針向量孩子鏈表如圖：頭指針向量孩子鏈表6.樹和森林樹和森林孩子兄弟表示法孩子兄弟表示法用二叉鏈表作為樹的存儲(chǔ)結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)的左鏈域指用二叉鏈表作為樹的存儲(chǔ)結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)的左鏈域指向該結(jié)點(diǎn)的第一個(gè)孩子，右鏈域指向下一個(gè)兄弟結(jié)點(diǎn)。向該結(jié)點(diǎn)的第一個(gè)孩子，右鏈域指向下一個(gè)兄弟結(jié)點(diǎn)。如圖：如圖：雙親只管長(zhǎng)子雙親只管長(zhǎng)子長(zhǎng)子連接兄弟長(zhǎng)子連接兄弟6.樹和森林樹和森林二、森林、樹與二叉樹的對(duì)應(yīng)關(guān)系二、森林、樹與二叉樹的對(duì)應(yīng)關(guān)系、樹與二叉樹的對(duì)應(yīng)關(guān)系、樹與二叉

39、樹的對(duì)應(yīng)關(guān)系樹與二叉樹均可用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，樹與二叉樹均可用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，因此給定一棵樹，用二叉鏈表存儲(chǔ)，可唯一對(duì)因此給定一棵樹，用二叉鏈表存儲(chǔ)，可唯一對(duì)應(yīng)一棵二叉樹，反之亦然。應(yīng)一棵二叉樹，反之亦然。 （）順時(shí)針轉(zhuǎn)度）順時(shí)針轉(zhuǎn)度（）孩子兄弟法）孩子兄弟法樹解釋：解釋：B是是A的第一個(gè)孩子，的第一個(gè)孩子，C、E是是B的兄弟的兄弟，D是是C的第一個(gè)孩子的第一個(gè)孩子。解釋：是的左孩子，解釋：是的左孩子，是的右孩子。是的右孩子。6.樹和森林樹和森林樹變?yōu)槎鏄涞姆椒渥優(yōu)槎鏄涞姆椒ǎǎ┰谛值苤g加一連線；（）在兄弟之間加一連線；（）對(duì)每一個(gè)結(jié)點(diǎn)，只保留它與第一個(gè)孩子的（）對(duì)每一個(gè)結(jié)點(diǎn)

40、，只保留它與第一個(gè)孩子的連線，去掉與其他孩子的連線；連線，去掉與其他孩子的連線；（）以樹根為軸心，將整棵樹順時(shí)針旋轉(zhuǎn)（）以樹根為軸心，將整棵樹順時(shí)針旋轉(zhuǎn)4545度。度。 特點(diǎn)特點(diǎn)：根無(wú)右子樹：根無(wú)右子樹6.樹和森林樹和森林2.2.森林與二叉樹的對(duì)應(yīng)關(guān)系森林與二叉樹的對(duì)應(yīng)關(guān)系（1 1）森林轉(zhuǎn)換為二叉樹的方法）森林轉(zhuǎn)換為二叉樹的方法 將森林將森林 F=TF=T1 1，T T2 2 . T Tm m 的各棵樹分別轉(zhuǎn)成二叉樹的各棵樹分別轉(zhuǎn)成二叉樹BTBT1 1，BTBT2 2 . BTBTm m 將將BTBTi+1i+1作為作為BTBTi i根結(jié)點(diǎn)的右子樹根結(jié)點(diǎn)的右子樹（i=1,2,i=1,2,.,m

41、-1,m-1）, ,得到一棵得到一棵BTBT。6.樹和森林樹和森林如圖：如圖： F=T1 ，T2， T3DBCABT1FEBT2BCFEJHADIGT1T3T2BT3HJIGJIFEBDAHGC6. 樹和森林樹和森林(2)二叉樹轉(zhuǎn)換森林的方法二叉樹轉(zhuǎn)換森林的方法 將當(dāng)前根結(jié)點(diǎn)和其左子樹作為森林的一棵樹將當(dāng)前根結(jié)點(diǎn)和其左子樹作為森林的一棵樹,并并將其右子樹作為森林的其他子樹；將其右子樹作為森林的其他子樹； 重復(fù)上面直到某結(jié)點(diǎn)的右子樹為空。重復(fù)上面直到某結(jié)點(diǎn)的右子樹為空。JIHGFEBCDAT1BCDAFET2T3JIHG6.6哈夫曼樹及其應(yīng)用哈夫曼樹及其應(yīng)用哈夫曼樹（哈夫曼樹（Huffman）樹

42、是一類帶權(quán)路徑長(zhǎng)度最短的樹）樹是一類帶權(quán)路徑長(zhǎng)度最短的樹一、一、Huffman樹（最優(yōu)二叉樹）樹（最優(yōu)二叉樹）1、概念概念 兩結(jié)點(diǎn)間的路徑：從一結(jié)點(diǎn)到另一結(jié)點(diǎn)所經(jīng)過(guò)的結(jié)點(diǎn)序列兩結(jié)點(diǎn)間的路徑：從一結(jié)點(diǎn)到另一結(jié)點(diǎn)所經(jīng)過(guò)的結(jié)點(diǎn)序列 路徑長(zhǎng)度：路徑上的分支樹路徑長(zhǎng)度：路徑上的分支樹 樹的路徑長(zhǎng)度：從根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和樹的路徑長(zhǎng)度：從根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和2763415例-為結(jié)點(diǎn)為結(jié)點(diǎn)1到到5之間的路徑，其之間的路徑，其路徑長(zhǎng)度為路徑長(zhǎng)度為2，樹的路徑長(zhǎng)度樹的路徑長(zhǎng)度=l12 +l13+ l14 +l15+ l16 +l17 =1+1+2+2+2+2=106.6哈夫曼樹及其應(yīng)用哈夫曼樹及其應(yīng)

43、用 完全二叉樹是路徑長(zhǎng)度最短的二叉樹。完全二叉樹是路徑長(zhǎng)度最短的二叉樹。 考慮帶權(quán)時(shí)：設(shè)樹中有考慮帶權(quán)時(shí)：設(shè)樹中有m個(gè)葉結(jié)點(diǎn)，每個(gè)個(gè)葉結(jié)點(diǎn)，每個(gè)葉結(jié)點(diǎn)帶一個(gè)權(quán)值葉結(jié)點(diǎn)帶一個(gè)權(quán)值w且根到葉結(jié)點(diǎn)且根到葉結(jié)點(diǎn)i的路徑長(zhǎng)的路徑長(zhǎng)度為度為 Li (=1，2， m），則樹的帶權(quán)路），則樹的帶權(quán)路徑長(zhǎng)度為樹中所有葉結(jié)點(diǎn)的權(quán)值與路徑長(zhǎng)度徑長(zhǎng)度為樹中所有葉結(jié)點(diǎn)的權(quán)值與路徑長(zhǎng)度的乘積的總和。的乘積的總和。 即：即： 6.6哈夫曼樹及其應(yīng)用哈夫曼樹及其應(yīng)用 例：使使WPL最小的二叉樹成為最優(yōu)二叉樹最小的二叉樹成為最優(yōu)二叉樹(Huffman 樹樹)完全二叉樹完全二叉樹dcab7 5 2 4 cdba2475WPLa=

44、2*7+2*5+2*2+2*4 WPLb=7*3+5*3+2*1+4*2 =36 =466.6哈夫曼樹及其應(yīng)用哈夫曼樹及其應(yīng)用 Huffman 樹樹WPLc=7*1+5*2+2*3+4*3 =35bdca7524（1）完全二叉樹并）完全二叉樹并不一定是不一定是Huffman樹；樹；（2）HT是權(quán)值越大是權(quán)值越大的越靠近根結(jié)點(diǎn)；的越靠近根結(jié)點(diǎn)；（3）HT不唯一，但不唯一，但WPL一定相等。一定相等。6.6哈夫曼樹及其應(yīng)用哈夫曼樹及其應(yīng)用2構(gòu)造構(gòu)造 Huffman樹算法樹算法(1) 以權(quán)值分別為以權(quán)值分別為W1,W2的各結(jié)點(diǎn)，構(gòu)成的各結(jié)點(diǎn)，構(gòu)成n棵棵二叉樹二叉樹T1,T2,Tn并組成森林并組成森林F=T1,T2,Tn,其中其中每棵二叉樹每棵二叉樹 Ti僅有一個(gè)權(quán)值為僅有一個(gè)權(quán)值為 Wi的根結(jié)點(diǎn)；的根結(jié)點(diǎn)；(2) 在在F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為左右子樹構(gòu)造中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為左右子樹構(gòu)造一棵新二叉樹，并且置新二叉樹根結(jié)點(diǎn)權(quán)值為左右子樹上一棵新二叉樹，并且置新二叉樹根結(jié)點(diǎn)權(quán)值為左右子樹上根結(jié)點(diǎn)的權(quán)值之和（根結(jié)點(diǎn)的權(quán)值根結(jié)點(diǎn)的權(quán)值之和（根結(jié)點(diǎn)的權(quán)值=左右孩子權(quán)值之和，左右孩子權(quán)值之和，葉結(jié)點(diǎn)的權(quán)值葉