數(shù)據(jù)結(jié)構(gòu)-樹與二叉樹

1、樹與二叉樹梁 音地球信息科學(xué)與技術(shù)系地球物理與空間信息學(xué)院基本概念回顧從此處開始我們將要接觸到非線性結(jié)構(gòu)了。回憶一下線性數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)？有限、有序只有唯一的頭和尾除了頭和尾以外，每一個(gè)數(shù)據(jù)元素都只有唯一的直接前驅(qū)和唯一的直接后繼基本概念回顧那么非線性的數(shù)據(jù)結(jié)構(gòu)將打破這三大特點(diǎn)中的一種或多種。比如我們即將講到的樹，它有唯一的頭，我們稱為根節(jié)點(diǎn)(Root)，但是它有很多尾，我們稱為葉子節(jié)點(diǎn)(Leaf)；除了根節(jié)點(diǎn)和葉子節(jié)點(diǎn)外，中間的節(jié)點(diǎn)有很多直接后繼，但是都只有唯一的直接前驅(qū)。樹的基本概念樹的基本概念A(yù)節(jié)點(diǎn)就是根節(jié)點(diǎn)，它沒有直接前驅(qū)；J、K、F、C、L、H和I節(jié)點(diǎn)都是葉子節(jié)點(diǎn)，它們都沒有直接后繼；

2、E、B、G和D節(jié)點(diǎn)都是中間節(jié)點(diǎn)；E的直接前驅(qū)是B，直接后繼是J和K；B的直接前驅(qū)是A，直接后繼是E和F；D的直接前驅(qū)也是A，直接后繼是G、H和I。樹的基本概念樹的定義：(1)有且僅有一個(gè)根節(jié)點(diǎn)；(2)除了根節(jié)點(diǎn)之外，其余的節(jié)點(diǎn)可以分成若干個(gè)互不相交有限集合，其中的每一個(gè)集合本身又是一棵樹?？梢?，樹的定義本身就是遞歸的。所以有關(guān)樹結(jié)構(gòu)的算法一般多以遞歸形式給出。樹的基本概念A(yù)為根節(jié)點(diǎn)；B、E、F、J和K組成一棵子樹，B為該子樹的根節(jié)點(diǎn)；C獨(dú)立組成一棵子樹，它既是根節(jié)點(diǎn)，又是葉子節(jié)點(diǎn)；D、G、H、I和L節(jié)點(diǎn)組成另一棵子樹，D為該子樹的根節(jié)點(diǎn)。樹的基本概念B、C和D節(jié)點(diǎn)有相同的直接前驅(qū)A，A稱為他們

3、的父節(jié)點(diǎn)(Parent)，B、C和D稱為A的孩子(Child)；有同一個(gè)父節(jié)點(diǎn)的孩子節(jié)點(diǎn)互稱兄弟(Sibling)，B、C和D節(jié)點(diǎn)就互為兄弟。以某一節(jié)點(diǎn)為根的子樹中的任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫(Offspring)。E、F、J和K節(jié)點(diǎn)都是B的子孫。樹的基本概念樹中節(jié)點(diǎn)得最大層次稱為樹的深度(Depth)或高度。節(jié)點(diǎn)的度：節(jié)點(diǎn)所擁有的子樹的數(shù)目。樹的度：樹內(nèi)各節(jié)點(diǎn)度的最大值。森林(Forest)是若干棵互不相交的樹的集合樹中節(jié)點(diǎn)的各子樹從左自右是右次序的，則該樹為有序樹，否則為無序樹。樹的基本概念樹的深度為4A節(jié)點(diǎn)的度為3B節(jié)點(diǎn)的度為2去掉A節(jié)點(diǎn)后，集合B, E, F, J, H, C, D,

4、G, H, I, L組成森林。樹的基本概念就邏輯結(jié)構(gòu)而言，任何一棵樹都是一個(gè)二元組Tree = (root, F)，其中，root是樹的根節(jié)點(diǎn)，F(xiàn)是m棵樹所構(gòu)成的森林。F = (T1, T2, Tm)，其中Ti = (ri, Fi)稱作根root的第i棵子樹。并且有Ti與Tj的交集為空集，其中1ij=m二叉樹二叉樹(Binary Tree)：本身是樹型結(jié)構(gòu)。每個(gè)節(jié)點(diǎn)最多只有兩棵子樹。即，節(jié)點(diǎn)的度不能大于2。二叉樹的子樹有左右之分，其次序不能顛倒。所以二叉樹是一個(gè)有序樹。二叉樹的性質(zhì)性質(zhì)1：在二叉樹的第i層上最多有2i1個(gè)節(jié)點(diǎn)。證明：用數(shù)學(xué)歸納法。i = 1時(shí)，節(jié)點(diǎn)數(shù)為1，就是根節(jié)點(diǎn)，假設(shè)i =

5、 k時(shí)，命題成立，即第k層上最多有2k1個(gè)節(jié)點(diǎn)，那么對于k+1層而言，由于是二叉數(shù)，其節(jié)點(diǎn)至多就是2第k層上的節(jié)點(diǎn)數(shù)。二叉樹的性質(zhì)性質(zhì)2：深度為k的二叉數(shù)，最多有2k-1個(gè)節(jié)點(diǎn)根據(jù)性質(zhì)1，對于第k而言，其最大的節(jié)點(diǎn)數(shù)是2i-1。那么總的節(jié)點(diǎn)數(shù)不能超過：二叉樹的性質(zhì)性質(zhì)3：對任何一棵二叉數(shù)T，如果其終端節(jié)點(diǎn)數(shù)為n0，度為2的節(jié)點(diǎn)數(shù)為n2，則n0 = n2+1。假設(shè)度為1的節(jié)點(diǎn)數(shù)為n1，則總的節(jié)點(diǎn)數(shù)為n0+ n1+ n2。除了根節(jié)點(diǎn)以外，每一個(gè)節(jié)點(diǎn)都只有唯一的直接前驅(qū)。二叉樹的性質(zhì)那么總的節(jié)點(diǎn)數(shù)還可以等于：n1+2n2+1實(shí)際的分支數(shù)就和中間節(jié)點(diǎn)與葉子節(jié)點(diǎn)總和相等。與式子n0+ n1+ n2作比較

6、，可以得到性質(zhì)3： n0 = n2+1兩類特殊的二叉數(shù)滿二叉樹：必須首先是二叉樹所有的節(jié)點(diǎn)的度都是2如果深度為k，則節(jié)點(diǎn)樹就是2k-1兩類特殊的二叉數(shù)這里為了方便的引入另外一種特殊的二叉樹，我們給滿二叉樹的每一個(gè)節(jié)點(diǎn)編號。編號的規(guī)則：從上向下，從左向右。如果我們對二叉樹按上述規(guī)則進(jìn)行編號，與其同深度的滿二叉樹對應(yīng)節(jié)點(diǎn)編號全一樣的樹稱為完全二叉樹。兩類特殊的二叉數(shù) 樹T1 樹T2兩類特殊的二叉數(shù) 樹T3 樹T4兩類特殊的二叉數(shù)樹T1和T3都是完全二叉樹，樹T2和T4都不是完全二叉樹。完全二叉樹的特點(diǎn)：葉子節(jié)點(diǎn)只可能在最大的兩層上出現(xiàn)；對任一節(jié)點(diǎn)，若其右分支下的子孫的最大層次為L，則其左分支下的子

7、孫的最大層次必為L或L1。二叉樹的性質(zhì)性質(zhì)4：具有n個(gè)節(jié)點(diǎn)的完全二叉樹的深度為log2n+1。若深度為k，根據(jù)完全二叉樹的定義以及性質(zhì)2，2k-1-1n=2k-1或者2k-1=n 2k，這樣，就有k-1= log2nk成立。于是，k = log2n+1。二叉樹的存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)用一組地址連續(xù)的存儲單元依次自上而下，從左至右存儲二叉樹上的節(jié)點(diǎn)元素。鏈?zhǔn)酱鎯Y(jié)構(gòu)依靠指針來連接根節(jié)點(diǎn)和其左、右子樹。二叉樹的存儲結(jié)構(gòu)順序存儲：123456789101112131415二叉樹的存儲結(jié)構(gòu)順序存儲：12345000067二叉樹的存儲結(jié)構(gòu)順序存儲：優(yōu)點(diǎn)：簡單、方便缺點(diǎn)：深度為k且只有k個(gè)節(jié)點(diǎn)的單枝樹，仍然需要使用2 k-1的一維數(shù)組存放。102000300000004二叉樹的存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)表示二叉樹的鏈表的結(jié)點(diǎn)中包含三個(gè)域：數(shù)據(jù)域左指針域右指針域LChildDataRChild二叉樹的存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)(C語言描述)typedef struct BiTNode ElemType data; struct BiTNode *LChild, *RChild; /左右孩子指針BiTree二叉樹