4-4二叉樹的邏輯結(jié)構(gòu)v第四章樹和二叉樹二叉樹的定義二叉樹的基本性質(zhì)二叉樹的抽象數(shù)據(jù)類型定義學(xué)什么？二叉樹的構(gòu)造二叉樹的遍歷操作4-4-1二叉樹的定義v第四章樹和二叉樹二叉樹的定義二叉樹：是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的、分別稱為根結(jié)點(diǎn)的左子樹和右子樹的二叉樹組成。二叉樹是度為2的樹嗎？AB二叉樹是度小于等于2的樹嗎？ABACBDEFGACBDEFG二叉樹有什么特點(diǎn)？（1）每個(gè)結(jié)點(diǎn)最多有兩棵子樹（2）二叉樹是有序的，其次序不能任意顛倒

為什么要研究二叉樹？（1）二叉樹是最簡單的樹結(jié)構(gòu)（2）將樹轉(zhuǎn)換為二叉樹，

從而利用二叉樹解決樹的有關(guān)問題二叉樹的特點(diǎn)斜樹斜樹：左斜樹和右斜樹的統(tǒng)稱左斜樹：所有結(jié)點(diǎn)都只有左子樹的二叉樹ABD右斜樹：所有結(jié)點(diǎn)都只有右子樹的二叉樹ABD斜樹有什么特點(diǎn)呢？（1）每一層只有一個(gè)結(jié)點(diǎn)（2）結(jié)點(diǎn)個(gè)數(shù)與其深度相同斜樹是樹結(jié)構(gòu)的特例，是從樹結(jié)構(gòu)退化成了線性結(jié)構(gòu)滿二叉樹滿二叉樹：所有分支結(jié)點(diǎn)都存在左子樹和右子樹，并且所有葉子都在同一層的二叉樹ABCDEFHIJKLMNOGABCDEFLMG所有分支結(jié)點(diǎn)都有左右子樹，但葉子不在同一層滿二叉樹有什么特點(diǎn)呢？（1）葉子只能出現(xiàn)在最下一層滿二叉樹是樹結(jié)構(gòu)的特例，是最豐滿的二叉樹ABCDEFHIJKLMNOG（4）在同樣深度的二叉樹中葉子結(jié)點(diǎn)個(gè)數(shù)最多（2）只有度為0和度為2的結(jié)點(diǎn)（3）在同樣深度的二叉樹中結(jié)點(diǎn)個(gè)數(shù)最多滿二叉樹滿二叉樹：所有分支結(jié)點(diǎn)都存在左子樹和右子樹，并且所有葉子都在同一層上的二叉樹L完全二叉樹完全二叉樹：在滿二叉樹中，從最后一個(gè)結(jié)點(diǎn)開始，連續(xù)去掉任意個(gè)結(jié)點(diǎn)得到的二叉樹ABCDEFHIJKMNOGABCDEFHIJKMG完全二叉樹有什么特點(diǎn)呢？（1）葉子結(jié)點(diǎn)只能出現(xiàn)在最下兩層且最下層的葉子結(jié)點(diǎn)都集中在二叉樹的左面ABCDEFHIJG（3）深度為k

的完全二叉樹在

k-1層上一定是滿二叉樹（2）完全二叉樹中如果有度為1的結(jié)點(diǎn)，只可能有一個(gè)，且該結(jié)點(diǎn)只有左孩子（4）在同樣結(jié)點(diǎn)個(gè)數(shù)的二叉樹中，完全二叉樹的深度最小完全二叉樹完全二叉樹：在滿二叉樹中，從最后一個(gè)結(jié)點(diǎn)開始，連續(xù)去掉任意個(gè)結(jié)點(diǎn)得到的二叉樹4-4-2二叉樹的基本性質(zhì)v第四章樹和二叉樹二叉樹的性質(zhì)性質(zhì)5-1：在一棵二叉樹中，如果葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則有:n0＝n2＋1ACBE證明:設(shè)n為二叉樹的結(jié)點(diǎn)總數(shù)，n1為二叉樹中度為1的結(jié)點(diǎn)數(shù)，則有：

n＝n0＋n1＋n2

在二叉樹中，除了根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都有唯一的一個(gè)分枝進(jìn)入，一個(gè)度為1的結(jié)點(diǎn)射出一個(gè)分枝，一個(gè)度為2的結(jié)點(diǎn)射出兩個(gè)分枝，所以有：

n＝n1＋2n2＋1兩式聯(lián)立，可以得到：

n0＝n2＋1性質(zhì)5-2：二叉樹的第

i

層上最多有2i-1個(gè)結(jié)點(diǎn)（i≥1）證明：采用歸納法證明。當(dāng)

i=1時(shí)，只有一個(gè)根結(jié)點(diǎn)，而2i-1=20=1，結(jié)論成立。假設(shè)

i=k時(shí)結(jié)論成立，即第

k層上最多有2k-1個(gè)結(jié)點(diǎn)。考慮

i=k+1時(shí)的情形。由于第

k+1層上的結(jié)點(diǎn)是第

k層上結(jié)點(diǎn)的孩子，而二叉樹中每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子，故在第

k+1層上的最多大結(jié)點(diǎn)個(gè)數(shù)有2×2k-1＝2k個(gè)結(jié)點(diǎn)，則在

i=k+1時(shí)結(jié)論也成立。由此，結(jié)論成立。二叉樹的性質(zhì)性質(zhì)5-3：一棵深度為k

的二叉樹中，最多有2k-1個(gè)結(jié)點(diǎn)證明：設(shè)深度為k的二叉樹中結(jié)點(diǎn)個(gè)數(shù)最多為n，則深度為k且具有2k-1個(gè)結(jié)點(diǎn)的二叉樹一定是滿二叉樹二叉樹的性質(zhì)證明：設(shè)具有n

個(gè)結(jié)點(diǎn)的完全二叉樹的深度為k，則2k-1-12k-1…2k-1第k層…第k-1層對(duì)不等式取對(duì)數(shù)，有：

k-1≤log2n＜k即：

log2n＜k≤log2n+1二叉樹的性質(zhì)性質(zhì)5-4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n+1。由于k

是整數(shù)，故必有

k＝log2n+1性質(zhì)5-5：對(duì)一棵具有n

個(gè)結(jié)點(diǎn)的完全二叉樹中從1開始按層序編號(hào)，對(duì)于編號(hào)為i（1≤i≤n）的結(jié)點(diǎn)（簡稱結(jié)點(diǎn)i），有：（1）如果i＞1，則結(jié)點(diǎn)i

的雙親結(jié)點(diǎn)的編號(hào)為i/2，否則結(jié)點(diǎn)i

無雙親結(jié)點(diǎn)（2）如果2i≤n，則結(jié)點(diǎn)i

的左孩子的編號(hào)為2i，否則結(jié)點(diǎn)i

無左孩子（3）如果2i+1≤n，則結(jié)點(diǎn)i

的右孩子的編號(hào)為2i+1，否則結(jié)點(diǎn)i

無右孩子12345689107二叉樹的性質(zhì)4-4-3二叉樹的抽象數(shù)據(jù)類型定義v第四章樹和二叉樹二叉樹的抽象數(shù)據(jù)類型定義ADTBiTreeDataModel

二叉樹由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的左右子樹構(gòu)成，結(jié)點(diǎn)具有層次關(guān)系OperationInitBiTree：初始化一棵空的二叉樹

CreateBiTree：建立一棵二叉樹

DestroyBiTree：銷毀一棵二叉樹PreOrder：前序遍歷二叉樹InOrder：中序遍歷二叉樹PostOrder：后序遍歷二叉樹LevelOrder：層序遍歷二叉樹endADT簡單起見，只討論二叉樹的遍歷二叉樹的遍歷二叉樹的遍歷：從根結(jié)點(diǎn)出發(fā)，按照某種次序訪問樹中所有結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)僅被訪問一次抽象操作，可以是對(duì)結(jié)點(diǎn)進(jìn)行的各種處理，這里簡化為輸出結(jié)點(diǎn)的數(shù)據(jù)限定先左后右：先序、中序、后序根結(jié)點(diǎn)D左子樹L右子樹R二叉樹按照什么次序?qū)Χ鏄溥M(jìn)行遍歷呢？二叉樹的遍歷方式：DLR、LDR、LRD、DRL、RDL、RLD

層序遍歷：按二叉樹的層序編號(hào)的次序訪問各結(jié)點(diǎn)二叉樹的先序遍歷操作定義：若二叉樹為空，則空操作返回；否則：（1）訪問根結(jié)點(diǎn)（2）先序遍歷根結(jié)點(diǎn)的左子樹（3）先序遍歷根結(jié)點(diǎn)的右子樹ACBDEFG先序：ABDGCEF二叉樹的遍歷二叉樹的中序遍歷操作定義：若二叉樹為空，則空操作返回；否則：（1）中序遍歷根結(jié)點(diǎn)的左子樹（2）訪問根結(jié)點(diǎn)（3）中序遍歷根結(jié)點(diǎn)的右子樹中序：DGBAECF二叉樹的后序遍歷操作定義：若二叉樹為空，則空操作返回；否則：（1）后序遍歷根結(jié)點(diǎn)的左子樹（2）后序遍歷根結(jié)點(diǎn)的右子樹（3）訪問根結(jié)點(diǎn)ACBDEFG后序：GDBEFCA二叉樹的遍歷層序：ABCDEFG二叉樹的層序遍歷操作定義：從二叉樹的根結(jié)點(diǎn)開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問若已知一棵二叉樹的先序（或中序，或后序，或?qū)有颍┬蛄校芊裎ㄒ淮_定這棵二叉樹呢？ABCABC先序遍歷序列：ABC若已知一棵二叉樹的先序序列和后序序列，能否唯一確定這棵二叉樹呢？后序遍歷序列：CBA二叉樹的構(gòu)造先序：ABCDEFG

HI中序：BCA

EDGHFIADEFG

HIBC先序：BC中序：BC先序：DEFGHI中序：EDGHFIDEFGHIABC二叉樹的構(gòu)造例4-1已知一棵二叉樹的先序遍歷序列和中序遍歷序列分別為ABCDEFGH和CDBAFEHG，請(qǐng)確定該二叉樹。先序：FG

HI中序：GHFIADEBCFGIH層序：

ABCDEFGHI中序：

D