已知二叉树的中序遍历是DBEAFC.前序遍历是ABDECF.后序遍历怎么算？

发布网友发布时间：2022-07-22 09:55

我来回答

共5个回答

热心网友时间：2023-11-09 10:12

1、首先声明一个静态二叉树节点类，通过该类对象，可以构建一棵二叉树结构。

2、然后实现算法，通过递归方式后序遍历一棵二叉树。

3、编写本地测试方法，测试递归方式后序遍历二叉树，输出符合预期，本地测试通过。

4、实现算法，通过迭代方式后序遍历一棵二叉树。

5、最后编写本地测试方法，测试迭代方式后序遍历二叉树，输出符合预期，本地测试通过。

热心网友时间：2023-11-09 10:12

先根据后根遍历和先根遍历画出二叉树，知道了二叉树，后根遍历也就出来了

热心网友时间：2023-11-09 10:13

先根据中序和前序画出二叉树结构就可以写出后序了

热心网友时间：2023-11-09 10:13

debfca

热心网友时间：2023-11-09 10:14

先理解前序和中序的涵义：
前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。

所以，前序遍历ABDECF中，A肯定是根节点（第一个遍历根节点）。对照中序遍历，就能知道
DBE是左子树，FC是又子树了。
然后分别研究左右子树：
1、左子树：中序DBE，前序是BDE；说明B是左子树的根节点，D是B的左孩子；E是右边的；
2、右子树类似：C是右子树的根节点，F是C的左孩子（因为在中序遍历中F时在C前面的，所以一定是左孩子；如果是右孩子的话中序遍历时就应该是在C后面了对吧）