二叉树的基本应用
统计二叉树叶子结点数
void Leafnum(bt *t)
{
if(t)
{
if(t->lchild == NULL && t->rchild == NULL)
{
count++;
Leafnum(t->lchild);
Leafnum(t->rchild);
}
}
}
二叉树结点
void Nodenum(bt *t)
{
if(t)
{
count++;
Nodenum(t->lchild);
Nodenum(t->rchild);
}
}
二叉树的深度
int TreeDepth(bt *t)
{
int ldep,rdep;
if(t == NULL) return 0;
else
{
ldep = TreeDepth(t->lchild);
rdep = TreeDepth(t->rchild)；
if(ldep > rdep) return ldep + 1;
else return rdep + 1;
}
}
查找数据元素
bt *Search(bt *t,datatype x)
{
bt *p;
if(t != NULL)
{
if(t->data == x)
return t;
p = Search(t->lchild,x);
if(p != NULL) return p;
else return Search(t->rchild,x);
}
else return NULL;
}
标识符树与表达式
将算术表达式用二叉树表示，称为标识符树，又称二叉表达树
运算对象都是叶结点
运算符都是根结点
从表达式产生标识符树的方法
(1)读入表达式的一部分生成相应的二叉树，再读入运算符，运算符与二叉树根结点的运算符比较优先级的高低
(a)读入优先级>根结点优先级，则读入的运算符作为根的右子树，原来的二叉树的右子树成为运算符的左子树
(b)读入优先级<=根结点的优先级，则读入运算符作为树根，而原来二叉树作为左子树
(2)遇到括号，先使括号内的表达式产生一棵二叉树，再把它的根结点连到前面已产生的而擦函数根结点的右子树上
(3)单目运算符+，-，加运算对象0
例如-A
哈夫曼树及其应用
路径长度：从一结点到另一结点经过的分支数目树的路径长度：从树根到每个结点的路径长度之和结点的带权路径长度：结点到树根的路径长度乘以结点上权的乘积树的带权路径长度：树的所有结点到根的带权路径长度最优树：带权路径长度最小的的二叉树
哈夫曼树的构造
(1)由给定的 n个权值{w1,w2,w3...wn}构成n棵二叉树的集合F={T1,T2....Tn}，其中每棵二叉树Ti中只有一个带权为Wi的根结点，其左右子树均空
(2)在F中选取 两棵根结点权值最小的树， 作为左右子树构建一个新的二叉树，且让新二叉树的根结点的权值等于其左右子树的根结点权值之和
(3)在F中删去这两棵树，同时将新得到的二叉树加入F中
(4)重复(2)和(3)，直到F只含一棵树为止。这棵树就是Huffman树
哈夫曼编码
规则：左零右一
代码部分
结点定义
typedef struct {
int weight;
int parent,lchild,rchild;
}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树
typedef char **HuffmanCode;
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{ //w存放n个字符的权值，构造赫夫曼树HT，并求出n个字符的赫夫曼码HC
if(n<=1) return; //n为字符数目
m = 2*n-1; //m为结点数目
HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元不用
//存放树的叶子结点,n-1个单元存放内部结点
for(p = HT,i = 1;i<=n;++i,++p,++w)
{
p->weight = *w;
p->parent = 0;
p->lchild = 0;
p->rchild = 0;
}
// *p = {*w,0,0,0};初始化HT中的叶结点循环退出时 i = n + 1；
for(;i<=m;++i,++p)
{
p->weight = 0;
p->parent = 0;
p->lchild = 0;
p->rchild = 0;
}
// *p = {0,0,0,0}；初始化HT中的内部结点
for(i = n+1;i<=m;++i)
{
Select(HT,i-1,s1,s2);
HT[s1].parent = i; HT[s2].parent = i;
HT[i].lchild = s1; HT[i].rchild = s2;
HT[i].weight = HT[s1].weight+HT[s2].weight;
}
}
从叶子到根逆向求赫夫曼编码
HC = (HuffmanCode)malloc((n+1)*sizeof(char *));
cd = (char *)malloc(n*sizeof(char));
cd[n-1] = '\0';
for( i = 1;i<=n;++i)
{
start = n-1;
for(c = i,f = HT[c].parent;f!=0;c =f,f=HT[f].parent)
if(HT[f],lchild ==c) cd[--start] = '0';
else cd[--start] = '1';
HC[i] = (char *)malloc((n-start)*sizeof(char));
strcpy(HC[i],&cd[start]);
}
free(cd);
