大學(xué)《數(shù)據(jù)結(jié)構(gòu)》第五章：樹(shù)和二叉樹(shù)-第一節(jié)-樹(shù)的基本概念和術(shù)語(yǔ)

本章概覽當(dāng)前講授一、知識(shí)結(jié)構(gòu)二、本章重難點(diǎn)本章重點(diǎn)是二叉樹(shù)的各種次序的遍歷及其應(yīng)用，二叉樹(shù)的線索化的方法及應(yīng)用、使用哈夫曼算法生成哈夫曼樹(shù)和構(gòu)造哈夫曼編碼，其中二叉樹(shù)的運(yùn)算，要求達(dá)到"綜合應(yīng)用"層次。難點(diǎn)是有關(guān)樹(shù)和二叉樹(shù)的應(yīng)用問(wèn)題的算法設(shè)計(jì)和實(shí)現(xiàn)。

第一節(jié)樹(shù)的基本概念和術(shù)語(yǔ)當(dāng)前講授一、引言樹(shù)形結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，樹(shù)中結(jié)點(diǎn)之間具有明確的層次關(guān)系，并且結(jié)點(diǎn)之間有分支，非常類似于真正的樹(shù)。樹(shù)形結(jié)構(gòu)在客觀世界中大量存在，如行政組織機(jī)構(gòu)和人類社會(huì)的家譜等都可用樹(shù)形結(jié)構(gòu)形象地表示。二、樹(shù)的定義1、樹(shù)(Tree)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集T，n=0時(shí)稱為空樹(shù)，任意非空樹(shù)（1）有且僅有一個(gè)特定的稱為根(Root)的結(jié)點(diǎn)；（2）n>1時(shí)，除根結(jié)點(diǎn)外的其余結(jié)點(diǎn)可分為m(m≥0)個(gè)互不相交的子集Tl，T2，…，Tm，其中每個(gè)子集本身又是一棵樹(shù)，并稱其為根的子樹(shù)(Subree)。2、從邏輯上看，樹(shù)形結(jié)構(gòu)具有以下特點(diǎn)：（1）任何非空樹(shù)中有且僅有一個(gè)結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)就是樹(shù)的根結(jié)點(diǎn)。（2）除根結(jié)點(diǎn)之外，其余所有結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)結(jié)點(diǎn)。（3）包括根結(jié)點(diǎn)在內(nèi)，每個(gè)結(jié)點(diǎn)可以有多個(gè)直接后繼結(jié)點(diǎn)。（4）樹(shù)形結(jié)構(gòu)是一種具有遞歸特征的數(shù)據(jù)結(jié)構(gòu)。（5）樹(shù)形結(jié)構(gòu)中的數(shù)據(jù)元素之間存在的關(guān)系通常是一對(duì)多，或者多對(duì)一的關(guān)系。三、樹(shù)的表示法1、樹(shù)結(jié)構(gòu)2、嵌套集合3、凹形表示法4、廣義表表示法（A（B（E，（F（J,K））），C（G），D（H，I）））四、樹(shù)結(jié)構(gòu)的基本術(shù)語(yǔ)（1）結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹(shù)的個(gè)數(shù)。如A的度為3，E的度為2。（2）樹(shù)的度：樹(shù)中結(jié)點(diǎn)度的最大值。如圖4-1所示的樹(shù)的度為3。（3）葉子（終端結(jié)點(diǎn)）：度為0的結(jié)點(diǎn)。如K，L，F(xiàn)，J等結(jié)點(diǎn)都是葉子結(jié)點(diǎn)。（4）分支結(jié)點(diǎn)（非終端結(jié)點(diǎn)）：度不為0的結(jié)點(diǎn)。除根結(jié)點(diǎn)之外的分支結(jié)點(diǎn)統(tǒng)稱為內(nèi)部結(jié)點(diǎn)。根結(jié)點(diǎn)又稱為開(kāi)始結(jié)點(diǎn)。如A，B、I等結(jié)點(diǎn)是分支結(jié)點(diǎn)。（5）孩子：結(jié)點(diǎn)的直接后繼（即結(jié)點(diǎn)的子樹(shù)的根）。如B是A的孩子，N是I的孩子。（6）雙親：結(jié)點(diǎn)的直接前趨。如B的雙親是A，N的雙親是I。（7）兄弟：同一雙親的孩子互為兄弟。如B、C，D互為兄弟，M，N互為兄弟。（8）子孫：一棵樹(shù)上的任何結(jié)點(diǎn)（不包括根結(jié)點(diǎn)）稱為根的子孫。如圖中其它結(jié)點(diǎn)都是根結(jié)點(diǎn)A的子孫。（9）祖先：從根結(jié)點(diǎn)開(kāi)始到該結(jié)點(diǎn)連線上的所有結(jié)點(diǎn)（除該結(jié)點(diǎn)）都是該結(jié)點(diǎn)的祖先。如N的祖先是I，C，A。（10）路徑：若樹(shù)中存在一個(gè)結(jié)點(diǎn)序列k1，k2，…，ki，使得ki是ki+1的雙親(1≤i<j)，則稱該結(jié)點(diǎn)序列是從kl到kj的一條路徑或道路。路徑的長(zhǎng)度指路徑所經(jīng)過(guò)的邊（即連接兩個(gè)結(jié)點(diǎn)的線段）的數(shù)目，等于j-1。注意：若一個(gè)結(jié)點(diǎn)序列是路徑，則在樹(shù)的樹(shù)形圖表示中，該結(jié)點(diǎn)序列"自上而下"地通過(guò)路徑上的每條邊。從樹(shù)的根結(jié)點(diǎn)到樹(shù)中其余結(jié)點(diǎn)均存在一條唯一的路徑。（11）結(jié)點(diǎn)的層：設(shè)根結(jié)點(diǎn)的層數(shù)為1，其余結(jié)點(diǎn)的層數(shù)等于雙親結(jié)點(diǎn)的層數(shù)加1。如B的層數(shù)是2，N的層數(shù)是4。（12）樹(shù)的高度（或深度）：樹(shù)中所有結(jié)點(diǎn)層數(shù)的最大值。圖所示的樹(shù)的高度為4。（13）有序樹(shù)和無(wú)序樹(shù)：將樹(shù)中每個(gè)結(jié)點(diǎn)的各子樹(shù)看成是從左到右有次序的(即不能互換)，則稱該樹(shù)為有序樹(shù)；否則稱為無(wú)序樹(shù)。（14）森林：是m(m≥0)棵互不相交的樹(shù)的集合。樹(shù)和森林的概念相近，刪去一棵樹(shù)的根，就得到一個(gè)森林；反之，加上一個(gè)結(jié)點(diǎn)作樹(shù)根，森林就變?yōu)橐豢脴?shù)。五、樹(shù)的性質(zhì)性質(zhì)一：非空樹(shù)中的結(jié)點(diǎn)總數(shù)等于樹(shù)中所有結(jié)點(diǎn)的度之和加1。證明：根據(jù)樹(shù)的定義，在一棵樹(shù)中，除根結(jié)點(diǎn)以外，每個(gè)結(jié)點(diǎn)有且僅有一個(gè)雙親結(jié)點(diǎn)，即每個(gè)結(jié)點(diǎn)與指向它的一個(gè)分支結(jié)點(diǎn)一一對(duì)應(yīng)，因而除了樹(shù)的根結(jié)點(diǎn)之外的結(jié)點(diǎn)數(shù)等于樹(shù)中所有結(jié)點(diǎn)的分支數(shù)（度數(shù)），由此可得知樹(shù)中的結(jié)點(diǎn)總數(shù)應(yīng)為所有結(jié)點(diǎn)的度之和加1。性質(zhì)二：度為k的非空樹(shù)的第i層最多有ki-1個(gè)結(jié)點(diǎn)（i≥1）。證明：（略）性質(zhì)三：深度為h的k叉樹(shù)最多有

個(gè)結(jié)點(diǎn)。證明：顯然，只有當(dāng)深度為h的k叉樹(shù)上的每一層都達(dá)到該層最大結(jié)點(diǎn)總數(shù)時(shí)，該樹(shù)的結(jié)點(diǎn)總數(shù)將達(dá)到最大，因此，有證畢【真題選解】（例題?填空題）已知在一棵含有n個(gè)結(jié)點(diǎn)的樹(shù)中，只有度為k的分支結(jié)點(diǎn)和度為0的葉子結(jié)點(diǎn)，則該樹(shù)中含有的葉子結(jié)點(diǎn)的數(shù)目為

。隱藏答案【答案】((k-1)×n+1)／k【解析】設(shè)度為k的分支結(jié)點(diǎn)數(shù)為nk，度為0的葉子結(jié)點(diǎn)數(shù)為n0，樹(shù)中總分支數(shù)為B。除根結(jié)點(diǎn)之外，其他每個(gè)結(jié)點(diǎn)都有且僅有一個(gè)進(jìn)入支，而這些進(jìn)入支是由度為k的結(jié)點(diǎn)發(fā)出的，度為k的結(jié)點(diǎn)總共發(fā)出k×nk個(gè)分支。顯然有：nk=n-n0