将{ 3, 8, 9, 1, 2, 6 }依次插入初始为空的二叉搜索树。则该树的后序遍历结果是:
时间: 2023-10-07 16:12:45 浏览: 646
插入顺序不同,得到的二叉搜索树也不同,但是由于二叉搜索树的性质,它们的中序遍历结果是相同的。所以我们先将这个序列排序,得到{1, 2, 3, 6, 8, 9},然后按照中序遍历的顺序依次插入,得到如下的二叉搜索树:
```
6
/ \
2 8
/ \ \
1 3 9
```
该树的后序遍历结果是:{1, 3, 2, 9, 8, 6}。
相关问题
将{ 3, 8, 9, 1, 2, 6 }依次插入初始为空的二叉排序树。则该树的后序遍历结果是: A. 1, 2, 8, 6, 9, 3 B. 2, 1, 3, 6, 9, 8 C. 1, 2, 3, 6, 9, 8 D. 2, 1, 6, 9, 8, 3
### 回答1:
答案是D.
依次插入{ 3, 8, 9, 1, 2, 6 },得到的二叉排序树如下:
```
3
/ \
1 8
\ \
2 9
/
6
```
该树的后序遍历结果是:2, 1, 6, 9, 8, 3。
### 回答2:
将给定的元素{ 3, 8, 9, 1, 2, 6 }依次插入初始为空的二叉排序树中,可以得到如下树状结构:
3
/ \
1 8
\ \
2 9
/
6
对这棵二叉排序树进行后序遍历,即先访问左子树,再访问右子树,最后访问根结点。按照这个顺序,遍历的结果为:2, 1, 6, 9, 8, 3。
所以,该树的后序遍历结果应为 D. 2, 1, 6, 9, 8, 3。
### 回答3:
将 { 3, 8, 9, 1, 2, 6 } 依次插入空的二叉排序树,插入顺序为 3, 8, 9, 1, 2, 6。根据二叉排序树的性质,较小的数字会插入到左子树,较大的数字会插入到右子树。
首先将 3 插入空树,得到:
3
然后将 8 插入到树中,由于 8 大于根节点 3,所以插入到右子树:
3
\
8
接下来将 9 插入到树中,由于 9 大于根节点 3,所以插入到右子树:
3
\
8
\
9
继续将 1 插入到树中,由于 1 小于根节点 3,所以插入到左子树:
3
/
1
\
8
\
9
然后将 2 插入到树中,由于 2 小于根节点 3,所以插入到左子树:
3
/
1
\
2
\
8
\
9
最后将 6 插入到树中,由于 6 大于根节点 3,所以插入到右子树:
3
/
1
\
2
\
8
\
9
\
6
所以该二叉排序树的后序遍历结果为 A. 1, 2, 8, 6, 9, 3。
将{ 32, 2, 15, 65, 28, 10 }依次插入初始为空的二叉搜索树。则该树的前序遍历结果是:
二叉搜索树的插入过程如下:
1. 将32作为根节点插入,得到如下树:
```
32
/ \
NULL NULL
```
2. 将2插入,得到如下树:
```
32
/ \
2 NULL
/ \
NULL NULL
```
3. 将15插入,得到如下树:
```
32
/ \
2 NULL
/ \
NULL 15
/ \
NULL NULL
```
4. 将65插入,得到如下树:
```
32
/ \
2 65
/ \ / \
15 NULL
/ \ / \
NULL NULL NULL NULL
```
5. 将28插入,得到如下树:
```
32
/ \
2 65
/ \ / \
15 NULL
/ \
28 NULL
/ \
NULL NULL
```
6. 最后将10插入,得到如下树:
```
32
/ \
2 65
/ \ / \
15 NULL
/ \
28 NULL
/ \
10 NULL
\
NULL
```
因此,该树的前序遍历结果是32 2 15 28 10 65。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)