前序遍历abcdefghi中序遍历dcbagfhei画二叉树
时间: 2023-02-26 19:48:41 浏览: 70
很高兴为你解答:二叉树的前序遍历abcdefghi中序遍历dcbagfhei的画法如下:
a
/ \
b c
/ \ \
d e f
/ \ / \
g h i
相关问题
已知一棵二叉树的前序遍历序列和中序遍历序列分别为ABCDEFGHI和BCAEDGHEL写出后序序列?
根据二叉树前序遍历和中序遍历的特点,可以得知该二叉树的根节点为A,且左子树的前序遍历序列为BCDEFGH,中序遍历序列为BCAEDG,右子树的前序遍历序列为I,中序遍历序列为LHEG。
接下来可以递归地处理左右子树,得到左子树的后序遍历序列为DEGCBHA,右子树的后序遍历序列为LHEGIA。因此,整棵二叉树的后序遍历序列为DEGCBHALHEGIA。
设某二叉树的前序遍历序列为:ABCDEFGHI,中序遍历序列为:BCAEDGHFI,则二叉树的后序序列为
根据二叉树遍历的性质,可以得到以下信息:
- 前序遍历的第一个节点为根节点,即A为根节点。
- 中序遍历中,A将树分成了左右两个子树,左子树为BCAE,右子树为GHFI。
- 同样地,前序遍历中,A之后的三个节点BCD为左子树的前序遍历序列,EFGHI为右子树的前序遍历序列。
根据这些信息,可以递归地构建二叉树并求出后序遍历序列:
1. 对于左子树,前序遍历序列为BCD,中序遍历序列为BCAE,递归构建左子树并求出后序遍历序列CDABE。
2. 对于右子树,前序遍历序列为EFGHI,中序遍历序列为GHFI,递归构建右子树并求出后序遍历序列GIFHE。
3. 将左右子树的后序遍历序列拼接到根节点后面,得到后序遍历序列CDABEGIFHEA。
因此,该二叉树的后序遍历序列为CDABEGIFHEA。