數(shù)據(jù)結構樹-二叉樹的定義和二叉樹性質與存儲本

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

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

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

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

數(shù)據(jù)關系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、分支結點:數(shù)據(jù)元素+若干指向子樹的分支分支的個數(shù)樹中所有結點的度的最大值度為零的結點度大于零的結點DHIJM（終端結點）（非終端結點）6、(從根到結點的)路徑：7、孩子結點、雙親結點兄弟結點、堂兄弟結點祖先結點、子孫結點8、結點的層次:9、樹的深度：

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

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

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

二叉樹或為空樹，或是由一個根結點加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成（即左、右子樹次序不能顛倒）。ABCDEFGHK根結點左子樹右子樹2、二叉樹的五種基本形態(tài)：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層的結點數(shù)=2i-22=2i-1

。性質2

：

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

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

20+21+

+2i-1=2i-1

。

性質3

：

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

2

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

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

：

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

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

<n≤2k–1

2k-1≤n<2k

即

k-1≤log2n<k因為k只能是整數(shù)，因此，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二叉樹的存儲結構二、二叉樹的鏈式存儲表示一、二叉樹的順序存儲表示（適合存儲完全二叉樹）即用一組地址連續(xù)的存儲單元依次從上至下，從左至右存儲完全二叉樹上的結點元素。也就是說，將完全二叉樹上編號為i的結點存放在數(shù)組下標為（i-1)的分量中。若要存儲一棵一般的二叉樹，結點的存放應與完全二叉樹上的結點對照，存儲在數(shù)組的相應分量中。用“0”表示不存在該結點?？赡軙速M很多存儲空間，單支樹就是一個極端情況。一、二叉樹的順序存儲表示完全二叉樹的數(shù)組表示一般二叉樹的數(shù)組表示數(shù)組表示順序存儲的C語言描述#defineMAX_TREE_SIZE100//二叉樹的最大結點數(shù)typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0號單元存儲根結點ADEBCFrootlchilddatarchild結點結構1.二叉鏈表二、二叉樹的鏈式存儲表示二叉鏈表的C語言描述typedefstruct

BiTNode

{

//結點結構

TElemTypedata;

struct

BiTNode

*lchild,*rchild;

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

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