输入关键字序列(16,3,7,11,9,26,18,14,15),给出构造一棵平衡二叉树的过程。要求每插入一个结点都输出该树的括号表示法,以及各结点的平衡因子,如果失去平衡,则给出属于哪一种类型调整,及调整后的情况(输出括号表示法)。最后再删除指定结点后,恢复平衡,再输出平衡二叉树的情况
时间: 2023-12-10 08:02:47 浏览: 225
好的,我会根据您的要求逐步构建这棵平衡二叉树。
首先,我们需要将给定的关键字序列进行排序,以便于构建平衡二叉树。排序后的序列为:3,7,9,11,14,15,16,18,26。
接下来,我们将序列的中间元素 14 插入作为树的根节点。此时,树为空,根节点的平衡因子为 0。
```
[14(0)]
```
接着,我们依次将剩下的元素插入二叉树中。插入 3,树的状态如下:
```
[14(1)]
/ \
[3(0)] [null]
```
插入 7,树的状态如下:
```
[14(1)]
/ \
[3(0)] [7(0)]
```
插入 9,树的状态如下:
```
[14(2)]
/ \
[7(1)] [null]
/ \
[3(0)] [9(0)]
```
插入 11,树的状态如下:
```
[14(2)]
/ \
[7(1)] [null]
/ \
[3(0)] [11(0)]
/ \
[9(0)] [null]
```
插入 15,树的状态如下:
```
[14(2)]
/ \
[7(1)] [15(0)]
/ \ \
[3(0)] [11(0)] [18(0)]
/ \
[9(0)] [null]
```
插入 16,树的状态如下:
```
[14(-1)]
/ \
[7(0)] [15(-1)]
/ \ / \
[3(0)] [11(-1)] [18(0)] [16(0)]
/ \
[9(0)] [null]
```
插入 18,树的状态如下:
```
[14(-2)]
/ \
[7(0)] [15(-1)]
/ \ / \
[3(0)] [11(-1)] [18(1)] [16(0)]
/ \
[9(0)] [null]
```
插入 26,树的状态如下:
```
[14(-2)]
/ \
[7(0)] [18(0)]
/ \ / \
[3(0)] [11(-1)] [15(0)] [26(0)]
/ \
[9(0)] [16(0)]
```
目前,这棵平衡二叉树已经完成构建。接下来,我们尝试删除结点 11。
从根节点开始查找 11,发现它是 7 的右子节点的左子节点。因此,我们需要以 11 为根节点做一次右旋操作,得到以下状态:
```
[14(-2)]
/ \
[7(0)] [18(0)]
/ \ / \
[3(0)] [11(0)] [15(0)] [26(0)]
/ \
[9(0)] [16(0)]
```
此时,平衡二叉树已经恢复平衡。
阅读全文