我要招人

去企业版

首页 > 试题广场 >

下列关于该平衡二叉树的叙述中，正确的是（）。

[单选题]

现有一棵无重复关键字的平衡二叉树（AVL 树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是（）。

```
根结点的度一定为 2
```
```
树中最小元素一定是叶结点
```
```
最后插入的元素一定是叶结点
```
```
树中最大元素一定是无左子树
```

查看答案及解析

推荐

艾晓米Amyfairy

只有两个结点的平衡二叉树的根结点的度为 1 ， A 错误。中序遍历后可以得到一个降序序列，树中最小元素一定无左子树（可能有右子树），因此不一定是叶结点， B 错误。最后插入的结点可能会导致平衡调整，而不一定是叶结点， C 错误。（来自王道论坛）

编辑于 2016-12-01 18:33:24 回复(6)

2019眷顾我

AVL树的定义首先要求该树是二叉查找树（满足排序规则）

发表于 2018-12-12 13:59:33 回复(0)

快说我这信号好

普通搜索树——AVL——RB树——map/set。 template<class T,class Compare = less<T>,class Alloc = allocator<T> > class set; 上面是STL里set的声明，可以看到Compare是个仿函数，所以中序搜索可以升序也可以降序。排序树有两种排序方法： 1.左孩子 < 根节点 < 右孩子（常见） Compare = less<T> 这种情况中序遍历得到的是一个升序序列 2.左孩子 > 根节点 > 右孩子 Compare = greater<T> 这种情况中序遍历得到的是一个降序序列

发表于 2018-04-25 15:07:27 回复(0)

梦境迷离

平衡二叉树=平衡二叉排序树？那么后面那一题左右子树可以交换吗为什么平衡树又能交换了. 这不就是说平衡！=排序？这是什么鬼题目。。

编辑于 2018-02-04 13:53:09 回复(0)

MLDWX

排序树有两种排序方法：

1.左孩子 < 根节点 < 右孩子（常见）

这种情况中序遍历得到的是一个升序序列

2.左孩子 > 根节点 > 右孩子

这种情况中序遍历得到的是一个降序序列

发表于 2017-08-21 17:55:01 回复(0)

小小陈

A：当树只有1个或两个结点的时候，根结点的度不可能为2

B：因为中序遍历得到的是个降序序列，所以最小的元素一定是最后一个遍历到的，中序遍历是左根右，当没有右子树的时候，最小元素是根

C：如果插入的元素破坏了平衡性，会进行调整

D：因为中序遍历是个降序序列，可知左儿子大于父结点，所以最大元素没有左子树

发表于 2017-02-14 22:05:30 回复(1)

zhaobinw

ABC选项均不一定。只看D，若最大元素有左子树X，则采用中序遍历后X一定在最大元素前，则不是降序序列。即最大元素一定是中序遍历的第一个元素。

发表于 2016-11-24 11:52:05 回复(0)

华白纸

A：当树只有1个或两个结点的时候，根结点的度不可能为2

B：因为中序遍历得到的是个降序序列，所以最小的元素一定是最后一个遍历到的，中序遍历是左根右，当没有右子树的时候，最小元素是根

C：如果插入的元素破坏了平衡性，会进行调整

D：因为中序遍历是个降序序列，可知左儿子大于父结点，所以最大元素没有左子树

发表于 2017-08-09 13:10:49 回复(0)

救赎i_

对于选项AB，可以举反例，A和B的反例如下，可以发现根的度为1，最小元素1不是叶子结点，A、B错误。

对于选项C，如果是二叉排序树，则C对，但是题目给的是AVL树，最后插入的元素会导致不平衡，引起旋转，C错误。

对于选项D，可以用反证法，由题目可得左子树 > 根 > 右子树，假设最大元素是M，且它有左子树，但是由二叉排序树的特性可知左子树的元素就比它大，与它是最大元素矛盾，故它没有左子树，D正确。

发表于 2022-07-19 20:42:58 回复(0)

学习吧。。

中序遍历选出最终元素肯定没有左子树

发表于 2022-01-02 14:33:20 回复(0)

简.201904161228604

平衡二叉树不应该是一棵二叉排序树吗，那么按照二叉排序树的定义它的中序序列应该是一个升序序列啊，为啥是降序序列？？？？

发表于 2021-09-01 11:46:49 回复(0)

小🐑找工作

AVL首先满足二叉搜索树（左小于中小于右）中序遍历是中左右，是降序序列，所以中最大。因此d正确

发表于 2023-08-30 18:44:38 回复(0)

在找内推的芹菜很不想上网课

最小元素一定是叶节点最小元素节点为a 假如a有左节点，左节点比他大，然后在中序输出的时候要先于a输出，同时也满足降序假如a有右节点，右节点比他小，在中序的输出要后于a输出，导致a不是最小值，所以不可能有右节点那么他可能是有左节点，可是王道的解析却说他不可能有左节点，搞不懂。各位大佬，我上面的判断有错吗 (T＿T)

发表于 2022-10-06 19:23:09 回复(0)