树（C语言）
2017-05-14 本文已影响238人
sunxiaohang
判定树
每个结点需要查找的次数刚好为该结点所在的层数，查找成功时查找次数不会超过判定树的深度，n个结点的判定树的深度为[LgN]+1
平均查找长度ASL（Average Search Length）
ASL=sum(层数*个数)/各层总个数n(n>=0)个结点构成的有限集合当n=0时称为空树
对于任何一棵非空树（n>0），它具备以下性质
- 树中会有一个root特殊结点用r表示
- 其余结点可分为m(m>0)个互不相交的有限集，其中每个集合本身又是一棵树，称为原来树的子树
树的特点：
- 子树是不相交的
- 出了根节点外，每隔结点有且仅有一个父结点
- 一棵N个结点的树有N-1条边（树是保证结点连通的最少边链接方式）
树的一些基本术语：
-
结点的度：结点的子树个数（满二叉树单个结点的度为2）
-
树的度：树的所有结点中最大的度数
-
叶结点：结点度为0的结点
-
父节点，子节点，兄弟结点
-
路径和路径长度
-
祖先节点：沿树根到某一结点路径上的所有节点都是这个结点的祖先结点
子孙结点通； -
结点的层次：规定根结点在一层，其他层次随子节点+1
-
树的深度：树中结点的最大层次就是这棵树的深度
儿子兄弟表示法可以将所有的树转化为二叉树
特殊二叉树： -
斜二叉树：只有左儿子或只有右结点
-
完美二叉树：满二叉树
-
完全二叉树：结点编号与满二叉树结点编号相同（编号不间断）
二叉树的特点 -
一个二叉树第i层的最大节点数为：2(i-1),i>=1
-
深度为k的二叉树有最大节点总数为2k-1,k>=1;
-
对于任何非空二叉树T，若N0表示叶子结点的个数，N2是度为2的非叶结点个数，那么两者满足关系：N0=N2+1;(即叶子结点个数-1=度数为2的结点个数)
二叉树的抽象数据类型定义
数据对象集：一个有穷的结点集合
若不为空，则由根节点和其左、右二叉树组成
操作集：判断树是否为空，遍历，创建二叉树
常用的遍历方法有：
先序遍历（根左右），
中序遍历（左根右），
后序遍历（左右根），
层次遍历（从上到下，从左到右）
在二叉树中，我们知道叶结点总数n0与有两个儿子的结点总数n2之间的关系是：n0=n2+1.
那么类似关系是否可以推广到m叉树中？也就是，如果在m叉树中，叶结点总数是n0，
有一个儿子的结点总数是n1，有2个儿子的结点总数是n2，有3个儿子的结点总数是n3，
那么，ni之间存在什么关系？
- 完全二叉树，非根节点的父节点序号是[i/2]
- 结点的左孩子结点序号是2i，若2i<=n，否则没有左孩子结点
- 结点的右孩子结点序号是2i+1，（若2i+1<=n,否则没有右孩子）
typedef struct BT{
int value;
struct BT *leftchild;
struct BT *rightchild;
}BinTree;
//二叉树的每个结点遍历都会遇到三次，第一次遇到就打印的为先序遍历，第二次遇到就打印的为中序遍历，第三次遇到就打印的为后序遍历
//先序遍历(递归遍历)
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);
}
}
//二叉树遍历的本质是将二维序列转换为一维序列
//使用队列进行二叉树的层级访问（遍历根节点，将左右儿子节点入队列）
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);
}
}
//给定前中序遍历结果或中后序遍历结果可以唯一确定一棵二叉树，给定前后序遍历结果不能唯一确定二叉树
//非递归实现（中序遍历）
void InOrderTraversal(BinTree *BT){
BinTree *T=BT;
LinkedStack *stack=CreateLinkedStack();//创建并初始化堆栈
while(T||!isEmpty(stack)){
while(T){//一直向左将沿途结点压入堆栈
Push(stack,T);
T=T->leftchild;//转向左子树
}
if(!isEmpty(stack)){
T=Pop(stack);//结点弹出堆栈
printf("%5d",T->value);//打印结点
T=T->rightchild;//转向右子树
}
}
}
//非递归实现（先序遍历）
void PreOrderTraversal(BinTree *BT){
BinTree *T=BT;
LinkedStack *stack=CreateLinkedStack();//创建并初始化堆栈
while(T||!isEmpty(stack)){
while(T){//一直向左将沿途结点压入堆栈
printf("%5d",T->value);//打印结点
Push(stack,T);
T=T->leftchild;//转向左子树
}
if(!isEmpty(stack)){
T=Pop(stack);//结点弹出堆栈
T=T->rightchild;//转向右子树
}
}
}
二叉搜索树：BST(binary search tree)
也称二叉排序树或二叉查找树
二叉搜索树条件
1.非空左子树的所有键值小于其根节点的键值
2.非空右子树的所有键值大于其根节点的键值
3.左，右子树都是二叉搜索树
//递归方式实现
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;//查找成功，返回结点地址(return尾递归)
}
//非递归方式实现
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;
}
//结点插入
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;
}
//删除结点
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 //找到要删除的结点
if(binTree->leftchild&&binTree->rightchild){//被删除结点有左右量子子节点
Temp=FindMin(binTree->rightchild);//在右子树中招最小的元素填充删除结点
binTree->value=Temp->value;
binTree->rightchild=Delete(binTree->rightchild,binTree->value);
}else{//被删除的结点有一个或无子结点
Temp=binTree;
if(!binTree->leftchild)binTree=binTree->rightchild;
else if(!binTree->rightchild)binTree=binTree->leftchild;
free(Temp);
}
return binTree;
}
平衡二叉树(Balanced Binary Tree)
(AVL树)(AVL是提出平衡树的学者名字首字母)
- 空树或任一结点左右子树高度差不超不过1|BF(T)|<=1
- 平衡因子(Balance Factor 简称BF：BF(T)=Hl-Hr)
- 其中hl和hr分别为T的左右子树高度
- 高度=层数-1
- 完全二叉树高度为log2N(平衡二叉树)
- Nh是高度为h的平衡二叉树的最小结点树
- Nh=F(h+2)-1
#define MaxData 10000
typedef struct HeapStruct{
int *value;//存储对元素的数组
int length;//堆的当前元素个数
int capacity;//堆的最大容量
}Heap;
优先队列（PriorityQueue）
取出元素的先后顺序是按照元素的优先权（关键字）大小，而不是元素进入队列的先后顺序
最大堆和最小堆都必须满足完全二叉树（切根节点最大或最小）最大堆的建立
建立最大堆：将已经存在的N个元素按最大堆的要求存放在要给一维数组中
- 方法一：通过插入操作，将N个元素一个个相继插入到一个初始为空的堆中去，其时间代价最大为O（NlogN）
- 方法二：在线性时间复杂度下建立最大堆
- (1)将N个元素按输入顺序存入，先满足完全二叉树的结构特性
- (2)调整各结点位置以满足最大堆的有序特性
建堆时，最坏的情况下需要挪动的元素次数等于树中各节点的高度和
对由同样n个整数构成的二叉搜索树（查找树）和最小堆：有以下结论
- 二叉搜索树高度大于等于最小堆高度
- 对该二叉搜索树进行中序遍历可得到从小到大的序列
- 从最小堆根节点到起任何叶结点的路径上的结点值构成从小到大的序列
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("最大堆已经满了");
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];
//用最大堆中最后一个元素从根节点开始过滤下层结点
temp=heap->value[heap->length--];
for(parent=1;parent*2<=heap->length;parent=child){
child=parent*2;
//左儿子和右儿子节点比较取较大者
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）
查找效率，查找次数乘查找概率
带权路径长度（WPL）：设二叉树有n个叶子结点，每隔叶子结点带有权值Wk，从根节点到每隔叶子结点的长度是Lk，则每隔叶子结点的带全路径长度之和WPL=（nEk=1）WkLk
最优二叉树或哈夫曼树：WPL最小的二叉树
哈夫曼树的特点
- 没有度为1的结点
- n个叶子结点的HuffmanTree有2n-1个结点
- HuffmanTree的任意非叶结点的左右子树交换后仍是HuffmanTree
对于一组权值，可能有不同构的两棵HuffmanTree
HuffmanTree *Huffman(Heap *heap){
//假设heap->length权值已经存在heap->value[]->weight里面
int i;HuffmanTree *huffmanTree;
BuildHeap(heap);//将heap->value[]按权值调整为最小堆
for(i=1;i<heap->length;i++){
huffmanTree=malloc(sizeof(HuffmanTree));//建立新结点
huffmanTree->left=DeleteMin(heap);//从最小堆中删除一个结点，作为新huffmanTree的左子结点
huffmanTree->right=DeleteMin(heap);//从最小堆中删除一个结点，作为新huffmanTree的右子结点
huffmanTree->weight=huffmanTree->weight+huffmanTree->right->weight;//计算新// 权值
Insert(heap,huffmanTree);
}
huffmanTree=DeleteMin(heap);
return huffmanTree;
}
/*二叉树用于编码
* 当被编码字母全部在二叉树的叶子结点的时候（即，编码字母不会出现在有子节点的结点中）便可以保证字符编码没有二义性
* */
