2. 从业资格
  3. 下面关于哈夫曼树的叙述中，正确的是（　　）。A.哈夫曼树一定是完全二叉树 B.

下面关于哈夫曼树的叙述中，正确的是（　　）。A.哈夫曼树一定是完全二叉树 B.

资格题库2022-08-02  75
问题 下面关于哈夫曼树的叙述中，正确的是（　　）。A.哈夫曼树一定是完全二叉树B.哈夫曼树一定是平衡二叉树C.哈夫曼树中权值最小的两个结点互为兄弟结点D.哈夫曼树中左孩子结点小于父结点、右孩子结点大于父结点
选项 A.哈夫曼树一定是完全二叉树
B.哈夫曼树一定是平衡二叉树
C.哈夫曼树中权值最小的两个结点互为兄弟结点
D.哈夫曼树中左孩子结点小于父结点、右孩子结点大于父结点
答案 C
解析 哈夫曼树是一种特殊的二叉树，但它不是完全二叉树，也不是平衡二叉树，给出n个权值{w1，w2，…，wn}构造一棵具有n个叶子结点的哈夫曼树的方法如下：
第一步，构造n个只有根结点的二叉树集合F={T1，T2，…，Tn}，其中每棵二叉树Ti的根结点带权为Wi（1≤k≤n）；
第二步，在集合F中选取两棵根结点的权值最小的二叉树作为左右子树，构造一棵新的二叉树，令新二叉树根结点的权值为其左、右子树上根结点的权值之和；
第三步，在F中删除这两棵二叉树，同时将新得到的二叉树加入到F中；
第四步，重复第二步和第三步，直到F只含有一棵二叉树为止，这棵二叉树便是哈夫曼树。
综上所述，我们可以知道哈夫曼树中权值最小的两个结点互为兄弟结点。
转载请注明原文地址:https://www.tihaiku.com/congyezige/2410148.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)