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

admin2018-07-17 28

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

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

选项

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

解析

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

计算机408

相关试题推荐

随机试题

最新回复(0)