第06章-樹與二叉樹A

第1章緒論第2章線性表第3章棧和隊列

第4章串第5章數組和廣義表第6章

樹和二叉樹

第7章圖第9章查找第10章排序目錄1

教

學

內

容1、樹的基本概念2、二叉樹的定義、性質及運算；3、二叉樹的存儲結構4、遍歷二叉樹5、線索二叉樹6、樹、森林、森林與二叉樹的轉換7、哈夫曼樹、哈夫曼編碼2樹型結構（非線性結構）結點之間有分支具有層次關系生活中的哪些實例是樹型結構呢？例自然界:樹人類社會家譜院系組織機構36.1樹的基本概念

樹的定義

樹是n(n0)個結點的有限集。若n=0，稱為空樹；若n>0，則它滿足如下兩個條件：有且僅有一個稱之為根(Root)的結點。當n>1，除根以外的其它結點分為m(m>0)個互不相交的有限集T1,T2,…,Tm，其中每個集合又是一棵符合本定義的樹，并且稱為根的子樹。4ACGBDEFKLHMIJ例如A只有根結點的樹有13個結點的樹A是根；其余數據元素分成三個互不相交的子集，T1={B,E,F,K,L}；T2={C,G}；T3={D,H,I,J,M},T1,T2,T3都是根A的子樹，且本身也是一棵樹。根結點T15T2T3R={<A,B>,<A,C>,<A,D>,<B,E>,<B,F>,<C,G>,<D,H>,<D,I>,<D,J>,<E,K>,<E,L>,<H,M>}ACGBDEFKLHMIJ6線性結構樹結構存在唯一的沒有前驅的“首元素”存在唯一的沒有前驅的“根結點”存在唯一的沒有后繼的“尾元素”存在多個沒有后繼的“葉子”其余元素均存在唯一的“前驅元素”和唯一的“后繼元素”其余結點均存在唯一的“前驅（雙親）結點”和多個“后繼（孩子）結點”樹結構和線性結構作如下對照：7樹的基本術語1層2層4層3層height=4ACGBDEFKLHMIJ結點結點的度葉子結點分支結點兒子結點父親結點兄弟結點祖先結點樹的度結點的層次樹的深度森林89樹的基本術語——即上層的那個結點(直接前驅)——即下層結點的子樹的根(直接后繼)——同一雙親下的同層結點（孩子之間互稱兄弟）——即雙親位于同一層的結點（但并非同一雙親）——即從根到該結點所經分支的所有結點——即該結點下層子樹中的任一結點ABCGEIDHFJMLK

根葉子森林有序樹無序樹——即根結點(沒有前驅)——即終端結點(沒有后繼)——指m棵不相交的樹的集合(例如刪除A后的子樹個數)雙親孩子兄弟堂兄弟祖先子孫——結點各子樹從左至右有序，不能互換（左為第一）——結點各子樹可互換位置?！礃涞臄祿亍Y點掛接的子樹數結點結點的度結點的層次終端結點分支結點樹的度樹的深度(或高度)ABCGEIDHFJMLK——從根到該結點的層數（根結點算第一層）——即度為0的結點，即葉子——即度不為0的結點（也稱為內部結點）——所有結點度中的最大值（Max{各結點的度}）——指所有結點中最大的層數（Max{各結點的層次}）問：右上圖中的結點數＝；樹的度＝；樹的深度＝1334（有幾個直接后繼就是幾度，亦稱“次數”）10ABCDEFGHIJKLM結點A的度：3結點B的度：2結點M的度：0葉子：K，L，F，G，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的祖先1112樹的性質：性質1：樹中的節(jié)點數n等于所有節(jié)點的度數加1（在一顆樹中，度之和=分支數，而分支數=n-1）性質2：度為m的樹中第i層上至多有mi-1個節(jié)點(i≥1)性質3：高度為h的度為m的樹至多有個節(jié)點。性質4：具有n個節(jié)點的度為m的樹的最小高度為

。13練習題：題目：一顆度為4的樹中，若有20個度為4的節(jié)點，10個度為3的節(jié)點，1個度為2的節(jié)點，10個度為1的節(jié)點，則該樹的葉子節(jié)點為

（）A.41 B.81 C.113 D.122解答：樹中只能有度為0,1,2,3,4的節(jié)點。所有節(jié)點和為n=n0+n1+n2+n3+n4。而度之和=n-1，并且度之和=1×n1+2×n2+3×n3+4×n4=1×10+2×1+3×10+4×20=122。則n=122+1=123n0=n-n1-n2-n3-n4=122-41=81。本題答案為（B）14求解樹的節(jié)點個數問題：對于度為m的樹，在n,n0,n1,n2,…,nm中只有兩個參數未知時，一般可以求出這兩個值。求解過程如下：n=n0+n1+n2+…+nm度之和=n-1度之和=n1+2n2+…+mnm所以有n=n1+2n2+…+mnm+1=n0+n1+n2+…+nm例如：若一顆有n個節(jié)點的樹，其中所有分支節(jié)點的度均為k，求該樹中葉子節(jié)點的個數。顯然，m=k,n2=n3=…=nm-1=0,則n=n0+nk,度之和=n-1=knk,nk=(n-1)/k,所以

n0=n-nk=n–(n-1)/k.有序樹子樹之間存在確定的次序關系無序樹子樹之間不存在確定的次序關系家族樹就屬于有序樹。15森林是m(m≥0)棵互不相交的樹的集合root給森林中的各子樹加上一個父親結點,森林就變成了樹。

T3T2T1ABEFKLDHMIJCGCG16

二叉樹或為空樹，或是由一個根結點加上兩棵分別稱為左子樹和右子樹的、互不交叉的二叉樹組成。6.2二叉樹BDEGHCILFA根結點右子樹左子樹17為何要重點研究每結點最多只有兩個“叉”的樹？二叉樹的結構最簡單，規(guī)律性最強；可以證明，所有樹都能轉為唯一對應的二叉樹，不失一般性。(a)空二叉樹(b)根和空的左右子樹(c)根和左子樹(d)根和右子樹(e)根和左右子樹

注：雖然二叉樹與樹概念不同，但有關樹的基本術語對二叉樹都適用。二叉樹的五種基本形態(tài)18由n個節(jié)點構成的二叉樹的形態(tài)總數為方法：加線—抹線—旋轉

abeidfhgc樹轉二叉樹舉例：abeidfhgc兄弟相連長兄為父孩子靠左特點是？根結點沒有右孩子！19討論：二叉樹怎樣還原為樹？abeidfhgc要點：逆操作，把所有右孩子變?yōu)樾值埽?/p>

abdefhgic20

性質1

在二叉樹的第i層上至多有2i－1個結點。(i1)證明：當i=1時，只有根結點，2i-1=20=1。假設對所有j，i>j1，命題成立，即第j層上至多有2j-1

個結點。由歸納假設第i-1層上至多有2i－2個結點。二叉樹的每個結點的度至多為2，故在第i層上的最大結點數為第i-1層上的最大結點數的2倍，即2*2i－2=2i-1。二叉樹的重要特性21

性質2

深度為k的二叉樹至多有2k-1個結點，其中k1。

證明：由性質1可見，深度為k的二叉樹的最大結點數為＝20+21+…+2k-1=2k-122

性質3

對任何一棵二叉樹T,如果其葉子結點數為n0,度為2的結點數為n2,則n0＝n2＋1。證明：n=n0+n1+n2

①

e=n–1=2n2+n1

②因此，2n2+n1=n0+n1+n2-1

n0=n2+1

23設e為樹的分支總數，則e=n-1。這些分支由度為1或2的節(jié)點射出，所以：滿二叉樹(FullBinaryTree)

定義1

:

一棵深度為k且有2k-1個結點的二叉樹稱為滿二叉樹。兩種特殊形態(tài)的二叉樹754389101113141512126特點:每一層上的結點數都達到最大,葉子全部在最底層24非完全二叉樹完全二叉樹(CompleteBinaryTree)

若設二叉樹的深度為h，除第h層外，其它各層(0h-1)的結點數都達到最大值，第h層從右向左連續(xù)缺若干結點。完全二叉樹621543BACDEGF25

性質4

具有n(n0)個結點的完全二叉樹的深度為log2(n)＋1。

證明：設完全二叉樹的深度為h，則根據性質2和完全二叉樹的定義有2h-1-1<n2h

-1,即2h-1n<2h，取對數h－1log2n<h，又h是整數，因此有h=log2(n)

＋126性質5

若對含n個結點的完全二叉樹從上到下且從左至右進行1至n的編號，則對完全二叉樹中任意一個編號為i的結點：621543245361哪個是完全二叉樹27(1)若i=1，則該結點是二叉樹的根，否則，編號為i/2的結點為其父親結點。(2)若2i>n，則該結點無左孩子，否則，編號為2i的結點為其左孩子結點。(3)若2i+1>n，則該結點無右孩子結點，否則，編號為2i+1的結點為其右孩子

結點。2829節(jié)點i和i+1在同一層上i+12i+22i+3i2i+12ii2i2i+1i+12i+3i/2

2i+2節(jié)點i和i+1不在同一層上二、二叉樹的鏈式存儲表示一、二叉樹的順序存儲表示6.3二叉樹的存儲結構30順序存儲表示用一組地址連續(xù)的存儲單元存儲二叉樹中的數據元素。將完全二叉樹上編號為i的結點元素存儲在一維數組中下標為i-1的分量中

BACEDFGHIJKLMNO31BACEDFGHIJ123456710891練習32

ABDCEF

012345ABCDEF24163