美文网首页二叉树之下
NOIP里的均衡二叉树,大家一起来看看

NOIP里的均衡二叉树,大家一起来看看

作者: 沈鸽gugu | 来源:发表于2018-08-21 10:44 被阅读1次

    原题:

    14(第十二届).高度为n的均衡的二叉树是指:如果去掉叶结点及相应的树枝,它应该是高度为n-1的满二叉树。在这里,树高等于叶结点的最大深度,根结点的深度为0,如果某个均衡的二叉树共有2381个结点,则该树的树高为()。

    A. 10 B. 11 C. 12 D. 13

    官方答案:B.11

    我的理解:

    假设答案正确,该均衡二叉树的树高为11。那么,从高为10往上应该是一个满二叉树,即11层(因为根节点高为0,高为10就是11层)2047个结点。那么,剩下的在高为11的有2381-2047=334个结点。因为叶子结点要被截掉,所以高为10的“叶子结点”都要有至少一个子节点。而高为10的结点有1024个,如果每一个“叶子结点”都只有一个子节点,1024>334,就会有一些“叶子结点”没有子节点,而被截掉。这样,截完以后的二叉树就不是满二叉树。而这样,该树就不是一个均衡的二叉树。则题解错误。

    那其他的答案呢?A是10,高为10的满二叉树都只有2047个结点。C是12,需要高为11的满二叉树,即4095个结点。D同理。

    我觉得这题有点不太对,大家一起来看看吧!

    相关文章

      网友评论

      • Endman:我觉得你讲的好像有道理诶

      本文标题:NOIP里的均衡二叉树,大家一起来看看

      本文链接:https://www.haomeiwen.com/subject/djsdiftx.html