對于線性數(shù)據(jù)結構，每個元素都有唯一的前驅（第一個除外）和后繼（最后一個除外），但是在現(xiàn)實應用中，一些問題的數(shù)據(jù)元素之間的關系就不這樣簡單。

本章學習一種非線性數(shù)據(jù)結構-----樹，數(shù)據(jù)元素之間是一種層次關系，元素有且只有一個前驅，但可以有多個后繼樹和二叉樹樹的概念和基本術語二叉樹二叉樹遍歷線索二叉樹樹與森林霍夫曼樹

樹和二叉樹1樹的概念和基本術語樹的定義

樹是由n(n0)個結點的有限集合。如果n=0，稱為空樹；如果n>0，則

有且僅有一個特定的稱之為根(Root)的結點，它只有直接后繼，但沒有直接前驅；

當n>1，除根以外的其它結點劃分為m(m>0)個互不相交的有限集

T1,T2,…,Tm，其中每個集合本身又是一棵樹，并且稱為根的子樹(SubTree)ACGBDEFKLHMIJ例如A只有根結點的樹有13個結點的樹其中:A是根,其余結點分成三個互不相交的子集，T1={B,E,F,K,L}；T2={C,G}；T3={D,H,I,J,M},T1,T2,T3都是根A的子樹，且本身也是一棵樹樹的基本術語樹的結點：包含一個數(shù)據(jù)元素及若干指向子樹的分支；孩子結點：結點的子樹的根稱為該結點的孩子雙親結點：B結點是A結點的孩子，則A結點是B結點的雙親ACGBDEFKLHMIJ兄弟結點：同一雙親的孩子結點

堂兄結點：雙親在同一層的結點互為堂兄弟結點層次

：根結點的層定義為1根的孩子為第二層結點依此類推ACGBDEFKLHMIJ樹的基本術語樹的高度（或深度）：樹中結點的最大層次結點的度：結點子樹的個數(shù)樹的度：樹內(nèi)各結點的度的最大值葉子結點：也叫終端結點，是度為0的結點分枝結點：也叫非終端結點，度不為0的結點有序樹：子樹有序的樹，（子樹不能互換）如：家族樹無序樹：不考慮子樹的順序ACGBDEFKLHMIJ樹的基本術語路徑：樹中的k個結點n1,n2，…，nk，滿足ni

是ni+1的雙親，n1到nk有一條路徑路徑長度：分支數(shù)＝路徑上結點個數(shù)一1根沒有雙親，葉子沒有孩子；vi是vj

的雙親，則L(vi)=L(vj)-1;

堂兄弟的雙親是兄弟關系嗎？有序樹和無序樹的區(qū)別注意ACGBDEFKLHMIJ任何一棵非空樹是一個二元組

Tree=（root，F(xiàn)）其中：root被稱為根結點，

F被稱為子樹森林是m（m≥0）棵互不相交的樹的集合ArootBEFKLCGDHIJMF森林對比樹型結構和線性結構的結構特點~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~線性結構樹型結構第一個數(shù)據(jù)元素

(無前驅)

根結點

(無前驅)最后一個數(shù)據(jù)元素

(無后繼)多個葉子結點

(無后繼)其它數(shù)據(jù)元素(一個前驅、一個后繼)其它數(shù)據(jù)元素(一個前驅、多個后繼)樹的常見表示方法1.直觀表示法：用圓圈表示結點，元素寫在圓圈中，連線表示元素之間的關系.根在上，葉子在下（即樹向下生長）2、集合表示法：根據(jù)樹的集合定義，寫出集合劃分

3、文氏圖表示法：

集合表示的一種直觀表示，用圖表示集合樹的常見表示法4、目錄表示法：

將一棵樹描述為一本書，書--章--節(jié)--小節(jié)樹的常見表示法5、廣義表表示法：將一棵樹描述為一個廣義表，子樹就對應子表人們最常用的是第一種，但是不適合計算機！樹的常見表示法樹的基本操作

InitTree（＆T）操作結果：構造空樹T。

DestroyTree（＆T）初始條件：樹T存在。操作結果：銷毀樹T。

CreateTree（＆T，definition）初始條件：definition給出樹T的定義。操作結果：按definition構造樹T。

ClearTree（＆T）初始條件：樹T存在。操作結果：將樹T清為空樹樹的基本操作

TreeEmpty（T）初始條件：樹T存在。操作結果：若T為空樹，則返回ture，否則false。

TreeDepth（T）初始條件：樹T存在。操作結果：返回T的深度。

Root（T）初始條件：樹T存在。操作結果：返回T的根。

Value（T,Cur_e）初始條件：樹T存在，cur＿e是T中某個結點。操作結果：返回cur＿e的值Assign（T，cur_e，value）初始條件：樹T存在，cur＿e是T中某個結點。操作結果：結點cur_e賦值為value。

Parent（T，cur＿e）初始條件：樹T存在，cur＿e是T中某個結點。操作結果：若cur＿e是T的非根結點，則返回它的雙親，否則函數(shù)值為“空”。

Rightsibling（T，cur＿e）初始條件：樹T存在，cur＿e是T中某個結點操作結果：若cur＿e有右兄弟，則返回它的右兄弟，否則函數(shù)值為“空”。

InsertChild（＆T，＆p，i，c）初始條件：樹T存在，p指向T中某個結點，1≤i≤p所指結點的度＋1，非空樹c與T不相交。操作結果：插入c為T中p指結點的第i棵子樹。DeleteChild（＆T，＆p，i）初始條件：樹T存在，p指向T中某個結點，1≤i≤p指結點的度。操作結果：刪除T中p所指結點的第i棵子樹。

TraverseTree（T，visit（））初始條件：樹T存在，visit是對結點操作的應用函數(shù)。操作結果：按某種次序對T的每個結點調(diào)用函數(shù)visit()一次且至多一次.一旦visit（）失敗，則操作失敗LeftChild（T，cur＿e）

初始條件：樹T存在，cur＿e是T中某個結點。操作結果：若cur＿e是T的非葉子結點，則返回它的最左孩子，否則返回“空”

6.2二叉樹一二叉樹的概念二二叉樹的性質三二叉樹的存儲結構定義:二叉樹或為空樹；或是由一個根結點加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成ABCDEFGHK根結點左子樹右子樹2二叉樹(BinaryTree)特點:每個結點至多只有兩棵子樹（二叉樹中不存在度大于2的結點）二叉樹的五種基本形態(tài)N空樹只含根結點NNNLRR右子樹為空樹L左子樹為空樹左右子樹均不為空樹應用舉例

e

d

c

b

f

a

+

*

/

-

-

a+b*(c-d)-e/f例可以用二叉樹表示表達式性質1 在二叉樹的第i層上至多有2i－1個結點(i

1)

[證明用歸納法]證明：當i=1時，只有根結點，2i-1=20=1。假設對所有j，i>j1，命題成立，即第j層上至多有2j-1

個結點。由歸納假設第i-1

層上至多有2i－2個結點。由于二叉樹的每個結點的度至多為2，故在第i層上的最大結點數(shù)為第i-1層上的最大結點數(shù)的2倍，即2*2i－2=2i-1。性質性質2 深度為k的二叉樹至多有2k-1個結點(k1)證明：由性質1可見，深度為k的二叉樹的最大結點數(shù)為

＝20+21+…+2k-1=2k-1＝性質3 對任何一棵二叉樹T,如果其葉結點數(shù)為n0,度為2的結點數(shù)為n2,則n0＝n2＋1.證明：若度為1的結點有n1

個，總結點個數(shù)為n，總邊數(shù)為e，則根據(jù)二叉樹的定義，

n=n0+n1+n2e=2n2+n1=n-1因此，有2n2+n1=n0+n1+n2

-1n2=n0

-1n0=n2+1定義1滿二叉樹(FullBinaryTree)

一棵深度為k且有2k-1個結點的二叉樹稱為滿二叉樹兩種特殊形態(tài)的二叉樹6217543891011131412滿二叉樹152154367216543非完全二叉樹定義2完全二叉樹(CompleteBinaryTree)

若設二叉樹的高度為h，則共有h層。除第h層外，其它各層(0h-1)的結點數(shù)都達到最大個數(shù)，第h層從右向左連續(xù)缺若干結點，這就是完全二叉樹。621754389101112完全二叉樹性質4

具有n(n0)個結點的完全二叉樹的深度為log2(n)＋1

證明： 設完全二叉樹的深度為h，則根據(jù)性質2和完全二叉樹的定義有

2h－1

-1<n2h-1或2h－1

n<2h取對數(shù)h－1<log2nh，又h是整數(shù)，因此有h=log2(n)

＋1性質5：在完全二叉樹中編號（1開始）為i的結點，1）若有左孩子，則左孩編號為2i；2）若有右孩子，則有孩子結點編號為2i+1；3）若有雙親，則雙親結點編號為

i/2；2i+2

2i2i+1

2i+22i+3i+1

2i2i+1iii+1二叉樹也可以采用兩種存儲方式：順序存儲結構和鏈式存儲結構。順序存儲結構這種存儲結構適用于完全二叉樹其存儲形式為：用一組連續(xù)的存儲單元按照完全二叉樹的每個結點編號的順序存放結點二叉樹的存儲結構一般二叉樹的順序表示ABCDEFGHIJABDHIJEFGC順序表示IABCFEDGH9J完全二叉樹的順序表示ABCD0EFGH0000IJ--------二叉樹的順序存儲表示------------#defineMAX_TREE_SIZE100//二叉樹的最大結點數(shù)

typedef

TElemType

SqBiTree[MAX_TREE_SIZE];//0號單元存放根結點

SqBiTree

bt;最壞情況：深度為k的且只有k個結點的單支樹需要長度為2k-1的一維數(shù)組。鏈式存儲結構

在順序存儲結構中，利用編號表示元素的位置及元素之間孩子或雙親的關系，因此對于非完全二叉樹，需要將空缺的位置用特定的符號填補，若空缺結點較多，勢必造成空間利用率的下降。在這種情況下，就應該考慮使用鏈式存儲結構常見的二叉樹結點結構如下所示：lChild

data

rChild其中，Lchild和Rchild是分別指向該結點左孩子和右孩子的指針，data是數(shù)據(jù)元素的內(nèi)容。類型定義為：

typedef

struct

BiTNode{

TElemTypedata;

struct

BiTNode

*Lchild,*Rchlid;}BTNode,*BTree;GHDEFBCA^G^^H^^D^E^F^B^CABT這種存儲結構的特點是尋找孩子結點容易，雙親比較困難。因此，若需要頻繁地尋找雙親，可以給每個結點添加一個指向雙親結點的指針域，其結點結構如下所示lChilddataparentrChild

typedef

struct

TriTNode

{//結點結構

TElemType