7. 已知二叉树的先序遍历为:ABCDE, 中序遍历为:CBDAE, 画出可能二叉树
时间: 2023-07-21 09:31:30 浏览: 158
二叉树的几种操作,包括递归先序建立二叉树、先序遍历、中序遍历、后序遍历、非递归的各种遍历
首先,根据先序遍历的性质,可以确定根节点为A;
然后,根据中序遍历的性质,可以将节点分为左子树和右子树,即:
左子树的中序遍历为:CBD,对应的先序遍历为:BCD;
右子树的中序遍历为:AE,对应的先序遍历为:AE。
接下来,我们可以继续递归构建左右子树。
左子树的先序遍历为:BCD,中序遍历为:CBD,可以构建出如下的左子树:
```
B
/ \
C D
```
右子树的先序遍历为:AE,中序遍历为:AE,可以构建出如下的右子树:
```
A
\
E
```
因此,可能的二叉树如下所示:
```
A
/ \
B E
/ \
C D
```
阅读全文