文档介绍：数据结构4树与二叉树
由NordriDesign提供
例：求中序线索树中给定结点的后继结点
BiThrTree inordernext ( BiThrTree p )
{ if ( p5
14
29
23
3
5
8
11
11
3
5
8
19
14
29
23
8
7
15
11
3
5
8
19
29
23
14
8
7
15
29
29
14
8
7
15
29
11
3
5
8
19
23
42
11
3
5
8
19
23
42
29
14
8
7
15
29
58
11
3
5
8
19
23
42
29
14
8
7
15
29
58
100
二、Haffman编码
前缀码：给定一个序列的集合，若没有一个序列是另一个序列的前缀，该序列集合称为前缀码。
例如：{ 000，001，01，10，11 }
{ 1 ，0001，000 }
定理：任意一棵二叉树的树叶可对应一个前缀码。
定理：任何一个前缀码都对应一棵二叉树。
数据传输过程中字符的编码问题。
在为字符编码时，总希望总的编码长度尽可能地短，因电文中每个字符出现的频率不同，所以可用前缀码，对常出现的字符用短码表示，使得到电文总长度最短。
假设每个字符在电文中出现的次数为wi，其编码长度为li，电文中只有n中字符
n
则电文总长为 ∑wili
i=1
对应二叉树上，若wi为叶子结点的权，li为根到叶子的路径长度
n
则二叉树的带权路径长度为 ∑wili
i=1
所以设计电文总长最短的二进制前缀码，即为以几种字符出现的频率作为权值，设计一棵Huffman树的问题，由此得到的二进制前缀码便称为Huffman编码。
一棵n个叶子结点的Huffman树共有2n-1个结点
赫夫曼树和赫夫曼编码的存储表示
typedef struct {
unsigned int weight ;
unsigned int parent , lchild , rchild ;
} HTNode , * HuffmanTree ;
typedef char * * HuffmanCode ;
例如：某通信系统中可能出现8种字符，, , , , , , , ,设计Huffman编码。
设权w={5,29,7,8,14,23,3,11}
n = 8
则：m=15
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n )
{ if ( n <= 1 ) return ;
m = 2 * n – 1 ;
HT=(HuffmanTree)
malloc((m+1)*sizeof(HTNode));
for(p=HT,i=1;i<=n;++i,++p,++w)
*p={*w,0,0,0};
for(;i<=m;++i;++p) *p={0,0,0,0};
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;
}
5
0
0
0
29
0
0
0
7
0
0
0
8
0
0
0
14
0
0
0
23
0
0
0
3