Question

现有一棵无重复关键字的平衡二叉树（AVL 树）

现有一棵无重复关键字的平衡二叉树（AVL 树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是 （）
A.根结点的度一定为 2
B.树中最小元素一定是叶结点
C.最后插入的元素一定是叶结点
D.树中最大元素一定是无左子树
答案是哪一个，为什么？求大神解答。

Answer 1

D、树中最大元素一定是无左子树。

因为每个结点的左子树的结点的值比该结点的值小，所以树中最大元素一定是无左子树。

BT退化为每个结点 (非叶) 只有两棵子树时，结点的数目最少，叶子也最少。设层号为i则各层结点数为2^(i-1)个，那么高为h的BT最大层号是j时，有h=j-1。

整个树的结点数为s=2^0+2^1+2^2+…+2^h, 故s=2^(h+1)-1。其叶子的个数是2^h。同理，当BT每个非叶结点都有三棵子数时，结点数目最多。

扩展资料：

任意节点的子树的高度差都小于等于1。常见的符合平衡树的有，B树（多路平衡搜索树）、AVL树（二叉平衡搜索树）等。

平衡树可以完成集合的一系列操作, 时间复杂度和空间复杂度相对于“2-3树”要低，在完成集合的一系列操作中始终保持平衡，为大型数据库的组织、索引提供了一条新的途径。

Answer 2

D
根据中序遍历得到降序序列可以知道，每个结点的左子树的结点的值比该结点的值小，因为没有重复的关键字，所以拥有最大值的结点没有左子树。

Answer 3

Answer 4

答案是D；但是想问一下C选项，最后插入的元素可能引起不平衡需要调整，可是调整之后似乎还是叶节点，有什么特例吗？？？