若某棵二叉树的先根遍历序列为ABCDEF,中根遍历序列为CBDAEF,则这棵二叉树的后根遍历序列为
时间: 2024-02-24 18:54:53 浏览: 112
二叉树的遍历,前序遍历 中序遍历 后序遍历
根据先根遍历序列和中根遍历序列可以重建出原二叉树,然后对这棵二叉树进行后根遍历即可得到后根遍历序列。
先根遍历序列为 ABCDEF,中根遍历序列为 CBDAEF。根据先根遍历序列的第一个元素 A,可以确定根节点为 A。在中根遍历序列中,A 的左边为左子树的节点 CB,右边为右子树的节点 DEF。因此,A 的左子树为以先根遍历序列中 BCD 为先根遍历序列,CB 为中根遍历序列的二叉树,右子树为以先根遍历序列中 EFG 为先根遍历序列,EF 为中根遍历序列的二叉树。
继续递归构建左右子树,得到下图所示的二叉树:
```
A
/ \
B D
/ \
C E
/ \
F G
```
对上述二叉树进行后根遍历,可得后根遍历序列为:C B F G E D A。
因此,该二叉树的后根遍历序列为 CBFGEDA。
阅读全文