樹和二叉樹1(定義和性質(zhì))

1、6.1 樹樹的定的定義義和基本和基本概概念念6.2 二叉二叉樹樹6.3 遍遍歷歷二叉二叉樹樹6.4 樹樹和森林和森林6.5 哈夫曼哈夫曼樹樹及其及其應(yīng)應(yīng)用用6.1 樹的定義和基本概念樹的定義和基本概念 一、樹的概念一、樹的概念：是：是n個結(jié)點的有限集合。個結(jié)點的有限集合。 根結(jié)點根結(jié)點 m個互不相交的有限集：個互不相交的有限集： T1，T2，Tm 其中每一個集合本身又是一棵樹，并且稱其中每一個集合本身又是一棵樹，并且稱為根的為根的子樹子樹。 樹的定義是遞歸的。樹的定義是遞歸的。非空樹非空樹: A A B C D B C D E F G H E F G H I J I J 二、樹的表示二、樹的表

2、示(1) 結(jié)點連線結(jié)點連線。隱含：上方結(jié)點是下方結(jié)點的前驅(qū)。隱含：上方結(jié)點是下方結(jié)點的前驅(qū)。(2)二元組表示二元組表示 如上面的如上面的T2可表示為：可表示為：K=C,G,I,JR=, C GI J 關(guān)系關(guān)系r應(yīng)滿足以下關(guān)系：應(yīng)滿足以下關(guān)系：根結(jié)點沒有前驅(qū)；根結(jié)點沒有前驅(qū)；其余每個結(jié)點只有一個前驅(qū)結(jié)點其余每個結(jié)點只有一個前驅(qū)結(jié)點任何結(jié)點可以有多個后繼任何結(jié)點可以有多個后繼A( )T1T3T2樹根(3) 廣義表表示廣義表表示B(E, F), C(G( I, J), D(H) A A B C D B C D E F G H E F G H I J I J 三、基本術(shù)語三、基本術(shù)語(1)樹的結(jié)點樹的

3、結(jié)點:包含一個數(shù)據(jù)元素包含一個數(shù)據(jù)元素及若干指向其子樹的分支及若干指向其子樹的分支(2)結(jié)點的度（結(jié)點的度（degree）：結(jié)點：結(jié)點擁有的子樹數(shù)。擁有的子樹數(shù)。(3)樹的度樹的度:樹內(nèi)各結(jié)點的度的最樹內(nèi)各結(jié)點的度的最大值。大值。 (4)根結(jié)點根結(jié)點：無前驅(qū)。：無前驅(qū)。(5)葉子（終端結(jié)點）葉子（終端結(jié)點）：度為零：度為零的結(jié)點。無后繼。的結(jié)點。無后繼。(6)分支結(jié)點（非終端結(jié)點）分支結(jié)點（非終端結(jié)點）：度不為零的結(jié)點。除根結(jié)點外度不為零的結(jié)點。除根結(jié)點外，分支結(jié)點也稱，分支結(jié)點也稱內(nèi)部結(jié)點內(nèi)部結(jié)點（一（一個前驅(qū)，多個后繼）個前驅(qū)，多個后繼） A B C D E F G H I J (8) 孩

4、子結(jié)點、雙親結(jié)點、和孩子結(jié)點、雙親結(jié)點、和兄弟結(jié)點：兄弟結(jié)點：(9) 堂兄弟：堂兄弟：(10)祖先：祖先：結(jié)點的祖先是從根結(jié)點的祖先是從根到該結(jié)點所經(jīng)分支上的所有到該結(jié)點所經(jīng)分支上的所有結(jié)點。結(jié)點。(11)子孫：子孫：以某結(jié)點為根的子以某結(jié)點為根的子樹中的任一結(jié)點都稱為該結(jié)樹中的任一結(jié)點都稱為該結(jié)點的子孫。點的子孫。(12)結(jié)點的層次：結(jié)點的層次：根為第一層根為第一層，根的孩子為第二層。，根的孩子為第二層。(13)樹的深度（高度）樹的深度（高度）：樹中：樹中結(jié)點的最大層次。結(jié)點的最大層次。 A B C D E F G H I J (14)(14)有序樹及無序樹有序樹及無序樹 B FE B E

5、FT1T2家族樹、機構(gòu)樹家族樹、機構(gòu)樹（15）森林）森林：M棵互不相交的樹的集合?？没ゲ幌嘟坏臉涞募?。線性結(jié)構(gòu)線性結(jié)構(gòu)樹型結(jié)構(gòu)樹型結(jié)構(gòu)第一個數(shù)據(jù)元素第一個數(shù)據(jù)元素 ( (無前驅(qū)無前驅(qū)) ) 根結(jié)點根結(jié)點 ( (無前驅(qū)無前驅(qū)) )最后一個數(shù)據(jù)元素最后一個數(shù)據(jù)元素 (無后繼無后繼)多個葉子結(jié)點多個葉子結(jié)點 ( (無后繼無后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個前驅(qū)、一個前驅(qū)、 一個后繼一個后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個前驅(qū)、一個前驅(qū)、 多個后繼多個后繼) )樹結(jié)構(gòu)與線性結(jié)構(gòu)的比較樹結(jié)構(gòu)與線性結(jié)構(gòu)的比較6.2 二叉樹二叉樹 6.2.1 二叉樹的定義和性質(zhì)二叉樹的定義和性質(zhì) 6.2

6、.2 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu) 6.2.3 二叉樹的運算二叉樹的運算一 、定義定義：二叉樹是n(n0)個結(jié)點的有限集合。它或為空樹(n=0),或由一個根結(jié)點和兩棵分別稱為根的左子樹和右子樹的互不相交的二叉樹組成。 這也是一個遞歸定義。二叉樹可以是空集合，根可以有空的左子樹或空的右子樹。6.2.1 二叉樹的定義及其性質(zhì)二叉樹的定義及其性質(zhì)ABCDEFGHK根結(jié)點左子樹右子樹EF特點特點：每個結(jié)點至多只有兩棵子樹，子樹有左：每個結(jié)點至多只有兩棵子樹，子樹有左右之分，其次序不能任意顛倒，分別稱為左右右之分，其次序不能任意顛倒，分別稱為左右子樹。子樹。ab兩棵不同的二叉樹兩棵不同的二叉樹ab二

7、叉樹的五種基本形態(tài)二叉樹的五種基本形態(tài) 空二叉樹空二叉樹 僅有僅有根結(jié)點根結(jié)點 右子右子樹為空樹為空 左子左子樹為空樹為空左右子樹左右子樹均非空均非空二、特殊的二叉樹二、特殊的二叉樹（1）滿二叉樹）滿二叉樹423167891011121314155特點：每一層上都含有最大結(jié)點數(shù)。特點：每一層上都含有最大結(jié)點數(shù)。深度為k k且含有2 -1個結(jié)點的二叉樹k（2）完全二叉樹）完全二叉樹4231678910 11125 完全二叉樹完全二叉樹滿二叉樹是完全二叉樹的特例滿二叉樹是完全二叉樹的特例樹中所含的 n n 個結(jié)點和滿二叉樹中編號編號為為 1 1 至至 n n 的結(jié)點的結(jié)點一一對應(yīng)。42316789

8、1011121314155滿二叉樹滿二叉樹4231678910 11125 非完全二叉樹非完全二叉樹4231678910 11125 完全二叉樹完全二叉樹（3）理想平衡樹）理想平衡樹 在一棵二叉樹中，若除最后一層外，其余層都是在一棵二叉樹中，若除最后一層外，其余層都是滿的，則稱此樹是理想平衡樹。滿的，則稱此樹是理想平衡樹。 理想平衡樹包括滿二叉樹和完全二叉樹。但并不一理想平衡樹包括滿二叉樹和完全二叉樹。但并不一定是完全二叉樹。定是完全二叉樹。4231678910 11125 理想平衡樹理想平衡樹三、三、 二叉樹的基本性質(zhì)二叉樹的基本性質(zhì) 性質(zhì)性質(zhì)1:在二叉樹的第在二叉樹的第k層上至多有層上至多

9、有2k-1個結(jié)點個結(jié)點(k1) 用歸納法證明：用歸納法證明： (1)k=1時時, 2k-1=1，即只有一個根結(jié)點。，即只有一個根結(jié)點。 (2)設(shè)對設(shè)對1jk-1,命題成立，則可以證明命題成立，則可以證明j=k時時命題也成立。命題也成立。 由于第由于第k-1層上至多有層上至多有2k-2個結(jié)點個結(jié)點，由于二叉，由于二叉樹中每個結(jié)點的度至多為樹中每個結(jié)點的度至多為2，故第，故第k層上的結(jié)層上的結(jié)點數(shù)最多為點數(shù)最多為 2k-2 2= 2k-1。 性質(zhì)性質(zhì)2：深度為：深度為k的二叉樹至多有的二叉樹至多有2k-1個結(jié)點個結(jié)點(k1) k （第（第i層上的最大結(jié)點數(shù)）層上的最大結(jié)點數(shù)） i=1 k = 2i

10、-1 i=1 =( 1 + 2 + 22 + + 2k-1)=2k-1性質(zhì)性質(zhì)3：對任何一棵二叉樹：對任何一棵二叉樹T，如果其終端結(jié)點，如果其終端結(jié)點數(shù)為數(shù)為n0，度為，度為2的結(jié)點數(shù)為的結(jié)點數(shù)為n2，則有，則有n0=n2+1。證明：設(shè)度為證明：設(shè)度為1的結(jié)點數(shù)為的結(jié)點數(shù)為n1, 總結(jié)點數(shù)為總結(jié)點數(shù)為n，則有則有 n = n0 + n1 + n2設(shè)分支數(shù)為設(shè)分支數(shù)為B， n = B + 1（除根結(jié)點外，每一（除根結(jié)點外，每一個結(jié)點都有一個分支到達）又由于這些分支數(shù)個結(jié)點都有一個分支到達）又由于這些分支數(shù)是由度為是由度為1和度為和度為2的結(jié)點發(fā)出的，因此，的結(jié)點發(fā)出的，因此，B = n1 + 2

11、n2。 n0 + n1 + n2 = n1 + 2n2 + 1 n0 = n2 + 1 假設(shè)深度為k，由性質(zhì)2，最大結(jié)點數(shù)為2k-1, 深度為k-1的最大結(jié)點數(shù)為2k-1-1。 2k-1-1 n 2k-1 或 2k-1 n 2k 2k-1 n+1 2k k-1 log2(n+1) klog2(n+1) k log2(n+1) +1 k = log2(n+1) 性質(zhì)性質(zhì)4：具有：具有n個結(jié)點的完全二叉樹的深度為個結(jié)點的完全二叉樹的深度為 log2(n+1) 或或 log2n + 1。k-1 log2 n 1, 則其雙親則其雙親parent(i)是結(jié)點是結(jié)點 i/2 (2)如果如果2in，則結(jié)點，

12、則結(jié)點 i 為葉子，否則其左孩子為葉子，否則其左孩子Lchild(i)是結(jié)點是結(jié)點2i。(3)如果如果2i+1n, 則結(jié)點則結(jié)點i無右孩子，否則其右無右孩子，否則其右孩子是結(jié)點孩子是結(jié)點2i+1。4231678910 11125 完全二叉樹完全二叉樹對于對于i=1,對于對于i1,可分兩種情況討可分兩種情況討論：論：證明證明(2),(3):對于對于i=1,左孩子是左孩子是2, 右孩子是右孩子是3。對于對于i1,可分兩種情況討論：可分兩種情況討論：第一種情況第一種情況：設(shè)第：設(shè)第j層的第層的第1個結(jié)點的編號為個結(jié)點的編號為i(i=2j-1),則其左孩子必為第則其左孩子必為第j+1層的第層的第1個結(jié)

13、點，個結(jié)點，其編號為其編號為 2j =2* 2j-1 =2i。若若2in，則，則i無左孩子。右孩子編號為無左孩子。右孩子編號為2i+1，若若2i+1n，則無右孩子。，則無右孩子。第二種情況：第二種情況：假設(shè)第假設(shè)第j層上某個結(jié)點的編號層上某個結(jié)點的編號為為i, 且且2i+1n，則其左孩子為，則其左孩子為2i，右孩子為，右孩子為2i+1。則編號為則編號為i+1的結(jié)點是編號為的結(jié)點是編號為i的結(jié)點的右兄的結(jié)點的右兄弟或堂兄弟，若它有左孩子，其編號必為弟或堂兄弟，若它有左孩子，其編號必為2i+2=2(i+1),若它有右孩子，其編號必為若它有右孩子，其編號必為2i+3=2(i+1)+1。例例1：具有：

14、具有n個結(jié)點的滿二叉樹，其葉結(jié)點的個結(jié)點的滿二叉樹，其葉結(jié)點的個數(shù)為多少？個數(shù)為多少？n = 2k-1n0 = 2k-1n0 = (n+1)/2例例2：設(shè)高為：設(shè)高為h的二叉樹只有度為的二叉樹只有度為0和和2的結(jié)點的結(jié)點，則此類二叉樹的結(jié)點數(shù)至少為？至多為？，則此類二叉樹的結(jié)點數(shù)至少為？至多為？四、樹與二叉樹的區(qū)別四、樹與二叉樹的區(qū)別A樹中結(jié)點的最大度數(shù)沒有限制，二叉樹結(jié)點最大度數(shù)為樹中結(jié)點的最大度數(shù)沒有限制，二叉樹結(jié)點最大度數(shù)為2。B 無明確指出，樹沒有左、右子樹之分，二叉樹有明確的左、無明確指出，樹沒有左、右子樹之分，二叉樹有明確的左、右子樹之分。右子樹之分。 二叉樹二叉樹樹樹6.2.2

15、二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu) (1) 順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu) 用一組連續(xù)的存儲單元存放二叉樹的數(shù)據(jù)元素。用一組連續(xù)的存儲單元存放二叉樹的數(shù)據(jù)元素。結(jié)點在數(shù)組中的相對位置蘊含著結(jié)點之間的關(guān)系。結(jié)點在數(shù)組中的相對位置蘊含著結(jié)點之間的關(guān)系。#define MAX_TREE_SIZE 100 / 二叉樹的最大結(jié)點數(shù)typedef TElemType SqBiTreeMAX_TREE_SIZE+1; / 1號單元存儲根結(jié)點SqBiTree bt;完全二叉樹完全二叉樹ABCDEFGHIJKLA13LKJIHGFEDCBA 1 2 3 4 5 6 7 8 9 10 11 12若父結(jié)點在數(shù)組中若父結(jié)點在

16、數(shù)組中i i下標處，其左孩子在下標處，其左孩子在2 2* *i i，右孩子在，右孩子在2 2* *i+1i+1ABCDEFG 表示該處沒有元素存在僅僅為了好理解ABCDEFG一般二叉樹一般二叉樹1 2 3 4 5 6 7 8 9 10 11若父結(jié)點在數(shù)組中若父結(jié)點在數(shù)組中i i下標處，其左孩子在下標處，其左孩子在2 2* *i i，右孩子在，右孩子在2 2* *i+1i+1一般二叉樹必須按完全二叉樹的形式存儲，一般二叉樹必須按完全二叉樹的形式存儲，將造成存儲的浪費。將造成存儲的浪費。v一個深度為一個深度為H且只有且只有H個結(jié)點的右單支樹需個結(jié)點的右單支樹需要要2h-1個結(jié)點存儲空間個結(jié)點存儲空間根據(jù)結(jié)點結(jié)構(gòu)不同根據(jù)結(jié)點結(jié)構(gòu)不同 二叉鏈表二叉鏈表 三叉鏈表三叉鏈表(2) 鏈式存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)ADEBCF rootlchild data rchild結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu): :1. 1. 二叉鏈表二叉鏈表typedef struct BiTNode / 結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu) TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指針 BiTNode, *BiTree;lchild data rchild結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu):C 語言的類型描述如下語言