首页 > 试题广场 >

一棵Huffman树有m个叶结点，使用struct Node

[单选题]
一棵Huffman树有m个叶结点，使用 
struct Node {
    struct Node *l;
    struct Node *r;
    int val;
}
结构来存储该树中的结点，一共会产生（ ）个空指针 
  • 2m + 1
  • 4m
  • 2m - 1
  • 2m
查看答案及解析
添加回答
FuestcK头像 FuestcK
Huffman树树中没有度为1的节点
所以节点数
n=n0+n1+n2
=n0+n2
=n0+(n0-1)
=2n0-1
=2m-1
一共有2m-1个节点，因此有2m-1-1条边，一条边占用一个指针域，因此被占用的指针域个数为2m-2
2m-1个节点一共有4m-2个指针域
未被占用的指针域个数为4m-2-（2m-2）=2m
最后答案为2m
发表于 2016-06-22 11:18:21 回复(0)
走心头像 走心
哈夫曼树没有度为一的节点，有m个叶子节点所以就有2m个空指针
发表于 2016-08-01 15:59:22 回复(0)
这个人没有名字头像 这个人没有名字
不就是几个叶节点乘以2吗？
发表于 2016-06-22 14:08:08 回复(4)
有痕头像 有痕
答案是最后一个选项
发表于 2023-04-28 09:46:52 回复(0)
泉州码农头像 泉州码农
还以为要计算根节点
发表于 2023-09-27 08:31:57 回复(0)
大胖鱼头头像 大胖鱼头
一个有n个节点的线索二叉树，每个节点都有指向左右孩子的两个指针域，则共有2n个指针域，而n个节点共有n-1条分支，所以共有2n-(n-1)个空指针域，即有n+1个线索
哈夫曼树没有度为1的节点，只有度为0和度为2的节点。该题说有m个叶节点，所以度为2的节点有m-1个，总结点就是m+m-1=2m-1个，把上面的n替换掉：2m-1+1=2m，所以会产生2m个空指针
发表于 2022-01-18 10:41:05 回复(0)
巫巫头像 巫巫
haffman树是由两棵树合并而来，不存在度为一的节点
发表于 2016-08-06 18:15:44 回复(0)
Ｍe怤畢炜eＭ头像 Ｍe怤畢炜eＭ
哈夫曼树只存在度为零和度为二的节点 叶子节点的个数为m 所以null指针的个数为2m个
编辑于 2016-07-14 13:55:07 回复(0)
shineNEVERLAND头像 shineNEVERLAND
发表于 2016-07-13 16:44:41 回复(0)
牛客470292号头像 牛客470292号
难道跟存储结构有关系？
发表于 2016-06-23 00:08:00 回复(0)
hidaring头像 hidaring
同问
发表于 2016-06-22 09:26:01 回复(0)
bboyzqh头像 bboyzqh
谁能解释以下，个人认为2m
发表于 2016-06-21 23:30:03 回复(1)
提交观点

问题信息

树
来自：乐视2017暑期实习生...
难度：
12条回答 9400浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号