首页 > 试题广场 >

下列各树形结构中,哪些是平衡二叉查找树:

[单选题]
下列各树形结构中，哪些是平衡二叉查找树： 
  •  	    4
            / \
           3   5
          /     \
         2       8
        /         \
       1           9

  •  	      7
             / \
            2   8
           / \
          1   4
             / \
            3   5

  • 	       5
             /   \
            2     8
           / \   /
          1   4 7
             /
            3

  • 		7
              /   \
             2     8
            / \   /
           1   4 6
              /
             3
查看正确选项
添加回答
牛客983574号头像 牛客983574号
A的3、5节点左右子树不平衡
发表于 2016-09-08 19:03:13 回复(0)
Miss.Zhou头像 Miss.Zhou
谁能解释一下图是怎么读出来的
发表于 2016-03-30 23:46:41 回复(1)
好学上进头像 好学上进
二叉平衡查找树：
左子树中所有节点的值小于根的值，右子树中的所有节点的值大于根的值
左右子树的高度之差的绝对值为0或1
一看，A、B就不满足第2条
D不满足第1条
发表于 2015-12-04 23:04:22 回复(13)
空空以空空头像 空空以空空
这道题倒是很好的让我彻底搞明白了平衡树和排序（查找）树
  • 平衡二叉树，或是一棵空树，或符合以下特性：
     【平衡特性1】：左子树的深度和右子树的深度相差不能超过1，可以是0（代表左右子树深度一样）、-1（代表左子树比右子树少一层）、1（代表左子树比右子树多一层）
    【平衡特性2】它的左右子树也要是平衡二叉树
  • 查找树，或是一棵空树，或满足符合以下特性：
    【查找特性1】：若左子树不为空，左子树节点所有的值均要小于根节点；
   【查找特性2】： 若右子树不为空，右子树节点所有的值均要大于根节点；
    【查找特性3】它的左右子树也要是查找树

据此，我们可以排除掉AB。

因为A中只有根节点满足了【平衡特性1】，而它的左孩子3并没有右子树，右孩子5并没有左子树，左子树的平衡因子是2。
B中，左子树深度是2，右子树深度是0，不是平衡树
D中，根节点的右子树不符合条件，节点6，小于根节点7，不符合【查找特性2】

发表于 2017-09-02 17:13:27 回复(0)
憨人要找个好工作头像 憨人要找个好工作
A为什么不对????????????????????????????????????????????
发表于 2016-08-02 13:01:43 回复(5)
我努力了，剩下的由上天了头像 我努力了，剩下的由上天了
平衡二叉查找树的三个特点
发表于 2019-05-09 22:32:58 回复(0)
我是俊生啊头像 我是俊生啊
二叉平衡查找树：
左子树中所有节点的值小于根的值，右子树中的所有节点的值大于根的值
左右子树的高度之差的绝对值为0或1
发表于 2017-08-20 10:37:18 回复(0)
任我游头像 任我游
平衡二叉树是平衡因子的绝对值不超过1的二叉排序树。。。
发表于 2017-08-06 09:31:18 回复(0)
钟爱一生头像 钟爱一生
A为什么错了
发表于 2017-03-10 20:59:50 回复(1)
Tahara头像 Tahara
都不是平衡树。
发表于 2016-09-22 16:21:53 回复(0)
Faith~doit头像 Faith~doit
D选项中右子树的6小于根7，不满足定义
发表于 2016-02-19 17:38:03 回复(0)
提交观点

问题信息

搜狗 算法工程师 树
来自：搜狗2016 C++工...
难度：
11条回答 9062浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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