第六章樹和二叉樹（一）6.1樹的類型定義6.2二叉樹的類型定義6.3二叉樹的存儲結構6.4二叉樹的遍歷6.5線索二叉樹6.6樹和森林的表示方法6.7

樹和森林的遍歷6.8哈夫曼樹與哈夫曼編碼數據對象D：D是具有相同特性的數據元素的集合。

若D為空集，則稱為空樹。否則:(1)在D中存在唯一的稱為根的數據元素root；

(2)當n>1時，其余結點可分為m(m>0)個互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定義的樹，稱為根root的子樹。

數據關系R：樹的類型定義

基本操作：查找類

插入類刪除類

Root(T)//求樹的根結點

查找類：Value(T,cur_e)//求當前結點的元素值

Parent(T,cur_e)//求當前結點的雙親結點LeftChild(T,cur_e)//求當前結點的最左孩子RightSibling(T,cur_e)//求當前結點的右兄弟TreeEmpty(T)//判定樹是否為空樹TreeDepth(T)//求樹的深度TraverseTree(T,Visit())//遍歷InitTree(&T)//初始化置空樹

插入類：CreateTree(&T,definition)//按定義構造樹Assign(&T,cur_e,value)//給當前結點賦值InsertChild(&T,&p,i,c)//將以c為根的樹插入為結點p的第i棵子樹

ClearTree(&T)//將樹清空

刪除類：DestroyTree(&T)//銷毀樹的結構DeleteChild(&T,&p,i)//刪除結點p的第i棵子樹基本術語樹（Tree)：是n個結點的有限集（n>=0)。在任意一棵非空樹中，有且僅有一個特定的稱為根的結點（root)；當n>1時，其余結點可分為m（m>0)個互不相交的有限集T1,T2,…,Tm,其中每個集合Ti本身又是一棵符合本定義的樹，并且稱為根root的子樹。ABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),D(H,I,J(M)))T1T3T2樹根例如:1、結點:2、結點的度:3、樹的度:4、葉子結點:5、分支結點:數據元素+若干指向子樹的分支分支的個數樹中所有結點的度的最大值度為零的結點度大于零的結點DHIJM（終端結點）（非終端結點）6、(從根到結點的)路徑：7、孩子結點、雙親結點兄弟結點、堂兄弟結點祖先結點、子孫結點8、結點的層次:9、樹的深度：

由從根到該結點所經分支和結點構成ABCDEFGHIJMKL假設根結點的層次為1，依次加1樹中葉子結點所在的最大層次樹的示意圖：根結點葉子結點分支結點子樹子樹子樹Level1Level2Level3Level4結點的層次任何一棵非空樹是一個二元組

Tree=（root，F）其中：root被稱為根結點

F被稱為子樹森林10、森林：是m（m≥0）棵互不相交的樹的集合。ArootBCDEFGHIJMKLF(１)有確定的根；(２)樹根和子樹根之間為有向關系。有向樹：有序樹：樹中結點的各子樹之間的先后次序是有意義的，不能互換，否則就成為另一棵樹了。子樹之間存在確定的次序關系。無序樹：樹中結點的各子樹之間的先后次序無意義，可以互換。子樹之間不存在確定的次序關系。二叉樹的類型定義二叉樹是樹的基礎，一般的樹可以轉化為二叉樹來處理。1、二叉樹的定義：

二叉樹或為空樹，或是由一個根結點加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成（即左、右子樹次序不能顛倒）。ABCDEFGHK根結點左子樹右子樹2、二叉樹的五種基本形態：N空樹只含根結點NNNLRR右子樹為空樹L左子樹為空樹左右子樹均不為空樹

二叉樹的主要基本操作：查找類插入類刪除類

Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);

PreOrderTraverse(T,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());

InitBiTree(&T);Assign(&T,&e,value);CreateBiTree(&T,definition);InsertChild(&T,p,LR,c);ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(&T,p,LR);二叉樹的重要特性

性質1

：在二叉樹的第i層上至多有2i-1個結點。(i≥1)用歸納法證明：

歸納基：

歸納假設：

歸納證明：i=1

層時，只有一個根結點：

2i-1=20=1；假設對所有的j，1≤j

i，命題成立；由歸納假設知：第i-1層上至多有2i-2個結點。又因為二叉樹上每個結點至多有兩棵子樹，則第i層的結點數=2i-22=2i-1

。性質2

：

深度為i的二叉樹上至多有2i-1個結點（i≥1）。證明：[證明用求等比數列前i項和的公式]

基于上一條性質，深度為i的二叉樹上的結點數至多為

20+21+

+2i-1=2i-1

。

性質3

：

對任何一棵二叉樹，若它含有n0個葉子結點、n2個度為

2

的結點，則必存在關系式：n0=n2+1。證明：設二叉樹上結點總數n=n0+n1+n2又二叉樹上分支總數b=n0*0+n1+2n2

而b=n-1=n0+n1+n2-1由此，n0=n2+1。兩類特殊形態的二叉樹：滿二叉樹：指的是深度為k且含有2k-1個結點的二叉樹。完全二叉樹：樹中所含的n個結點和滿二叉樹中編號為1至n的結點一一對應。123456789101112131415abcdefghij性質4

：

具有n個結點的完全二叉樹的深度為

log2n+1。證明：設完全二叉樹的深度為k，則由性質2和完全二叉樹的定義知：深度為k-1的二叉樹應該是一棵滿二叉樹，故結點數為2k-1-1；深度為k的完全二叉樹當為滿二叉樹時結點數最多為2k–1。所以得2k-1-1

<n≤2k–1

2k-1≤n<2k

即

k-1≤log2n<k因為k只能是整數，因此，k=log2n

+1。性質5：若對含n個結點的完全二叉樹從上到下且從左至右進行1

至n

的編號，則對完全二叉樹中任意一個編號為i

的結點：

(1)若i=1，則該結點是二叉樹的根，無雙親，否則，編號為i/2的結點為其雙親結點；

(2)若2i>n，則該結點無左孩子，

否則，編號為2i的結點為其左孩子結點；

(3)若2i+1>n，則該結點無右孩子結點，

否則，編號為2i+1的結點為其右孩子結點。6.3二叉樹的存儲結構二、二叉樹的鏈式存儲表示一、二叉樹的順序存儲表示（適合存儲完全二叉樹）即用一組地址連續的存儲單元依次從上至下，從左至右存儲完全二叉樹上的結點元素。也就是說，將完全二叉樹上編號為i的結點存放在數組下標為（i-1)的分量中。若要存儲一棵一般的二叉樹，結點的存放應與完全二叉樹上的結點對照，存儲在數組的相應分量中。用“0”表示不存在該結點。可能會浪費很多存儲空間，單支樹就是一個極端情況。一、二叉樹的順序存儲表示完全二叉樹的數組表示一般二叉樹的數組表示數組表示順序存儲的C語言描述#defineMAX_TREE_SIZE100//二叉樹的最大結點數typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0號單元存儲根結點ADEBCFrootlchilddatarchild結點結構1.二叉鏈表二、二叉樹的鏈式存儲表示二叉鏈表的C語言描述typedefstruct

BiTNode

{

//結點結構

TElemTypedata;

struct

BiTNode

*lchild,*rchild;

//左右孩子指針}BiTNode,*BiTree;lchilddatarchild結點結構:ADEBCFroot2．三叉鏈表parent

lchilddatarchild結點結構三叉鏈表的C語言描述typedefstructTriTNode{