(下图为某操作系统中文件系统的目录结构。 请回答以下问题。 哈夫曼树是一种特殊的树形结构,请证明哈夫曼树的总结点数总为奇数。

admin2018-07-17  25

问题 (下图为某操作系统中文件系统的目录结构。

    请回答以下问题。
哈夫曼树是一种特殊的树形结构,请证明哈夫曼树的总结点数总为奇数。

选项

答案由哈夫曼树中没有度为1的结点可知任意哈夫曼树的n1=0,又因哈夫曼树为二叉树,满足n0=1+n2,所以哈夫曼树的总结点数n=n0+n1+n2=n0+0+n0—1=2n0一1,可知无论初始有多少个叶子结点,哈夫曼树的总结点数一定为奇数。

解析
转载请注明原文地址:https://kaotiyun.com/show/Q8Ri777K
0

最新回复(0)