判定樹
每個結(jié)點需要查找的次數(shù)剛好為該結(jié)點所在的層數(shù)躺酒，查找成功時查找次數(shù)不會超過判定樹的深度洒闸，n個結(jié)點的判定樹的深度為[LgN]+1
平均查找長度ASL（Average Search Length）
ASL=sum(層數(shù)*個數(shù))/各層總個數(shù)n(n>=0)個結(jié)點構(gòu)成的有限集合當(dāng)n=0時稱為空樹
對于任何一棵非空樹（n>0），它具備以下性質(zhì)
- 樹中會有一個root特殊結(jié)點用r表示
- 其余結(jié)點可分為m(m>0)個互不相交的有限集碌上，其中每個集合本身又是一棵樹倚评，稱為原來樹的子樹
樹的特點：
- 子樹是不相交的
- 出了根節(jié)點外浦徊，每隔結(jié)點有且僅有一個父結(jié)點
- 一棵N個結(jié)點的樹有N-1條邊（樹是保證結(jié)點連通的最少邊鏈接方式）
樹的一些基本術(shù)語：
結(jié)點的度：結(jié)點的子樹個數(shù)（滿二叉樹單個結(jié)點的度為2）
樹的度：樹的所有結(jié)點中最大的度數(shù)
葉結(jié)點：結(jié)點度為0的結(jié)點
父節(jié)點，子節(jié)點天梧，兄弟結(jié)點
路徑和路徑長度
祖先節(jié)點：沿樹根到某一結(jié)點路徑上的所有節(jié)點都是這個結(jié)點的祖先結(jié)點
子孫結(jié)點通盔性；結(jié)點的層次：規(guī)定根結(jié)點在一層，其他層次隨子節(jié)點+1
-
樹的深度：樹中結(jié)點的最大層次就是這棵樹的深度
兒子兄弟表示法可以將所有的樹轉(zhuǎn)化為二叉樹
特殊二叉樹： 斜二叉樹：只有左兒子或只有右結(jié)點
完美二叉樹：滿二叉樹
完全二叉樹：結(jié)點編號與滿二叉樹結(jié)點編號相同（編號不間斷）
二叉樹的特點一個二叉樹第i層的最大節(jié)點數(shù)為：2(i-1),i>=1
深度為k的二叉樹有最大節(jié)點總數(shù)為2k-1,k>=1;
對于任何非空二叉樹T呢岗，若N0表示葉子結(jié)點的個數(shù)冕香，N2是度為2的非葉結(jié)點個數(shù)，那么兩者滿足關(guān)系：N0=N2+1;(即葉子結(jié)點個數(shù)-1=度數(shù)為2的結(jié)點個數(shù))
二叉樹的抽象數(shù)據(jù)類型定義
數(shù)據(jù)對象集：一個有窮的結(jié)點集合
若不為空后豫，則由根節(jié)點和其左悉尾、右二叉樹組成
操作集：判斷樹是否為空，遍歷挫酿，創(chuàng)建二叉樹
常用的遍歷方法有：
先序遍歷（根左右）构眯，
中序遍歷（左根右），
后序遍歷（左右根）早龟，
層次遍歷（從上到下惫霸，從左到右）
在二叉樹中，我們知道葉結(jié)點總數(shù)n0與有兩個兒子的結(jié)點總數(shù)n2之間的關(guān)系是：n0=n2+1.
那么類似關(guān)系是否可以推廣到m叉樹中葱弟？也就是壹店，如果在m叉樹中，葉結(jié)點總數(shù)是n0芝加，
有一個兒子的結(jié)點總數(shù)是n1硅卢，有2個兒子的結(jié)點總數(shù)是n2，有3個兒子的結(jié)點總數(shù)是n3妖混，
那么老赤，ni之間存在什么關(guān)系？
- 完全二叉樹制市，非根節(jié)點的父節(jié)點序號是[i/2]
- 結(jié)點的左孩子結(jié)點序號是2i，若2i<=n弊予，否則沒有左孩子結(jié)點
- 結(jié)點的右孩子結(jié)點序號是2i+1祥楣，（若2i+1<=n,否則沒有右孩子）
typedef struct BT{
int value;
struct BT *leftchild;
struct BT *rightchild;
}BinTree;
//二叉樹的每個結(jié)點遍歷都會遇到三次，第一次遇到就打印的為先序遍歷汉柒，第二次遇到就打印的為中序遍歷误褪，第三次遇到就打印的為后序遍歷
//先序遍歷(遞歸遍歷)
void PreOrderTraversal(BinTree *BT){
if(BT){
if(!BT->leftchild&&!BT->rightchild)
printf("%d\n",BT->value);
PreOrderTraversal(BT->leftchild);
PreOrderTraversal(BT->rightchild);
}
}
//中序遍歷(遞歸遍歷)
void InOrderTraversal(BinTree *BT){
if(BT){
if(!BT->leftchild&&!BT->rightchild)
InOrderTraversal(BT->leftchild);
printf("%d\n",BT->value);
InOrderTraversal(BT->rightchild);
}
}
//后序遍歷(遞歸遍歷)
void PostOrderTraversal(BinTree *BT){
if(BT){
if(!BT->leftchild&&!BT->rightchild)
PostOrderTraversal(BT->leftchild);
PostOrderTraversal(BT->rightchild);
printf("%d\n",BT->value);
}
}
//二叉樹遍歷的本質(zhì)是將二維序列轉(zhuǎn)換為一維序列
//使用隊列進(jìn)行二叉樹的層級訪問（遍歷根節(jié)點，將左右兒子節(jié)點入隊列）
void LevelOrderTraversal(BinTree BT){
Queue *queue;
BinTree *T;
queue=CreateQueue();
AddQueue(queue,BT);
while(!IsEmptyQueue(queue)){
T=DeleteQueue(queue);
printf("%d\n",T->value);
if(T->leftchild)AddQueue(queue,T->leftchild);
if(T->rightchild)AddQueue(queue,T->rightchild);
}
}
//給定前中序遍歷結(jié)果或中后序遍歷結(jié)果可以唯一確定一棵二叉樹碾褂，給定前后序遍歷結(jié)果不能唯一確定二叉樹
//非遞歸實現(xiàn)（中序遍歷）
void InOrderTraversal(BinTree *BT){
BinTree *T=BT;
LinkedStack *stack=CreateLinkedStack();//創(chuàng)建并初始化堆棧
while(T||!isEmpty(stack)){
while(T){//一直向左將沿途結(jié)點壓入堆棧
Push(stack,T);
T=T->leftchild;//轉(zhuǎn)向左子樹
}
if(!isEmpty(stack)){
T=Pop(stack);//結(jié)點彈出堆棧
printf("%5d",T->value);//打印結(jié)點
T=T->rightchild;//轉(zhuǎn)向右子樹
}
}
}
//非遞歸實現(xiàn)（先序遍歷）
void PreOrderTraversal(BinTree *BT){
BinTree *T=BT;
LinkedStack *stack=CreateLinkedStack();//創(chuàng)建并初始化堆棧
while(T||!isEmpty(stack)){
while(T){//一直向左將沿途結(jié)點壓入堆棧
printf("%5d",T->value);//打印結(jié)點
Push(stack,T);
T=T->leftchild;//轉(zhuǎn)向左子樹
}
if(!isEmpty(stack)){
T=Pop(stack);//結(jié)點彈出堆棧
T=T->rightchild;//轉(zhuǎn)向右子樹
}
}
}
二叉搜索樹：BST(binary search tree)
也稱二叉排序樹或二叉查找樹
二叉搜索樹條件
1.非空左子樹的所有鍵值小于其根節(jié)點的鍵值
2.非空右子樹的所有鍵值大于其根節(jié)點的鍵值
3.左兽间，右子樹都是二叉搜索樹
//遞歸方式實現(xiàn)
Position Find(BinTree *binTree,int result){
if(!binTree)return NULL;
if(result>binTree->value)return Find(binTree->rightchild,result);
else if(result<binTree->value)return Find(binTree,result);
else return binTree;//查找成功，返回結(jié)點地址(return尾遞歸)
}
//非遞歸方式實現(xiàn)
Position IterFind(BinTree *binTree,int value){
while(binTree){
if(result>binTree->value)
binTree=binTree->rightchild;
else if(result<binTree->value)
binTree=binTree->leftchild;
else
return binTree;
}
return NULL;
}
//尋找最小值
Position FindMin(BinTree *binTree){
if(!binTree)return NULL;
else if(!binTree->leftchild)
return binTree;
else
return FindMin(binTree->leftchild);
}
//尋找最大值
Position FindMax(BinTree *binTree){
if(binTree){
while(binTree->rightchild)
binTree=binTree->rightchild;
}
return binTree;
}
//結(jié)點插入
BinTree * Insert(BinTree *binTree, int value) {
if(!binTree){
binTree=malloc(sizeof(BinTree));
binTree->value=value;
binTree->leftchild=binTree->rightchild=NULL;
}else{
if(value<binTree->value)
binTree->leftchild=Insert(binTree->leftchild,value);
else if(value>binTree->value)
binTree->rightchild=Insert(binTree->rightchild,value);
}
return binTree;
}
//刪除結(jié)點
BinTree *Delete(BinTree *binTree,int value){
(Position)BinTree *Temp;
if(!binTree)printf("要刪除的元素未找到");
//左子樹遞歸刪除
else if(value<binTree->value)binTree->leftchild=Delete(binTree,value);
//右子樹遞歸刪除
else if(value>binTree->value)binTree->rightchild=Delete(binTree->rightchild,value);
else //找到要刪除的結(jié)點
if(binTree->leftchild&&binTree->rightchild){//被刪除結(jié)點有左右量子子節(jié)點
Temp=FindMin(binTree->rightchild);//在右子樹中招最小的元素填充刪除結(jié)點
binTree->value=Temp->value;
binTree->rightchild=Delete(binTree->rightchild,binTree->value);
}else{//被刪除的結(jié)點有一個或無子結(jié)點
Temp=binTree;
if(!binTree->leftchild)binTree=binTree->rightchild;
else if(!binTree->rightchild)binTree=binTree->leftchild;
free(Temp);
}
return binTree;
}
平衡二叉樹(Balanced Binary Tree)
(AVL樹)(AVL是提出平衡樹的學(xué)者名字首字母)
- 空樹或任一結(jié)點左右子樹高度差不超不過1|BF(T)|<=1
- 平衡因子(Balance Factor 簡稱BF：BF(T)=Hl-Hr)
- 其中hl和hr分別為T的左右子樹高度
- 高度=層數(shù)-1
- 完全二叉樹高度為log2N(平衡二叉樹)
- Nh是高度為h的平衡二叉樹的最小結(jié)點樹
- Nh=F(h+2)-1
#define MaxData 10000
typedef struct HeapStruct{
int *value;//存儲對元素的數(shù)組
int length;//堆的當(dāng)前元素個數(shù)
int capacity;//堆的最大容量
}Heap;
優(yōu)先隊列（PriorityQueue）
取出元素的先后順序是按照元素的優(yōu)先權(quán)（關(guān)鍵字）大小正塌，而不是元素進(jìn)入隊列的先后順序
最大堆和最小堆都必須滿足完全二叉樹（切根節(jié)點最大或最朽致浴）最大堆的建立
建立最大堆：將已經(jīng)存在的N個元素按最大堆的要求存放在要給一維數(shù)組中
- 方法一：通過插入操作恤溶，將N個元素一個個相繼插入到一個初始為空的堆中去，其時間代價最大為O（NlogN）
- 方法二：在線性時間復(fù)雜度下建立最大堆
- (1)將N個元素按輸入順序存入帜羊，先滿足完全二叉樹的結(jié)構(gòu)特性
- (2)調(diào)整各結(jié)點位置以滿足最大堆的有序特性
建堆時咒程，最壞的情況下需要挪動的元素次數(shù)等于樹中各節(jié)點的高度和
對由同樣n個整數(shù)構(gòu)成的二叉搜索樹（查找樹）和最小堆：有以下結(jié)論
- 二叉搜索樹高度大于等于最小堆高度
- 對該二叉搜索樹進(jìn)行中序遍歷可得到從小到大的序列
- 從最小堆根節(jié)點到起任何葉結(jié)點的路徑上的結(jié)點值構(gòu)成從小到大的序列
Heap * Create(int MaxSize){
Heap *heap=malloc(sizeof(Heap));
heap->value=malloc((MaxSize+1)*sizeof(int));
heap->length=0;
heap->capacity=MaxSize;
heap->value[0]=MaxData;//定義哨兵，便于操作
return heap;
}
void Insert(Heap *heap,int value){
int i;
if(IsFull(heap)){
printf("最大堆已經(jīng)滿了");
return;
}
i=++heap->length;
for(;heap->value[i/2]<value;i/=2)
heap->value[i]=heap->value[i/2];
heap->value[i]=value;
}
int DeleteMax(Heap *heap){
int parent,child;
int maxValue,temp;
if(IsEmpty(heap)){
printf("最大堆已空");
return 0;
}
maxValue=heap->value[1];
//用最大堆中最后一個元素從根節(jié)點開始過濾下層結(jié)點
temp=heap->value[heap->length--];
for(parent=1;parent*2<=heap->length;parent=child){
child=parent*2;
//左兒子和右兒子節(jié)點比較取較大者
if((child!=heap->length)&&(heap->value[child]<heap->value[child+1]))
child++;
if(temp>=heap->value[child])break;
else
heap->value[parent]=heap->value[child];
}
heap->value[parent]=temp;
return maxValue;
}
int IsEmpty(Heap *heap){
return heap->length==0;
}
int IsFull(Heap *heap){
return heap->length==heap->capacity;
}
typedef struct TreeNode{
int weight;
struct TreeNode *left,*right;
}HuffmanTree;
哈夫曼樹（HuffmanTree）
查找效率讼育，查找次數(shù)乘查找概率
帶權(quán)路徑長度（WPL）：設(shè)二叉樹有n個葉子結(jié)點帐姻，每隔葉子結(jié)點帶有權(quán)值Wk，從根節(jié)點到每隔葉子結(jié)點的長度是Lk奶段，則每隔葉子結(jié)點的帶全路徑長度之和WPL=（nEk=1）WkLk
最優(yōu)二叉樹或哈夫曼樹：WPL最小的二叉樹
哈夫曼樹的特點
- 沒有度為1的結(jié)點
- n個葉子結(jié)點的HuffmanTree有2n-1個結(jié)點
- HuffmanTree的任意非葉結(jié)點的左右子樹交換后仍是HuffmanTree
對于一組權(quán)值饥瓷，可能有不同構(gòu)的兩棵HuffmanTree
HuffmanTree *Huffman(Heap *heap){
//假設(shè)heap->length權(quán)值已經(jīng)存在heap->value[]->weight里面
int i;HuffmanTree *huffmanTree;
BuildHeap(heap);//將heap->value[]按權(quán)值調(diào)整為最小堆
for(i=1;i<heap->length;i++){
huffmanTree=malloc(sizeof(HuffmanTree));//建立新結(jié)點
huffmanTree->left=DeleteMin(heap);//從最小堆中刪除一個結(jié)點，作為新huffmanTree的左子結(jié)點
huffmanTree->right=DeleteMin(heap);//從最小堆中刪除一個結(jié)點痹籍，作為新huffmanTree的右子結(jié)點
huffmanTree->weight=huffmanTree->weight+huffmanTree->right->weight;//計算新// 權(quán)值
Insert(heap,huffmanTree);
}
huffmanTree=DeleteMin(heap);
return huffmanTree;
}
/*二叉樹用于編碼
* 當(dāng)被編碼字母全部在二叉樹的葉子結(jié)點的時候（即呢铆，編碼字母不會出現(xiàn)在有子節(jié)點的結(jié)點中）便可以保證字符編碼沒有二義性
* */
