数据结构单元练习7(4)

5 29 33 11 20 49

82

WPL=(16+17)*2+(9+14+15)*3+6*4+(2+3)*5=229

15． 假设用于通信的电文仅由A、B、C、D、E、F、G 、H8个字母组成，字母在电文中出现的频率分别为7，19，2，6，32，3，21，10。试为这8个字母设计哈夫曼编码。

解：以权值：2、3、6、7、10、19、21、32构造哈夫曼树：

六．算法设计题

以二叉链表为存储结构，设二叉树BT结构为： typedef struct BT { char data; BT *lchild; BT *rchild; }BT;

0 0 0 1001 401 0 0 601 字母编号 A B C D 1 E F G H 对应编码 1010 00 10000 1001 11 10001 01 1011 出现频率 7 19 2 6 32 3 21 10 19 21 11 5 1 2 328 1 17 7 32 0 1 0 6 101． 求二叉树中的度数为2的结点。 2． 求二叉树中值为最大的元素。 3． 将二叉树各结点存储到一维数组中。

4． 前序输出二叉树中各结点及其结点所在的层号。 5． 求二叉树的宽度

6． 交换二叉树各结点的左右子树。

7． 写出在二叉树中查找值为x的结点在树中层数的算法。 解： 1．

求二叉树中的度数为2的结点。 void count(BT t) { if (t)

{ if (t->lchild && t->rchild)

k++;

count(t->lchild); count(t->rchild); } }

2. 求二叉树中值为最大的元素。

int maxnode(BT t, int max) { if (t)

{ if (t->data>max)

max=t->data;

max=maxnode(t->lchild,max); max=maxnode(t->rchild,max); } }

3．将二叉树各结点存储到一维数组中。

void create(BT t,int a[ ],int i) { if (t)

{ a[i]=t->data;

create (t->lchild, a, 2*i); create (t->rchild, a, 2*i+1);

} }

4．前序输出二叉树中各结点及其结点所在的层号。void preorderlevel (BT t,int h) // t的层数为h { if (t!=NULL)