已知一棵二叉树的先序遍历序列和中序遍历序列分别为1 2 4 5 3 6 和 4 2 5 1 3 6 ,画出这颗二叉树并求其后序序列。
时间: 2024-06-08 09:10:46 浏览: 74
二叉树先序和中序求后序
首先根据先序遍历的第一个节点确定根节点,即为1。然后在中序遍历中找到1的位置,可以将中序遍历分为左子树和右子树两部分。左子树的中序遍历为4 2 5,右子树的中序遍历为3 6。
接下来考虑左子树和右子树的先序遍历序列。左子树的先序遍历为2 4 5,右子树的先序遍历为3 6。
对于左子树,其先序遍历的第一个节点为2,因此2为左子树的根节点。根据同样的方法继续划分左右子树,可以得到左子树的先序遍历为4 5,中序遍历为4 2 5;右子树的先序遍历为无,中序遍历为3 6。
对于左子树的左子树,其先序遍历的第一个节点为4,因此4为左子树的左子树的根节点。由于该节点没有左右子树,因此得到左子树的左子树的后序遍历为4。
对于左子树的右子树,其先序遍历的第一个节点为5,因此5为左子树的右子树的根节点。同样地,由于该节点没有左右子树,得到左子树的右子树的后序遍历为5。
对于右子树,其先序遍历的第一个节点为3,因此3为右子树的根节点。由于该节点没有左子树,右子树的后序遍历为6 3。
综上所述,该二叉树的后序遍历为4 5 2 6 3 1。
二叉树的图示如下:
```
1
/ \
2 3
/ \ \
4 5 6
```
阅读全文