首页 > 试题广场 >

现有一棵无重复关键字的平衡二叉树(AVL 树),对其进行中序

[单选题]
现有一棵无重复关键字的平衡二叉树(AVL 树),对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中,正确的是?
  • 根结点的度一定为 2
  • 树中最小元素一定是叶结点
  • 最后插入的元素一定是叶结点
  • 树中最大元素一定是无左子树

本题目明说了是降序序列。

A. 不一定嘛。只有根结点也可以。

B. 中序遍历:LPR。当没有R的时候,最小元素是P,它不是叶子结点。

C. 因为要进行平衡调整,所以不一定。 LR旋转和RL旋转,最后插入的结点都可能成为根节点【LR:左孩子的右子树本来就是空时;RL:右孩子的左子树本来就是空时】。比如:


D. 中序遍历:LPR。如果有左子树,则P比左子树更小,不会是最大元素。

 【来自:数据结构考研冯强】

发表于 2020-04-30 10:03:46 回复(4)
平衡二叉树是一颗二叉搜索树(我也不知道为什么,就是这么规定的),中序遍历得到一个降序序列,说明左节点值>父节点>右节点
如果最大元素有左子树,则左子树的值就比最大元素的值大,所以不可能有左子树,其他的选项可以对着上面的概念看。
发表于 2019-09-28 16:32:00 回复(2)
有没有能画出来题目中描述的这样的二叉排序树的,怎么感觉题目有问题啊,二叉排序树中序遍历不应该怎么样都是是升序吗?平衡二叉树又属于二叉排序树,那平衡二叉树遍历怎么样不都应该也是升序吗? 题目中怎么会遍历的结果变成降序啊?  如果存在这种树可以画出来看看吗? 小白实在不理解,望各位大神不吝赐教。 
发表于 2022-04-04 14:37:34 回复(3)
选D
一开始以为是常见的升序,看错了,如果是降序的话确实D为正解,如果存在最大元素存在左子树,则一定有元素比最左元素要大,故不符合题意。
发表于 2020-10-30 20:26:32 回复(0)