第6章 树和二叉树练习题及答案(2)

4. 把如图所示的树转化成二叉树。

答：注意全部兄弟之间都要连线（包括度为2的兄弟）,并注意原有连线结点一律归入左子树，新添连线结点一律归入右子树。 A B E C K F H D L G I M J

5、画出和下列二叉树相应的森林。

答：注意根右边的子树肯定是森林，而孩子结点的右子树均为兄弟。

6、假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。 解：哈夫曼编码

先将概率放大100倍，以方便构造哈夫曼树。

w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6], (7,10)】, ……19, 21, 32

（100） （40） （60） 19 21 32 （28）

（17） （11）

0 1 0 1 0 1 19 21 32 0 1 0 1 0 1 7 10 6 0 1 2 3 7 10 6 （5） 2 3

WPL＝2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第6章 树和二叉树练习题及答案(2)在线全文阅读。