分别用以下方法建立二叉树并用图型显示出来: (1)用先序遍历的输入序列 (2)用层次遍历的输入序列 (3)用先序和中序遍历的结果 (4)最后对所建立的二叉树进行中序线索化,并对此线索树进行中序遍历(不使用栈)。
时间: 2024-02-22 09:55:00 浏览: 84
好的,我来回答你的问题。
1. 用先序遍历的输入序列建立二叉树:
首先,我们需要了解先序遍历的规则:先访问根节点,然后递归访问左子树,最后递归访问右子树。
例如,给定一个先序遍历序列为 {1,2,4,5,3,6,7},我们可以按照以上规则建立二叉树,具体过程如下:
```
1
/ \
2 3
/ \ / \
4 5 6 7
```
2. 用层次遍历的输入序列建立二叉树:
层次遍历的规则是:按照树的层次,从上到下,从左到右访问每个节点。
例如,给定一个层次遍历序列为 {1,2,3,4,5,6,7},我们可以按照以上规则建立二叉树,具体过程如下:
```
1
/ \
2 3
/ \ / \
4 5 6 7
```
3. 用先序和中序遍历的结果建立二叉树:
通过先序和中序遍历序列建立二叉树的过程需要了解如下规则:
- 先序遍历的第一个节点为根节点;
- 在中序遍历中,根节点左边的节点都是左子树的节点,右边的节点都是右子树的节点;
- 通过上述规则,可以递归建立左子树和右子树。
例如,给定先序遍历序列为 {1,2,4,5,3,6,7},中序遍历序列为 {4,2,5,1,6,3,7},我们可以按照以上规则建立二叉树,具体过程如下:
```
1
/ \
2 3
/ \ / \
4 5 6 7
```
4. 对所建立的二叉树进行中序线索化,并对此线索树进行中序遍历(不使用栈):
中序线索化的过程如下:
- 对于每个叶子节点,左指针指向该节点在中序遍历中的前驱节点,右指针指向该节点在中序遍历中的后继节点;
- 对于每个非叶子节点,如果其左子树为空,则将左指针指向该节点在中序遍历中的前驱节点;如果其右子树为空,则将右指针指向该节点在中序遍历中的后继节点。
例如,我们可以对建立的二叉树进行中序线索化,得到以下线索二叉树:
```
4
<- 2 ->
<- 5 1 ->
<- 6 3 ->
-> 7
```
对线索二叉树进行中序遍历的过程如下:
- 找到中序遍历序列中的第一个节点(也就是线索二叉树中最左侧的节点);
- 如果该节点有左子树,则进入左子树中最右侧的节点,并进行相应的操作(如输出节点值);
- 如果该节点没有左子树,则进行相应的操作(如输出节点值),并进入右子树中最左侧的节点;
- 重复以上步骤,直到遍历完所有节点。
由于线索二叉树中的后继节点指向的是中序遍历中的后继节点,因此不使用栈也可以轻松地实现中序遍历。
阅读全文