利用先序遍历创建二叉树,并给出相应二叉树的中序遍历结果。
时间: 2024-01-23 15:39:14 浏览: 84
Java实现先序遍历二叉树
假设先序遍历结果为:A B D G E C F H
根据先序遍历的规则,我们可以知道根节点是A,因此我们可以创建一个以A为根节点的二叉树。
接下来我们需要确定A的左右子树。我们可以通过查看中序遍历结果来确定。中序遍历结果为:G D B E A F H C
我们可以发现,A的左子树中的所有节点在中序遍历结果中都在A的左边,而A的右子树中的所有节点在中序遍历结果中都在A的右边。
因此,我们可以将中序遍历结果拆分为左右子树的部分:G D B E为左子树,F H C为右子树。
接下来,我们可以利用同样的方法递归的创建左右子树。左子树的先序遍历结果为:B D G E,中序遍历结果为:G D B E。右子树的先序遍历结果为:C F H,中序遍历结果为:F H C。
最终得到的二叉树如下所示:
```
A
/ \
B C
/ \ \
D E F
\ \
G H
```
中序遍历结果为:G D B E A F H C。
阅读全文