2. 考研
  3. 如右图所示为一棵平衡二叉树(字母不是关键字)，在结点D的右子树上插入结点F后，会导致该平衡二叉树失去平衡，则调整后的平衡二叉树中平衡因子的绝对值为1的分支结点数为( )。

如右图所示为一棵平衡二叉树(字母不是关键字)，在结点D的右子树上插入结点F后，会导致该平衡二叉树失去平衡，则调整后的平衡二叉树中平衡因子的绝对值为1的分支结点数为( )。

admin2019-12-10  45
问题 如右图所示为一棵平衡二叉树(字母不是关键字)，在结点D的右子树上插入结点F后，会导致该平衡二叉树失去平衡，则调整后的平衡二叉树中平衡因子的绝对值为1的分支结点数为(  )。
选项 A、0
B、1
C、2
D、3
答案B
解析 考查平衡二叉树的旋转。由于在结点A的右孩子(R)的右子树(R)上插入新结点F，A的平衡因子由一1减至一2，导致以A为根的子树失去平衡，需要进行RR旋转(左单旋)。
    RR旋转的过程如上图所示，将A的右孩子C向左上旋转代替A成为根结点，将A结点向左下旋转成为C的左子树的根结点，而C的原来的左子树E则作为A的右子树。故，调整后的平衡二叉树中平衡因子的绝对值为1的分支结点数为1。

    注意：平衡旋转的操作都是在插入操作后，引起不平衡的最小不平衡子树上进行的，只要将这个最小不平衡子树调整平衡，则其上级结点也将恢复平衡。
转载请注明原文地址:https://jikaoti.com/ti/8vDjFFFM
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)