设数据集合D={1,12,5,8,3,10,7,13,9},详细说明依次取D中各数据,构造一棵二叉排序树bt
时间: 2023-10-03 17:10:25 浏览: 117
首先,我们需要选择一个结点作为二叉排序树(BST)的根节点。由于数据集合D中的第一个元素为1,我们将其作为根节点。
接下来,我们依次取D中的每个数据,并将它们插入到BST中。
1. 取12,由于12大于1,我们将其插入到根节点的右子树中,得到如下的二叉排序树:
```
1
\
12
```
2. 取5,由于5小于1,我们将其插入到根节点的左子树中,得到如下的二叉排序树:
```
1
/ \
5 12
```
3. 取8,由于8大于1,且小于12,我们将其插入到12的左子树中,得到如下的二叉排序树:
```
1
/ \
5 12
/
8
```
4. 取3,由于3小于1,且小于5,我们将其插入到5的左子树中,得到如下的二叉排序树:
```
1
/ \
5 12
/ /
3 8
```
5. 取10,由于10大于1,且大于5,且小于12,我们将其插入到12的左子树中,得到如下的二叉排序树:
```
1
/ \
5 12
/ / \
3 10 8
```
6. 取7,由于7大于1,且大于5,且小于10,我们将其插入到10的左子树中,得到如下的二叉排序树:
```
1
/ \
5 12
/ / \
3 10 8
/
7
```
7. 取13,由于13大于1,且大于12,我们将其插入到12的右子树中,得到如下的二叉排序树:
```
1
/ \
5 12
/ / \
3 10 13
/ /
7 8
```
8. 取9,由于9大于1,且大于5,且小于10,我们将其插入到10的左子树中,得到如下的二叉排序树:
```
1
/ \
5 12
/ / \
3 10 13
/ / \
7 8 9
```
最终,我们得到了如下的二叉排序树:
```
1
/ \
5 12
/ / \
3 10 13
/ / \
7 8 9
```