Question

设一棵二叉树的中序遍历序列为BDCA，后序遍历序列为DBAC，则这棵二叉树的前序序列

Answer 1

这个先根据后序遍历确定根节点为C。再根据中序遍历得到根节点的右孩子为A。然后根据后序遍历确定，B是根节点的左孩子，D是B的孩子。再根据中序遍历，得到D是B的右孩子。根据这个画出二叉树。

前序遍历结果是：CBDA。

扩展资料：

1、前序遍历的规则：访问根节点、前序遍历左子树、前序遍历右子树。

这里需要注意：在完成第2,3步的时候，也是要按照前序遍历二叉树的规则完成。

前序遍历的输出结果：ABDECF。

2、中序遍历：中序遍历可以记为左根右，也就是说在二叉树的遍历过程中，首先要遍历二叉树的左子树，接着遍历根节点，最后遍历右子树。同样，在二叉树为空的时候，结束返回。

中序遍历的规则：中序遍历左子树、访问根节点、中序遍历右子树

注意：在完成第1，3步的时候，要按照中序遍历的规则来完成。

中序遍历的输出结果：DBEAFC

3、后序遍历：后序遍历可以记为左右根，也就是说在二叉树的遍历过程中，首先按照后序遍历的规则遍历左子树，接着按照后序遍历的规则遍历右子树，最后访问根节点。在二叉树为空的时候，结束返回。

后序遍历二叉树的规则：后序遍历左子树、后序遍历右子树、访问根节点

注意：在完成1,2步的时候，依然要按照后序遍历的规则来完成。

后序遍历的输出顺序：DEBFCA。

Answer 2

后序序列最后一个为根节点，所以C为根节点，由中序遍历和后序遍历可以达到，二叉树如下：

由二叉树可以得出前序遍历为CBDA

Answer 3

从后续可以看出，根节点是C，再从中序上看，BD是根的左子树部分，A是C的右子数部分，从而很快地看出，CBDA为前序序列