给定关键字序列{25,18,3,21, 65,98,31,19, 22,12,0,29, 101},绘制与之对应的二叉排序树, 画 出顺次删除关键字0、 22 、25的过程
时间: 2025-01-01 14:39:43 浏览: 8
首先,我们构建一个二叉搜索树(Binary Search Tree,BST)需要按照每个元素值大小插入节点,并保持左子树小于根节点,右子树大于根节点的性质。给定的序列为 {25, 18, 3, 21, 65, 98, 31, 19, 22, 12, 0, 29, 101}。
1. 首先插入第一个元素25作为根节点:
```
25
/ \
/ \
18 65
/ \ /
3 21 98
```
2. 插入22:
```
25
/ \
/ \
18 65
/ \ / \
3 21 98 22
```
22较小,所以插入到18和21之间。
3. 插入0:
```
25
/ \
/ \
18 65
/ \ / \
3 21 98 22
\
0
```
0是最小的,所以它会成为22的左子节点。
4. 删除关键字0:
由于0是叶子节点,直接删除即可,不会影响其他节点结构。此时二叉搜索树变为:
```
25
/ \
/ \
18 65
/ \ / \
3 21 98 22
```
5. 删除关键字22:
22有一个子节点,即0(已删除),因此找到22的右兄弟(如果存在)并替换其位置。这里22没有右兄弟,我们将其父节点18的右指针指向空(表示删除了22):
```
25
/ \
/ \
18 65
/ / \
3 98 21
```
6. 删除关键字25:
同样的过程,查找25的右子树中的最大值(这里是98),然后将98移动到25的位置并删除25,得到新的树结构:
```
65
/ \
/ \
18 98
/ /
3 21
\
22
```
这就完成了从初始序列到删除特定关键字的操作。
阅读全文