输入关键字序列(16,3,7,11,9,26,18,14,15),给出构造一棵平衡二叉树的过程。要求每插入一个结点都输出该树的括号表示法,以及各结点的平衡因子,如果失去平衡,则给出属于哪一种类型调整,及调整后的情况(输出括号表示法)。最后再删除指定结点后,恢复平衡,再输出平衡二叉树的情况。
时间: 2023-11-26 22:02:41 浏览: 52
首先,我们按照输入序列构造一棵二叉排序树:
```
16
/ \
3 26
/ \
18 -
/ \
14 15
/ \
11 -
/ \
7 9
```
这棵二叉排序树并不是一棵平衡二叉树,接下来我们需要对其进行调整,使之成为一棵平衡二叉树。
首先,我们需要计算每个结点的平衡因子。对于任意一个结点,它的平衡因子等于其左子树的高度减去右子树的高度。对于平衡二叉树,任意节点的平衡因子必须满足 $-1 \leqslant \text{平衡因子} \leqslant 1$,否则该节点所在的子树就不平衡。
```
16(+2)
/ \
3(-1) 26(-1)
/ \
18(0) -
/ \
14(0) 15(-1)
/ \
11(-1)-
/ \
7(0) 9(0)
```
我们可以发现,节点16、3、26、18和15的平衡因子不符合要求,它们所在的子树不平衡。接下来,我们需要对这些不平衡的子树进行调整。
首先考虑节点16所在的子树,我们可以发现,其右子树的高度大于左子树的高度,因此需要进行左旋操作。左旋操作的目的是将右子树中较低的节点提升为根节点,同时将原来的根节点降为左子树的节点。执行左旋操作后,节点16的平衡因子变为0,节点3的平衡因子变为1。
```
3(0)
/ \
16(0) 26(-1)
/ \
14 15
/ \
7 9
```
接下来,考虑节点3所在的子树,我们可以发现,其左子树的高度大于右子树的高度,因此需要进行右旋操作。右旋操作的目的是将左子树中较高的节点提升为根节点,同时将原来的根节点降为右子树的节点。执行右旋操作后,整棵树变为:
```
14(0)
/ \
3(0) 16(0)
/ \ / \
7 9 15 26(-1)
/ \
18(0) -
```
可以发现,整棵树已经成为了一棵平衡二叉树。
接下来,我们需要删除指定的节点,恢复平衡。假设我们要删除节点18,删除后的树为:
```
14(0)
/ \
3(0) 16(0)
/ \ / \
7 9 15 26(-2)
\
19(0)
```
我们可以发现,节点26的平衡因子为-2,不符合要求,因此需要进行调整。由于节点26的右子树的平衡因子为-1,因此需要进行左旋操作。左旋操作后,节点26的平衡因子变为0,节点16的平衡因子变为-1。
```
14(0)
/ \
3(0) 16(-1)
/ \ / \
7 9 15 26(0)
\
19(0)
```
接下来,考虑节点16所在的子树,我们可以发现,其右子树的平衡因子为0,不需要进行调整。整棵树已经恢复平衡。
最终平衡二叉树的结构为:
```
14(0)
/ \
3(0) 16(-1)
/ \ / \
7 9 15 26(0)
\
19(0)
```