《樹和二叉樹》教學(xué)課件

《樹和二叉樹》幻燈片本課件PPT僅供大家學(xué)習(xí)使用學(xué)習(xí)完請自行刪除，謝謝！本課件PPT僅供大家學(xué)習(xí)使用學(xué)習(xí)完請自行刪除，謝謝！本課件PPT僅供大家學(xué)習(xí)使用學(xué)習(xí)完請自行刪除，謝謝！本課件PPT僅供大家學(xué)習(xí)使用學(xué)習(xí)完請自行刪除，謝謝！《樹和二叉樹》幻燈片本課件PPT僅供大家學(xué)習(xí)使用課程回憶什么是稀疏矩陣稀疏矩陣表示廣義表定義課程回憶什么是稀疏矩陣本講目錄樹的定義和根本術(shù)語二叉樹樹的定義樹的基本術(shù)語二叉樹的定義二叉樹的性質(zhì)二叉樹的存儲結(jié)構(gòu)本講目錄樹的定義和根本術(shù)語樹的定義二叉樹的定本講重點、難點重點二叉樹的定義二叉樹的性質(zhì)二叉樹的存儲構(gòu)造難點二叉樹的定義二叉樹的性質(zhì)本講重點、難點重點樹的定義和根本術(shù)語樹的定義和根本術(shù)語二叉樹樹的定義樹的基本術(shù)語樹的定義和根本術(shù)語樹的定義和根本術(shù)語樹的定義樹的定義樹型結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)。直觀看來樹是以分支關(guān)系定義的層次結(jié)構(gòu)。樹型結(jié)構(gòu)在客觀世界中廣泛存在，如人類社會的族譜和各種社會組織機(jī)構(gòu)都可用樹來形象表示。樹在計算機(jī)領(lǐng)域中也有著廣泛的應(yīng)用，如在數(shù)據(jù)庫系統(tǒng)中，可用樹來組織信息；在分析算法的行為時，可用樹來描述其執(zhí)行過程。樹的定義樹型結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)。樹的定義例如：家族樹樹的定義例如：家族樹樹棧和隊列數(shù)組和廣義表線性表和廣義表數(shù)據(jù)結(jié)構(gòu)……線性表廣義表棧隊列……樹的定義例如本書的目錄樹棧和隊列數(shù)組和廣義表線性表和廣義表數(shù)據(jù)結(jié)構(gòu)……線性表廣義表樹的定義樹的定義樹是由n(n0)個結(jié)點組成的有限集合。如果n=0，稱為空樹；如果n>0，那么:有一個特定的稱之為根(root)的結(jié)點，它只有后繼，但沒有前驅(qū)；除根以外的其它結(jié)點劃分為m(m>0)個互不相交的有限集合T1,T2,…,Tm。每個集合本身又是一棵樹，并且稱之為根的子樹(subTree)。每棵子樹的根結(jié)點有且僅有一個直接前驅(qū)，但可以有0個或多個后繼。樹的定義是遞歸的。樹的定義樹的定義樹的定義例如圖(a)是一棵空樹，沒有結(jié)點圖(b)是一棵只有根結(jié)點的樹，根結(jié)點是A圖(c)是一棵有13個結(jié)點的樹，其中A是根結(jié)點三個互不相交的子集：T1={B,E,F,K,L},T2={C,G},T3={D,H,I,J,M}樹的定義例如圖(a)是一棵空樹，沒有結(jié)點樹的定義抽象數(shù)據(jù)類型樹的定義ADTTree{數(shù)據(jù)對象D：D是具有一樣特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：假設(shè)D為空集，那么稱為空樹；否那么:(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root,(2)當(dāng)n>1時，其余結(jié)點可分為m(m>0)個互不相交的有限集T1,T2,…,Tm,其中每一棵子集本身又是一棵符合本定義的樹，稱為根root的子樹。根本操作P：(見教材)}ADTTree樹的定義抽象數(shù)據(jù)類型樹的定義樹的表示樹的邏輯表示方法有多種，常見的有：樹形圖表示法嵌套集合表示法〔文氏圖表示法〕凹入表示法廣義表表示法樹的定義樹的表示樹的定義樹的根本術(shù)語根本術(shù)語結(jié)點：數(shù)據(jù)元素+假設(shè)干指向子樹的分支結(jié)點的度：分支的個數(shù)〔或子樹的個數(shù)〕葉子結(jié)點〔終端結(jié)點〕：度為零的結(jié)點分支結(jié)點〔非終端結(jié)點〕：度不等于零的結(jié)點樹的度：樹中所有結(jié)點的度的最大值孩子結(jié)點：結(jié)點的子樹的根結(jié)點為該結(jié)點的孩子結(jié)點雙親結(jié)點：與孩子結(jié)點相對應(yīng)的結(jié)點兄弟結(jié)點：同一個雙親的孩子結(jié)點之間的互稱祖先結(jié)點：從根結(jié)點起到該結(jié)點所經(jīng)分支上的所有結(jié)點子孫結(jié)點：以某結(jié)點為根的子樹中的任意結(jié)點樹的根本術(shù)語根本術(shù)語樹的根本術(shù)語根本術(shù)語層次：從根結(jié)點起，根結(jié)點為第一層，跟的孩子為第二層，依次類推假設(shè)根結(jié)點的層次為1,第l層的結(jié)點的子樹根結(jié)點的層次為l+1堂兄弟：雙親在同一層的結(jié)點互稱深度：樹中葉子結(jié)點所在的最大層次有序樹：子樹之間存在確定的次序關(guān)系無序樹：子樹之間不存在確定的次序關(guān)系森林：是m〔m≥0〕棵互不相交的樹的集合。任何一棵非空樹是一個二元組Tree=〔root，F(xiàn)〕其中：root被稱為根結(jié)點，F(xiàn)被稱為子樹森林CGFHIJMDEKLBFAroot樹的根本術(shù)語根本術(shù)語CGFHIJMDEKLBFAroot二叉樹樹的定義和根本術(shù)語二叉樹二叉樹的定義二叉樹的性質(zhì)二叉樹的存儲結(jié)構(gòu)二叉樹樹的定義和根本術(shù)語二叉樹的定義二叉樹的定義二叉樹的定義二叉樹是由n(n>=0)個結(jié)點的有限集合構(gòu)成，此集合或者為空集，或者由一個根結(jié)點及兩棵互不相交的左右子樹組成，并且左右子樹都是二叉樹。二叉樹的每個結(jié)點至多只有兩棵子樹〔結(jié)點的度最多為2〕。二叉樹的子樹有左右之分，其次序不能任意顛倒。根結(jié)點右子樹左子樹EFHKCBADGEF二叉樹的定義二叉樹的定義根結(jié)點右子樹左子樹EFHKCBADG二叉樹的定義抽象數(shù)據(jù)類型二叉樹的定義ADTBinaryTree{數(shù)據(jù)對象D：D是具有一樣特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：假設(shè)D為空集，那么稱為空二叉樹；否那么:(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root(2)當(dāng)n>1時，其余結(jié)點可分為2個互不相交的有限集Dl，Dr(3)假設(shè)Dl，Dr都不為空集，那么Dl，Dr本身又是一棵符合本定義的二叉樹，稱為根root的左右子樹。根本操作P：(見教材)}ADTBinaryTree二叉樹的定義抽象數(shù)據(jù)類型二叉樹的定義二叉樹的定義二叉樹的5種根本形態(tài)AABABACB

(b)根和空的左右子樹

(c)根和左子樹(d)根和右子樹(e)根和左右子樹

(a)空二叉樹二叉樹的定義二叉樹的5種根本形態(tài)AABABACB(5×3！=30棵二叉樹的定義例如：由三個結(jié)點組成的二叉樹的根本類型有幾種？由三個結(jié)點組成的二叉樹的根本形態(tài)有5種。如果這三個結(jié)點分別是A,B,C。那么可以組成幾棵二叉樹？5×3！=30棵二叉樹的定義例如：由三個結(jié)點組成的二叉樹的根二叉樹的性質(zhì)二叉樹的性質(zhì)性質(zhì)1：在二叉樹的第i層上至多有2i-1個結(jié)點。(i≥1)證明：用歸納法證明：歸納基：i=1層時，只有一個根結(jié)點，2i-1=20=1；歸納假設(shè)：假設(shè)對所有的j，1≤ji，命題成立;歸納證明：二叉樹上每個結(jié)點至多有兩棵子樹，那么第i層的結(jié)點數(shù)=2i-22=2i-1。按照題意，二叉樹除最后一層，其余每一層上的結(jié)點都有兩個孩子結(jié)點，那么每一層均比上一層的結(jié)點個數(shù)多一倍。按照等比數(shù)列的定義，每一項都可以看作是相應(yīng)每一層上的結(jié)點個數(shù)，那么，ai=ai*qi-1=2i-1二叉樹的性質(zhì)二叉樹的性質(zhì)用歸納法證明：按照題意，二叉樹除最后二叉樹的性質(zhì)性質(zhì)2：深度為k的二叉樹上至多含2k-1個結(jié)點〔k≥1〕證明：基于上一條性質(zhì)，深度為k

的二叉樹上的結(jié)點數(shù)至多為

20+21++2k-1=2k-1

二叉樹的性質(zhì)性質(zhì)2：深度為k的二叉樹上至多含2k-1個結(jié)點〔二叉樹的性質(zhì)性質(zhì)3：對任何一棵二叉樹，假設(shè)它含有n0個葉子結(jié)點、n2個度為2的結(jié)點，那么必存在關(guān)系式：n0=n2+1證明：設(shè)二叉樹上結(jié)點總數(shù)n=n0+n1+n2又二叉樹上分支總數(shù)B=n1+2n2而B=n-1=n0+n1+n2–1由此，n0=n2+1二叉樹的性質(zhì)性質(zhì)3：對任何一棵二叉樹，假設(shè)它含有n0個葉子滿二叉樹：指的是深度為k且含有2k-1個結(jié)點的二叉樹。完全二叉樹：樹中所含的n個結(jié)點和滿二叉樹中編號為1

至n

的結(jié)點一一對應(yīng)。123456789101112131415abcdefghij特點：每一層上的結(jié)點數(shù)都是最大結(jié)點數(shù)特點：葉子結(jié)點只能在層次最大的兩層出現(xiàn)任意結(jié)點，假設(shè)其右分支下的子孫最大層數(shù)為L,那么左分支下的子孫的最大層次為L或L+1兩類特殊的二叉樹二叉樹的性質(zhì)滿二叉樹：指的是深度為k且含有2k-1個結(jié)點的二叉樹。完全二性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為

log2n+1證明：設(shè)完全二叉樹的深度為k

那么根據(jù)第二條性質(zhì)得2k-1≤n<2k即k-1≤log2n<k

因為k

只能是整數(shù)，因此，k=log2n

+1二叉樹的性質(zhì)性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為證明：設(shè)完全二叉樹性質(zhì)5：假設(shè)對含n個結(jié)點的完全二叉樹從上到下且從左至右進(jìn)展1至n的編號，那么對完全二叉樹中任意一個編號為i的結(jié)點：假設(shè)i=1，那么該結(jié)點是二叉樹的根，無雙親,否那么，編號為i/2的結(jié)點為其雙親結(jié)點;假設(shè)2i>n，那么該結(jié)點無左孩子，

否那么，編號為2i的結(jié)點為其左孩子結(jié)點；假設(shè)2i+1>n，那么該結(jié)點無右孩子結(jié)點，

否那么，編號為2i+1的結(jié)點為其右孩子結(jié)點。二叉樹的性質(zhì)性質(zhì)5：假設(shè)對含n個結(jié)點的完全二叉樹從上到二叉樹的二叉樹的存儲構(gòu)造順序存儲構(gòu)造它是用一組連續(xù)的存儲單元存儲二叉樹的數(shù)據(jù)元素。必須把二叉樹的所有結(jié)點安排成為一個恰當(dāng)?shù)男蛄?，結(jié)點在這個序列中的相互位置能反映出結(jié)點之間的邏輯關(guān)系，用編號的方法：從樹根起，自上層至下層，每層自左至右的給所有結(jié)點編號。順序存儲表示#defineMAX_TREE_SIZE100typedefintTElemType;typedefTElemTypeSqBiTree[MAX_TREE_SIZE]；SqBiTreebt;二叉樹的存儲構(gòu)造順序存儲構(gòu)造二叉樹的存儲構(gòu)造例如：完全二叉樹的數(shù)組表示二叉樹的存儲構(gòu)造例如：完全二叉樹的數(shù)組表示二叉樹的存儲構(gòu)造例如：一般二叉樹的數(shù)組表示00000二叉樹的存儲構(gòu)造例如：一般二叉樹的數(shù)組表示00000二叉樹的存儲構(gòu)造順序存儲構(gòu)造的缺點由于一般二叉樹必須仿照完全二叉樹那樣存儲，可能會浪費(fèi)很多存儲空間，單支樹就是一個極端情況。假設(shè)經(jīng)常需要插入與刪除樹中結(jié)點時，順序存儲方式需要大量移動數(shù)據(jù)。二叉樹的存儲構(gòu)造順序存儲構(gòu)造的缺點二叉樹的存儲構(gòu)造鏈?zhǔn)酱鎯?gòu)造二叉鏈表二叉鏈表構(gòu)造：數(shù)據(jù)域、左指針域、右指針域

lchilddatarchild二叉鏈表存儲表示：typedefcharTElemType;typedefstructBiTNode{TElemTypedata;structBiTNode*lchild，*rchild；//左右孩子指針}BiTNode，*BiTree；二叉樹的存儲構(gòu)造鏈?zhǔn)酱鎯?gòu)造lchilddat二叉樹的存儲構(gòu)造鏈?zhǔn)酱鎯?gòu)造三叉鏈表三叉鏈表構(gòu)造：數(shù)據(jù)域、左指針域、右指針域、雙親指針域

lchilddataparentrchild思考：二叉樹的三叉鏈表存儲表示如何定義？二叉樹的存儲構(gòu)造鏈?zhǔn)酱鎯?gòu)造lchild二叉樹的存儲構(gòu)造二叉樹鏈?zhǔn)酱鎯?gòu)造例如二叉樹的存儲構(gòu)造二叉樹鏈?zhǔn)酱鎯?gòu)造例如教學(xué)內(nèi)容樹的定義和根本術(shù)語二叉樹樹的定義樹的基本術(shù)語二叉樹的定義二叉樹的性質(zhì)二叉樹的存儲結(jié)構(gòu)教學(xué)內(nèi)容樹的定義和根本術(shù)語樹的定義二叉樹的定本講總結(jié)為什么說樹的定義是遞歸的？二叉樹的性質(zhì)有哪些？二叉樹的順序存儲構(gòu)造有什么缺點？本講總結(jié)為什么說樹的定義是遞歸的？上機(jī)實驗實驗14-1建立一棵含有n個結(jié)點的二叉樹，采用二叉鏈表存儲〔ex6-1.c〕上機(jī)實驗實驗14-1ThankYou!ThankYou!《樹和二叉樹》幻燈片本課件PPT僅供大家學(xué)習(xí)使用學(xué)習(xí)完請自行刪除，謝謝！本課件PPT僅供大家學(xué)習(xí)使用學(xué)習(xí)完請自行刪除，謝謝！本課件PPT僅供大家學(xué)習(xí)使用學(xué)習(xí)完請自行刪除，謝謝！本課件PPT僅供大家學(xué)習(xí)使用學(xué)習(xí)完請自行刪除，謝謝！《樹和二叉樹》幻燈片本課件PPT僅供大家學(xué)習(xí)使用課程回憶什么是稀疏矩陣稀疏矩陣表示廣義表定義課程回憶什么是稀疏矩陣本講目錄樹的定義和根本術(shù)語二叉樹樹的定義樹的基本術(shù)語二叉樹的定義二叉樹的性質(zhì)二叉樹的存儲結(jié)構(gòu)本講目錄樹的定義和根本術(shù)語樹的定義二叉樹的定本講重點、難點重點二叉樹的定義二叉樹的性質(zhì)二叉樹的存儲構(gòu)造難點二叉樹的定義二叉樹的性質(zhì)本講重點、難點重點樹的定義和根本術(shù)語樹的定義和根本術(shù)語二叉樹樹的定義樹的基本術(shù)語樹的定義和根本術(shù)語樹的定義和根本術(shù)語樹的定義樹的定義樹型結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)。直觀看來樹是以分支關(guān)系定義的層次結(jié)構(gòu)。樹型結(jié)構(gòu)在客觀世界中廣泛存在，如人類社會的族譜和各種社會組織機(jī)構(gòu)都可用樹來形象表示。樹在計算機(jī)領(lǐng)域中也有著廣泛的應(yīng)用，如在數(shù)據(jù)庫系統(tǒng)中，可用樹來組織信息；在分析算法的行為時，可用樹來描述其執(zhí)行過程。樹的定義樹型結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)。樹的定義例如：家族樹樹的定義例如：家族樹樹棧和隊列數(shù)組和廣義表線性表和廣義表數(shù)據(jù)結(jié)構(gòu)……線性表廣義表棧隊列……樹的定義例如本書的目錄樹棧和隊列數(shù)組和廣義表線性表和廣義表數(shù)據(jù)結(jié)構(gòu)……線性表廣義表樹的定義樹的定義樹是由n(n0)個結(jié)點組成的有限集合。如果n=0，稱為空樹；如果n>0，那么:有一個特定的稱之為根(root)的結(jié)點，它只有后繼，但沒有前驅(qū)；除根以外的其它結(jié)點劃分為m(m>0)個互不相交的有限集合T1,T2,…,Tm。每個集合本身又是一棵樹，并且稱之為根的子樹(subTree)。每棵子樹的根結(jié)點有且僅有一個直接前驅(qū)，但可以有0個或多個后繼。樹的定義是遞歸的。樹的定義樹的定義樹的定義例如圖(a)是一棵空樹，沒有結(jié)點圖(b)是一棵只有根結(jié)點的樹，根結(jié)點是A圖(c)是一棵有13個結(jié)點的樹，其中A是根結(jié)點三個互不相交的子集：T1={B,E,F,K,L},T2={C,G},T3={D,H,I,J,M}樹的定義例如圖(a)是一棵空樹，沒有結(jié)點樹的定義抽象數(shù)據(jù)類型樹的定義ADTTree{數(shù)據(jù)對象D：D是具有一樣特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：假設(shè)D為空集，那么稱為空樹；否那么:(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root,(2)當(dāng)n>1時，其余結(jié)點可分為m(m>0)個互不相交的有限集T1,T2,…,Tm,其中每一棵子集本身又是一棵符合本定義的樹，稱為根root的子樹。根本操作P：(見教材)}ADTTree樹的定義抽象數(shù)據(jù)類型樹的定義樹的表示樹的邏輯表示方法有多種，常見的有：樹形圖表示法嵌套集合表示法〔文氏圖表示法〕凹入表示法廣義表表示法樹的定義樹的表示樹的定義樹的根本術(shù)語根本術(shù)語結(jié)點：數(shù)據(jù)元素+假設(shè)干指向子樹的分支結(jié)點的度：分支的個數(shù)〔或子樹的個數(shù)〕葉子結(jié)點〔終端結(jié)點〕：度為零的結(jié)點分支結(jié)點〔非終端結(jié)點〕：度不等于零的結(jié)點樹的度：樹中所有結(jié)點的度的最大值孩子結(jié)點：結(jié)點的子樹的根結(jié)點為該結(jié)點的孩子結(jié)點雙親結(jié)點：與孩子結(jié)點相對應(yīng)的結(jié)點兄弟結(jié)點：同一個雙親的孩子結(jié)點之間的互稱祖先結(jié)點：從根結(jié)點起到該結(jié)點所經(jīng)分支上的所有結(jié)點子孫結(jié)點：以某結(jié)點為根的子樹中的任意結(jié)點樹的根本術(shù)語根本術(shù)語樹的根本術(shù)語根本術(shù)語層次：從根結(jié)點起，根結(jié)點為第一層，跟的孩子為第二層，依次類推假設(shè)根結(jié)點的層次為1,第l層的結(jié)點的子樹根結(jié)點的層次為l+1堂兄弟：雙親在同一層的結(jié)點互稱深度：樹中葉子結(jié)點所在的最大層次有序樹：子樹之間存在確定的次序關(guān)系無序樹：子樹之間不存在確定的次序關(guān)系森林：是m〔m≥0〕棵互不相交的樹的集合。任何一棵非空樹是一個二元組Tree=〔root，F(xiàn)〕其中：root被稱為根結(jié)點，F(xiàn)被稱為子樹森林CGFHIJMDEKLBFAroot樹的根本術(shù)語根本術(shù)語CGFHIJMDEKLBFAroot二叉樹樹的定義和根本術(shù)語二叉樹二叉樹的定義二叉樹的性質(zhì)二叉樹的存儲結(jié)構(gòu)二叉樹樹的定義和根本術(shù)語二叉樹的定義二叉樹的定義二叉樹的定義二叉樹是由n(n>=0)個結(jié)點的有限集合構(gòu)成，此集合或者為空集，或者由一個根結(jié)點及兩棵互不相交的左右子樹組成，并且左右子樹都是二叉樹。二叉樹的每個結(jié)點至多只有兩棵子樹〔結(jié)點的度最多為2〕。二叉樹的子樹有左右之分，其次序不能任意顛倒。根結(jié)點右子樹左子樹EFHKCBADGEF二叉樹的定義二叉樹的定義根結(jié)點右子樹左子樹EFHKCBADG二叉樹的定義抽象數(shù)據(jù)類型二叉樹的定義ADTBinaryTree{數(shù)據(jù)對象D：D是具有一樣特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：假設(shè)D為空集，那么稱為空二叉樹；否那么:(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root(2)當(dāng)n>1時，其余結(jié)點可分為2個互不相交的有限集Dl，Dr(3)假設(shè)Dl，Dr都不為空集，那么Dl，Dr本身又是一棵符合本定義的二叉樹，稱為根root的左右子樹。根本操作P：(見教材)}ADTBinaryTree二叉樹的定義抽象數(shù)據(jù)類型二叉樹的定義二叉樹的定義二叉樹的5種根本形態(tài)AABABACB

(b)根和空的左右子樹

(c)根和左子樹(d)根和右子樹(e)根和左右子樹

(a)空二叉樹二叉樹的定義二叉樹的5種根本形態(tài)AABABACB(5×3！=30棵二叉樹的定義例如：由三個結(jié)點組成的二叉樹的根本類型有幾種？由三個結(jié)點組成的二叉樹的根本形態(tài)有5種。如果這三個結(jié)點分別是A,B,C。那么可以組成幾棵二叉樹？5×3！=30棵二叉樹的定義例如：由三個結(jié)點組成的二叉樹的根二叉樹的性質(zhì)二叉樹的性質(zhì)性質(zhì)1：在二叉樹的第i層上至多有2i-1個結(jié)點。(i≥1)證明：用歸納法證明：歸納基：i=1層時，只有一個根結(jié)點，2i-1=20=1；歸納假設(shè)：假設(shè)對所有的j，1≤ji，命題成立;歸納證明：二叉樹上每個結(jié)點至多有兩棵子樹，那么第i層的結(jié)點數(shù)=2i-22=2i-1。按照題意，二叉樹除最后一層，其余每一層上的結(jié)點都有兩個孩子結(jié)點，那么每一層均比上一層的結(jié)點個數(shù)多一倍。按照等比數(shù)列的定義，每一項都可以看作是相應(yīng)每一層上的結(jié)點個數(shù)，那么，ai=ai*qi-1=2i-1二叉樹的性質(zhì)二叉樹的性質(zhì)用歸納法證明：按照題意，二叉樹除最后二叉樹的性質(zhì)性質(zhì)2：深度為k的二叉樹上至多含2k-1個結(jié)點〔k≥1〕證明：基于上一條性質(zhì)，深度為k

的二叉樹上的結(jié)點數(shù)至多為

20+21++2k-1=2k-1

二叉樹的性質(zhì)性質(zhì)2：深度為k的二叉樹上至多含2k-1個結(jié)點〔二叉樹的性質(zhì)性質(zhì)3：對任何一棵二叉樹，假設(shè)它含有n0個葉子結(jié)點、n2個度為2的結(jié)點，那么必存在關(guān)系式：n0=n2+1證明：設(shè)二叉樹上結(jié)點總數(shù)n=n0+n1+n2又二叉樹上分支總數(shù)B=n1+2n2而B=n-1=n0+n1+n2–1由此，n0=n2+1二叉樹的性質(zhì)性質(zhì)3：對任何一棵二叉樹，假設(shè)它含有n0個葉子滿二叉樹：指的是深度為k且含有2k-1個結(jié)點的二叉樹。完全二叉樹：樹中所含的n個結(jié)點和滿二叉樹中編號為1

至n

的結(jié)點一一對應(yīng)。123456789101112131415abcdefghij特點：每一層上的結(jié)點數(shù)都是最大結(jié)點數(shù)特點：葉子結(jié)點只能在層次最大的兩層出現(xiàn)任意結(jié)點，假設(shè)其右分支下的子孫最大層數(shù)為L,那么左分支下的子孫的最大層次為L或L+1兩類特殊的二叉樹二叉樹的性質(zhì)滿二叉樹：指的是深度為k且含有2k-1個結(jié)點的二叉樹。完全二性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為

log2n+1證明：設(shè)完全二叉樹的深度為k

那么根據(jù)第二條性質(zhì)得2k-1≤n<2k即k-1≤log2n<k

因為k

只能是整數(shù)，因此，k=log2n

+1二叉樹的性質(zhì)性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為證明：設(shè)完全二叉樹性質(zhì)5：假設(shè)對含n個結(jié)點的完全二叉樹從上到下且從左至右進(jìn)展1至n的編號，那么對完全二叉樹中任意一個編號為i的結(jié)點：假設(shè)i=1，那么該結(jié)點是二叉樹的根，無雙親,否那么，編號為i/2的結(jié)點為其雙親結(jié)點;假設(shè)2i>n，那么該結(jié)點無左孩子，

否那么，編號為2i的結(jié)點為其左孩子結(jié)點；假設(shè)2i+1>n，那么該結(jié)點無右孩子結(jié)點，

否那么，編號為2i+1的結(jié)點為其右孩子結(jié)點。二叉樹的性質(zhì)性質(zhì)5：假設(shè)對含n個結(jié)點的完全二叉樹從上到二叉樹的二叉樹的存儲構(gòu)造順序存儲構(gòu)造它是用一組連續(xù)的存儲單元存儲二叉樹的數(shù)據(jù)元素。必須把二叉樹的所有結(jié)點安排成為一個恰當(dāng)?shù)男蛄?，結(jié)點在這個序列中的相互位置能反映出結(jié)點之間的邏輯關(guān)系，用編號的方法