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

本章概覽當前講授一、知識結構二、本章重難點本章重點是二叉樹的各種次序的遍歷及其應用，二叉樹的線索化的方法及應用、使用哈夫曼算法生成哈夫曼樹和構造哈夫曼編碼，其中二叉樹的運算，要求達到"綜合應用"層次。難點是有關樹和二叉樹的應用問題的算法設計和實現(xiàn)。

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

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

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