🏷️ 知识点：平衡二叉树
若将关键字 1,2,3,4,5,6,7 依次插入到初始为空的平衡二叉树 T 中，则 T 中平衡因子为 0 的分支结点的个数是（ ）。
A.0
B.1
C.2
D.3
[tag_link] 正确答案：D利用 7 个关键字构建平衡二叉树 T，平衡因子为 0 的分支结点个数为 3，构建的平衡二叉树如下图所示。构造及调整的过程如下：
在下图所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37 所在结点的左、右子结点中保存的关键字分别是()。
[tag_link]
正确答案：C
插入 48 以后，该 AVL 根结点的平衡因子由 -1 变为 -2, 在最小不平衡子树根结点的右子树 (R) 的左子树 (L) 中插入新结点引起的不平衡属于 RL 型平衡旋转，需要做两次旋转操作（先右旋后左旋）。24 13 53 37 90 24 13 53 37 90 48 37 24 53 13 48 90 RL 旋转 调整后，关键字 37 所在结点的左、右子结点中保存的关键字分别是 24、53。
若平衡二叉树的高度为 6 ，且所有非叶结点的平衡因子均为 1 ，则该平衡二叉树的结点总数为（ ）。
A. 10
B. 20
C. 32
D. 33
[tag_link]
正确答案：B
所有非叶结点的平衡因子均为 1，即平衡二叉树满足平衡的最少结点情况，如下图所示。
对于高度为 N、左右子树的高度分别为 N-1 和 N-2、所有非叶结点的平衡因子均为 1 的平衡二叉树，总结点数的公式为：CN=CN−1+CN−2+1,C1=1,C2=2,C3=2+1+1=4，可推出C6=20。
现有一棵无重复关键字的平衡二叉树（AVL 树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是（ ）。
A. 根结点的度一定为 2 B. 树中最小元素一定是叶结点 C. 最后插入的元素一定是叶结点 D. 树中最大元素一定是无左子树
[tag_link] 正确答案：D只有两个结点的 平衡二叉树 的根结点的度为 1，A 错误。中序遍历后可以得到一个降序序列，树中最大元素一定无左子树（可能有右子树），因此不一定是叶结点，B 错误。最后插入的结点可能会导致平衡调整，而不一定是叶结点，C 错误。
在任意一棵非空平衡二叉树（AVL 树）T1 中，删除某结点 v 之后形成平衡二叉树 T2 ，再将 v 插入 T2 形成平衡二叉树 T3 。下列关于 T1 与 T3 的叙述中，正确的是（ ）。
I.若 v 是 T1 的叶结点，则 T1 与 T3 可能不相同
II.若 v 不是 T1 的叶结点，则 T1 与 T3 一定不相同
III.若 v 不是 T1 的叶结点，则 T1 与 T3 一定相同
A. 仅 I B. 仅 II C. 仅 I、II D. 仅 I、III
[tag_link]
正确答案：A
非空平衡二叉树中插入结点，在失去平衡调整前，一定插入在叶结点的位置。若删除的是 T1 的叶结点，则删除后平衡二叉树不会失去平衡，即不会发生调整，再插入此结点得到的二叉平衡树 T1 与 T3 相同;若删除后平衡二叉树失去平衡而发生调整，再插入结点得到的二叉平衡树 T3 与 T1 可能不同。I 正确。例如，如下图所示，删除结点 0，平衡二叉树失衡调整，再插入结点 0 后，平衡二叉树和以前不同。对于比较绝对的说法 II 和 III，通常只需举出反例即可。
若删除的是 T1 的非叶结点，且删除和插入操作均没有导致平衡二叉树的调整 (这时可以首先想到删除的结点只有一个孩子的情况)，则该结点从非叶结点变成了叶结点，T1 与 T3 显然不同。例如，如下图所示，删除结点 2，用右孩子结点 3 填补，再插入结点 2，平衡二叉树和以前不同。
若删除的是 T1 的非叶结点，且删除和插入操作后导致了平衡二叉树的调整，则该结点有可能通过旋转后继续变成非叶结点，T1 与 T3 相同。例如，如下图所示，删除结点 2，用右孩子结点 3 填补，再插入结点 2，平衡二叉树失衡调整，调整后的平衡二叉树和以前相同。
下列二叉排序树中，满足平衡二叉树定义的是()。
A.
B.
C.
D.
[tag_link]
正确答案：B
根据 AVL 的定义有，任意结点的左、右子树高度差的绝对值不超过 1。
而其余 3 个 选项均可以找到不符合该条件的结点。
在做题过程中，如果答案不太明显，可以把每个非叶结点的平衡因子都写出来再进行判断。
如图所示为一棵平衡二叉树（字母不是关键字），在结点 D 的右子树上插入结点 F 后，会导致该平衡二叉树失去平衡，则调整后的平衡二叉树中平衡因子的绝对值为 1 的分支结点数为（ ）。
A. 0 B. 1 C. 2 D. 3
[tag_link]
正确答案：B
考查平衡二叉树的旋转。 由于在结点 A 的右孩子（R）的右子树（R）上插入新结点 F，A 的平衡因子由 -1 减至 -2，导致以 A 为根的子树失去平衡，需要进行 RR 旋转（左单旋）。
RR 旋转的过程如上图所示，将 A 的右孩子 C 向左上旋转代替 A 成为根结点，将 A 结点向左下旋转成为 C 的左子树的根结点，而 C 的原来的左子树 E 则作为 A 的右子树。 故，调整后的平衡二叉树中平衡因子的绝对值为 1 的分支结点数为 1。
注意：平衡旋转的操作都是在插入操作后，引起不平衡的最小不平衡子树上进行的，只要将这个最小不平衡子树调整平衡，则其上级结点也将恢复平衡。
由元素序列（27,16,75,38,51）构造平衡二叉树，则首次出现的最小不平衡子树的根（即离插入结点最近且平衡因子的绝对值为 2 的结点）是（ ）。
A. 27 B. 38 C. 51 D. 75
[tag_link]
正确答案：D
按序列（27,16,75,38,51）依次插入构造平衡二叉树：
- 插入 27 和 16 后，树平衡。 >
- 插入 75 后，树仍平衡。 >
- 插入 38 后，各节点平衡因子绝对值均不超过 1，树平衡。 >
- 插入 51 后，节点 38 的平衡因子变为 -1（平衡），但节点 75 的左子树高度为 1、右子树高度为 -1（空），平衡因子计算为 1 - (-1) = 2，绝对值首次达到 2，成为不平衡节点。 > 继续向上检查，节点 27 的平衡因子也变为 -2，但节点 75 是离插入点 51 最近的不平衡节点，因此最小不平衡子树的根是 75。 >
含有 20 个结点的平衡二叉树的最大深度为（ ）。
A. 4 B. 5 C. 6 D. 7
[tag_link]
正确答案：C
平衡二叉树（例如 AVL 树）要求每个结点的左右子树高度差不超过 1。 对于给定的结点数，最大深度对应于结点数最少的平衡二叉树结构——为了最大化深度，树应尽可能“瘦”，但平衡条件限制了子树的深度差。
设深度为
（根结点深度为 1）的平衡二叉树的最小结点数为 ，满足递归关系：
其中 ， 。
计算可得：
现有 20 个结点，因为 ，即深度为 6 时至少需要 20 个结点，而深度为 7 至少需要 33 个结点（ ），所以 20 个结点可以构建深度为 6 的平衡二叉树，但无法构建深度为 7 的平衡二叉树。
因此，最大深度为 6。
在含有 15 个结点的平衡二叉树上，查找关键字为 28（存在该结点）的结点，则依次比较的关键字有可能是（ ）。
A. 30,36 B. 38,48,28 C. 48,18,38,28 D. 60,20,50,40,38,28
[tag_link]
正确答案：C
在平衡二叉树（如AVL树）中查找结点时，比较序列必须遵循二叉搜索树的性质：若目标值小于当前结点值，则进入左子树； 若大于，则进入右子树。 同时，树有15个结点且平衡，高度约为 log₂15≈4，因此查找路径上的结点数通常不超过4个（对应高度为3）。
- 选项A：比较30后，28<30应进入左子树，但下一个比较36>30，不可能进入左子树，违反二叉搜索树性质。
- 选项B：比较38后，28<38应进入左子树，但下一个比较48>38，不可能进入左子树，同样违反性质。
- 选项C：序列48,18,38,28符合二叉搜索树性质：28<48进入左子树； 28>18进入右子树； 28<38进入左子树； 找到28。 路径长度为4，对应树高度为3，对于15个结点的平衡二叉树是可能的，可以通过调整其他结点保持平衡。
- 选项D：序列60,20,50,40,38,28虽符合二叉搜索树性质，但路径长度为6，对应树高度至少为5。 对于15个结点的平衡二叉树，高度为5至少需要20个结点（如AVL树的最小结点数要求），因此不可能在保持平衡的前提下存在这样的查找路径。
综上，只有选项C可能。
给定平衡二叉树如下图所示，插入关键字 23 后，根中的关键字是（ ）。
A. 16 B. 20 C. 23 D. 25
[tag_link]
正确答案：D
根据 AVL 旋转方法 可知，这题采用 RL 型旋转，旋转后树的结构为：
25
/ \
20 30
/ \ \
16 23 40
根结点为 25
已知平衡二叉树（AVL 树）的定义为：树中任意一个节点的左右子树的高度差的绝对值不超过 1，且左右子树均为平衡二叉树。若某平衡二叉树的高度为 4（根节点的高度记为 1），则其根节点的左右子树的节点数之差最多为（ ）
A. 1 B. 2 C. 3 D. 5
[tag_link]
正确答案：D
**【解析】**平衡二叉树高度为 4（根节点高度为 1），因此左右子树的高度组合为：
- 两者均为 3，或
- 一个为 3、另一个为 2。为最大化节点数之差，应使较高子树取最大节点数，较低子树取最小节点数。
- 高度 3 的平衡二叉树最大节点数为 7（满二叉树），
- 高度 2 的最小节点数为 2（根节点加一个子节点），此时节点数之差为7−2=5。若左右子树高度均为 3，节点数之差最大为7−4=3。因此，根节点的左右子树节点数之差最多为 5。
从二叉树的任一结点出发到根的路径上，所经过的结点序列必按其关键字降序排列的是（ ）。
A. 二叉排序树 B. 大顶堆 C. 小顶堆 D. 平衡二叉树
[tag_link]
正确答案：C
在小顶堆中，每个结点的关键字都小于或等于其子结点的关键字。
因此，从任意结点出发，向上遍历父结点直至根结点，所经过的结点关键字会逐渐减小或保持不变，即序列必然是降序排列。
对于大顶堆，父结点的关键字大于或等于子结点的关键字，路径上的结点关键字序列是升序排列，不符合要求。 二叉排序树和平衡二叉树的关键字排列没有统一规则，路径上的结点序列不一定满足降序排列。
（13 分）已知一棵二叉树采用二叉链表存储，结点结构为：
root 指向根结点。请编写算法判断该二叉树是否是平衡二叉树，即二叉树中任意结点的左右子树的深度相差不超过 1。例如下图所示的二叉树就是一棵平衡二叉树。
要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。
[tag_link]
【答案】
（1）基本设计思想：采用递归后序遍历二叉树，在计算每个结点高度的同时判断其左右子树是否平衡。递归函数返回当前子树的高度，若子树不平衡则返回 -1 作为标志。对于每个结点，先递归检查其左右子树，若任一子树返回 -1，则当前子树不平衡；否则计算左右子树高度差，若超过 1 则返回 -1，否则返回当前子树高度（即左右子树最大高度加 1）。最终，若根结点对应的递归返回值不为 -1，则二叉树是平衡的。
（2）算法描述（C 语言）： #include <stdlib.h> // 用于 abs 函数 #include <stdbool.h> // 用于 bool 类型 struct Node { struct Node * lchild ; int data ; struct Node * rchild ; }; // 辅助函数：检查以 root 为根的子树是否平衡，返回高度；若不平衡返回 -1 int checkBalance ( struct Node * root ) { if ( root == NULL ) { return 0 ; // 空树高度为 0，平衡 } // 递归检查左子树 int leftHeight = checkBalance ( root -> lchild ); if ( leftHeight == - 1 ) { return - 1 ; // 左子树不平衡，向上传递 } // 递归检查右子树 int rightHeight = checkBalance ( root -> rchild ); if ( rightHeight == - 1 ) { return - 1 ; // 右子树不平衡，向上传递 } // 检查当前结点左右子树高度差 if ( abs ( leftHeight - rightHeight ) > 1 ) { return - 1 ; // 当前结点不平衡 } // 返回当前子树高度 return ( leftHeight > rightHeight ? leftHeight : rightHeight ) + 1 ; } // 主函数：判断二叉树是否平衡 bool isBalanced ( struct Node * root ) { return checkBalance ( root ) != - 1 ; } 【解析】 该算法基于递归实现，核心思想是在计算结点高度时同步判断平衡性，避免重复遍历。checkBalance 函数采用后序遍历顺序：先递归处理左右子树，再处理当前结点。若子树不平衡（返回 -1），则立即向上返回，无需进一步计算；否则比较左右子树高度差，若超过 1 则返回 -1 表示不平衡，否则返回当前子树高度。isBalanced 函数通过调用 checkBalance 检查返回值是否为 -1 来判断整棵树的平衡性。算法中每个结点仅访问一次，时间复杂度为 O(n)，n 为结点数；递归栈空间复杂度为 O(h)，h 为树高。这种设计既高效又简洁，符合题目要求。
右图是一棵逻辑上的树 T, 则在关于该树的存储结构的叙述 中，错误的是()。
A. 若 T 采用双亲表示法，则有9个指向双亲的指针 B. 若 T 采用孩子表示法，则在 T 中查找某个结点的孩子比 双亲表示法更方便 C. 若 T 采用孩子兄弟表示法，则在 T中查找某个结点的双 亲的时间复杂度为O(1) D. 双亲表示法是顺序存储结构，孩子表示法和孩子兄弟表示法通常是链式存储结构
[tag_link]
正确答案：C
将下面一个由3棵树组成的森林转换为二叉树。
[tag_link]
D