在一个空的二叉排序树中依次插入关键字序列为12,7,17,11,16,2,13,9,21,4,请画出所得到的二叉排序树。
时间: 2023-09-13 15:06:28 浏览: 162
对于输入二叉树的排序
依次插入关键字序列12,7,17,11,16,2,13,9,21,4,得到的二叉排序树如下图所示:
```
12
/ \
7 17
/ \ / \
2 11 13 21
/ \
9 16
/
4
```
解释:首先将12作为根节点插入,然后7比12小,所以插入7的左子树中,17比12大,所以插入17的右子树中,11比7大但比12小,所以插入11的左子树中,16比12大但比17小,所以插入16的右子树中,2比7小,所以插入2的左子树中,13比12大但比17小,所以插入13的右子树中,9比7大但比11小,所以插入9的左子树中,21比17大,所以插入21的右子树中,4比2大,所以插入4的右子树中。最终得到的二叉排序树满足左子树中的所有关键字均小于根节点,右子树中的所有关键字均大于根节点。
阅读全文