數(shù)據(jù)結(jié)構(gòu)課件：二叉樹的基本性質(zhì)

二叉樹的基本性質(zhì)

本講要點(diǎn)二叉樹的定義

二叉樹的5個(gè)基本性質(zhì)研究二叉樹的意義？二叉樹的結(jié)構(gòu)相對(duì)簡(jiǎn)單，其運(yùn)算也自然簡(jiǎn)單，便于初學(xué)者入門。由于多叉樹可以借助一定的規(guī)則轉(zhuǎn)換為二叉樹，因此二叉樹結(jié)構(gòu)在應(yīng)用中具有非常重要的地位。

1.二叉樹的定義由n（n≥0）個(gè)結(jié)點(diǎn)組成的有限集合。若n＝0，稱為空樹?；蛘呤怯梢粋€(gè)根結(jié)點(diǎn)和兩棵互不相交的稱為左子樹和右子樹的二叉樹組成。二叉樹的定義是遞歸的。1.二叉樹的定義特點(diǎn)？每個(gè)結(jié)點(diǎn)的度只可能是（

）；二叉樹是（有/無）序樹。

0，1，2有即使某結(jié)點(diǎn)只有一棵子樹，也要區(qū)分該子樹是左子樹還是右子樹1.二叉樹的定義二叉樹的5種基本形態(tài)練一練：畫出具有3個(gè)結(jié)點(diǎn)的樹和具有3個(gè)結(jié)點(diǎn)的二叉樹的形態(tài)二叉樹和樹是兩種樹結(jié)構(gòu)。2.二叉樹的基本性質(zhì)性質(zhì)1

：二叉樹的第i層上最多有2i-1個(gè)結(jié)點(diǎn)（i≥1）。推廣：高度為h的k叉樹中，第i層上最多具有（）個(gè)結(jié)點(diǎn)。ki－12.二叉樹的基本性質(zhì)性質(zhì)2：一棵高度為k的二叉樹中，最多有（）個(gè)結(jié)點(diǎn)，

最少有（）個(gè)結(jié)點(diǎn)。特殊的二叉樹1滿二叉樹：高度為k且具有2k-1個(gè)結(jié)點(diǎn)的二叉樹2k-1k特點(diǎn)？分支結(jié)點(diǎn)：葉子：結(jié)點(diǎn)的度：所有分支結(jié)點(diǎn)都存在左子樹和右子樹葉子只能出現(xiàn)在最下一層只有度為0和度為2的結(jié)點(diǎn)2.二叉樹的基本性質(zhì)特殊的二叉樹1滿二叉樹？A1523467BCDEFGLM89不是滿二叉樹。高度為4，應(yīng)該具有24-1個(gè)結(jié)點(diǎn)。滿二叉樹在同樣高度的二叉樹中結(jié)點(diǎn)個(gè)數(shù)最多滿二叉樹在同樣高度的二叉樹中葉子結(jié)點(diǎn)個(gè)數(shù)最多2.二叉樹的基本性質(zhì)特殊的二叉樹2完全二叉樹對(duì)一棵具有n個(gè)結(jié)點(diǎn)的二叉樹按層序編號(hào)，如果編號(hào)為i（1≤i≤n）的結(jié)點(diǎn)與同樣高度的滿二叉樹中編號(hào)為i的結(jié)點(diǎn)在二叉樹中的位置完全相同。

2.二叉樹的基本性質(zhì)8A1523467BCDEFGHIK在滿二叉樹中，從最后一個(gè)結(jié)點(diǎn)開始，連續(xù)去掉任意個(gè)結(jié)點(diǎn)，即是一棵完全二叉樹。A1523467910BCDEFGHIJK11L12M13N14O15不是完全二叉樹，結(jié)點(diǎn)10與滿二叉樹中的結(jié)點(diǎn)10不是同一個(gè)結(jié)點(diǎn)89102.二叉樹的基本性質(zhì)8A1523467BCDEFGHIJA1523467910BCDEFGHIJK11L12M13N14O158910特點(diǎn)？葉子結(jié)點(diǎn)：如果有度為1的結(jié)點(diǎn)：高度為k的完全二叉樹在k-1層上：只能出現(xiàn)在最下兩層，且最下層的葉子結(jié)點(diǎn)都集中在二叉樹的左部只可能有一個(gè)，且該結(jié)點(diǎn)只有左孩子一定是滿二叉樹2.二叉樹的基本性質(zhì)特殊的二叉樹3斜樹所有結(jié)點(diǎn)都只有左子樹的二叉樹稱為左斜樹；所有結(jié)點(diǎn)都只有右子樹的二叉樹稱為右斜樹；左斜樹和右斜樹統(tǒng)稱為斜樹。ABCABC練一練：性質(zhì)2：一棵高度為k的二叉樹中，最多有2k-1個(gè)結(jié)點(diǎn)，最少有k個(gè)結(jié)點(diǎn)。高度為k且具有2k-1個(gè)結(jié)點(diǎn)的二叉樹（一定/不一定）是滿二叉樹。高度為k且具有k個(gè)結(jié)點(diǎn)的二叉樹（一定/不一定）是斜樹。

√√2.二叉樹的基本性質(zhì)性質(zhì)3：在一棵二叉樹中，如果葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則有:

n0＝n2＋1。證明:

抓住結(jié)點(diǎn)總數(shù)=結(jié)點(diǎn)總度數(shù)+1

n0+n1+n2=n1+2*n2+1

n0=n2+1推廣：已知一棵度為m的樹中有n1個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，…nm個(gè)度為m的結(jié)點(diǎn)，問該樹中有多少個(gè)葉子結(jié)點(diǎn)？證明：抓住結(jié)點(diǎn)總數(shù)=結(jié)點(diǎn)總度數(shù)+1

n0+n1+n2+…+nm=n1+2*n2+…+m*nm+1=>n0=1+n2+…+(m-1)nm練一練任一個(gè)有n個(gè)結(jié)點(diǎn)的二叉樹，有m個(gè)葉子結(jié)點(diǎn)，則非葉子結(jié)點(diǎn)數(shù)（度為2）有多少個(gè)？因?yàn)閚0＝n2+1

n2＝n0–1

n2＝m-1練一練在有n個(gè)結(jié)點(diǎn)的滿二叉樹中，有多少個(gè)葉子結(jié)點(diǎn)？n0＝n2+1

因?yàn)樵跐M二叉樹中沒有度為1的結(jié)點(diǎn)，只有度為0的葉子結(jié)點(diǎn)和度為2的分支結(jié)點(diǎn)，所以，n＝n0+n2

葉子結(jié)點(diǎn)n0＝(n+1)/22.二叉樹的基本性質(zhì)證明：假設(shè)具有n個(gè)結(jié)點(diǎn)的完全二叉樹的高度為k，根據(jù)完全二叉樹的定義和性質(zhì)2，有下式成立

2k-1≤n＜2k

2k-1-1…2k-12k-1———第k-1層———第k層…最少結(jié)點(diǎn)數(shù)最多結(jié)點(diǎn)數(shù)性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的高度為log2n+1。2.二叉樹的基本性質(zhì)證明：假設(shè)具有n個(gè)結(jié)點(diǎn)的完全二叉樹的高度為k，根據(jù)完全二叉樹的定義和性質(zhì)2，有下式成立

2k-1≤n＜2k性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的高度為log2n+1。log2n+1[log2n]log2n[log2n]+1k所在區(qū)間對(duì)不等式取對(duì)數(shù)，有：

k-1≤log2n＜k即：

log2n＜k≤log2n+1由于k是整數(shù)，故必有k＝log2n+1。2.二叉樹的基本性質(zhì)性質(zhì)5：對(duì)一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹中從1開始按層序編號(hào)，則對(duì)于任意的序號(hào)為i（1≤i≤n）的結(jié)點(diǎn)（簡(jiǎn)稱為結(jié)點(diǎn)i），有點(diǎn)i的雙親結(jié)點(diǎn)為（）結(jié)點(diǎn)i的左孩子為（）結(jié)點(diǎn)i的右孩子為（）。i/22i2i＋12.二叉樹的基本性質(zhì)性質(zhì)5：對(duì)一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹中從1開始按層序編號(hào)，則對(duì)于任意的序號(hào)為i（1≤i≤n）的結(jié)點(diǎn)（簡(jiǎn)稱為結(jié)點(diǎn)i），有果i＞1，則結(jié)點(diǎn)i的雙親結(jié)點(diǎn)的序號(hào)為

i/2；

如果i＝1，則結(jié)點(diǎn)i是根結(jié)點(diǎn)，無雙親結(jié)點(diǎn)。如果2i≤n，則結(jié)點(diǎn)