题29
题目
Q:【2015 统考真题】现有一棵无重复关键字的平衡二叉树 (AVL), 对其进行中序遍历可得到一个降序序列.
下列关于该平衡二又树的叙述中, 正确的是 ( ).
A. 根结点的度一定为 2
B. 树中最小元素一定是叶结点
C. 最后插入的元素一定是叶结点
D. 树中最大元素一定是无左子树
分析
A:左边小，右边大，这还是一个降序排列，说明就是一直在输出右边
我的理解和答案似乎是不同的
二叉排序树是指左子树的所有节点的值都小于根节点的值，右子树的所有节点的值都大于根节点的值
解
D
大多数教材将平衡二叉树定义为一种高度平衡的二叉排序树, 二叉排序树的中序序列是一个升序序列, 而题意正好相反。
由此可知, 命题老师认为平衡二叉树仅为一棵满足高度平衡的二叉树, 不一定是二叉排序树。
只有两个结点的平衡二叉树的根结点的度为
中序遍历后得到一个降序序列 (与二叉排序树正好相反), 树中最大元素一定无左子树 (可能有右子树), 这与二叉排序树也正好相反, 也因此不一定是叶结点, B 错误, D 正确。
最后插入的结点可能会导致平衡调整, 而不一定是叶结点, C 错误。