首页 > 试题广场 >

关于结点树相同的折半判定树和完全二叉树，以下说法正确的是（&

[单选题]
关于结点树相同的折半判定树和完全二叉树，以下说法正确的是（      ） 
  • 折半判定树的高度与完全二叉树高度一致
  • 折半判定树的高度比完全二叉树高度大
  • 折半判定树的高度比完全二叉树高度小
  • 折半判定树的高度与完全二叉树高度没有关系
查看正确选项
添加回答
掌心里的小雨头像 掌心里的小雨

考点：二叉树的性质--折半判定树和完全二叉树

  • 折半判定树

    • 折半判定树的构造过程其实就是对有序列表二分查找的过程，有序列表的中点是折半判定树的根节点，比根节点小的被分到根节点的左子树，比根节点大的被分到根节点的右子树；
    • 折半判定树的性质：
      • 任意两棵折半查找判定树，若它们的结点个数相同，则它们的结构完全相同
      • 任意结点的左右子树中结点个数最多相差1
      • 任意结点的左右子树的高度最多相差1
      • 任意两个叶子所处的层次最多相差1

  • 完全二叉树：如果二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k 层所有的结点都连续集中在最左边

引用：https://blog.csdn.net/weixin_45655152/article/details/103689188

编辑于 2020-08-23 14:02:19 回复(0)
比风酷头像 比风酷
若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
 折半判定数： 二分法
发表于 2020-02-13 13:57:37 回复(0)
6565949419头像 6565949419
首先折半查找判定树是平衡二叉树，因为任意结点的左右子树的结点数只相差1，那么意味着任意结点的左右子树高度最多也相差1。对于折半查找判定树，如果某一层有结点，那么它的上一层必然是满结点，如果不满，左右子树也只相差1层，如图所示，那么左右结点数就不可能只相差1，至少相差2，与上述矛盾，所以折半查找判定树是更加严格的平衡二叉树，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，因此相同结点数的折半查找判定树和完全二叉树的高度相同。前面1～h-1层结点数都达到最大个数，最后一层多出来的个数相同，那么也意味着高度相同。

发表于 2022-09-14 20:09:27 回复(0)
OPPO内推码_80378832_必过头像 OPPO内推码_80378832_必过
为什么 
折半判定树的高度与完全二叉树高度一致？
发表于 2021-08-01 11:00:32 回复(0)
牛客879654083号头像 牛客879654083号

百度折半判定树画法



发表于 2020-03-22 18:04:41 回复(0)
其华灼灼头像 其华灼灼
折半查找及其二叉判定树简易画法
发表于 2020-02-22 11:52:17 回复(0)
vicyor头像 vicyor
      18                                     12
  12                                  18           14
       14
BST                                   完全二叉树
不一样啊!!!!!
发表于 2020-02-15 12:26:22 回复(2)
Shadow4U头像 Shadow4U
这两个高度都为log2n向上取整。
折半判定树和完全二叉树都为平衡二叉树，节点数又相同，高度肯定相同吧
编辑于 2020-02-04 10:38:33 回复(0)
夏花爱秋叶头像 夏花爱秋叶
既然节点树相同，那么高度肯定相同啦。。
发表于 2020-01-30 11:12:02 回复(0)
vagant头像 vagant
感觉折半查找就是二分查找吧
发表于 2020-01-18 22:05:10 回复(0)
行不更名坐不改姓头像 行不更名坐不改姓
折半判定树是什么东西？
发表于 2020-01-18 13:25:58 回复(3)
2^74207281-1头像 2^74207281-1
应该是这样的吧，关于结点数相同的折半判定树和完全二叉树
发表于 2020-01-17 18:11:29 回复(0)
大谦头像 大谦
有大佬说下的么?
发表于 2020-01-15 15:00:18 回复(1)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 前端工程师 算法工程师 爱奇艺 测试开发工程师 2020 Java工程师
上传者：小小
难度：
13条回答 4369浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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