Question

用C语言编写：建立一棵以二叉链表结构存储的二叉树，并对其进行遍历。求该二叉树中的结点个数等操作。

Answer 1

存储结构
typedef struct {
int weight;
int parent, lchild, rchild;
} HTNode ,*HuffmanTree; // 动态分配数组存储huffman树
算法设计
void createHuffmantree(){
ht=(HuffmanTree)malloc(m+1)*sizeof(HTNode);// 动态分配数组存储huffman树,0号单元未用
// m:huffman 树中的结点数（m=2*n-1）
for (i=1;i<=m;++i)
ht[i].parent= ht[i]->lch= ht[i]->rch=0;
for (i=1;i<=n;++i)
ht[i].weight=w[i]; //初始化，w[i]：n个叶子的权值
for (i=n+1;i<=m,++i) ｛ //建哈夫曼树
select(i-1),s1,s2); //在ht[k](1<=k<=i-1)中选择两个双亲域为零而权值取最小的结点 :s1和s2
ht[s1].parent= ht[s2].parent=i;
ht[i].lch=s1;
ht[i].rch=s2;
ht[i].weight=ht[s1].weight + ht[s2].weight ;
};
}