已知某二叉树的后序遍历序列是DACBE,中序遍历序列是DEBAC,则它的的前序遍历序列是什么?

如题所述

已知某二叉树的后序遍历序列是DACBE,中序遍历序列是DEBAC,则它的的前序遍历序列是edbac。

后序遍历顺序是“左子树―右子树―树根节点”:中序遍历是“左子树-树根节点-右子树”,前序遍历是“树根节点―左子树―右子树”。

二叉树的遍历(traversing binary tree)是指从根结点出发,按照某种次序依次访问二叉树中所有的结点,使得每个结点被访问依次且仅被访问一次。四种遍历方式分别为:先序遍历、中序遍历、后序遍历、层序遍历。

扩展资料

二叉树具有以下几个性质:

1、二叉树中,第 i 层最多有 2i-1 个结点。

2、如果二叉树的深度为 K,那么此二叉树最多有 2K-1 个结点。

3、二叉树中,终端结点数(叶子结点数)为 n0,度为 2 的结点数为 n2,则 n0=n2+1。

满二叉树除了满足普通二叉树的性质,还具有以下性质:

1、满二叉树中第 i 层的节点数为 2n-1 个。

2、深度为 k 的满二叉树必有 2k-1 个节点 ,叶子数为 2k-1。

3、满二叉树中不存在度为 1 的节点,每一个分支点中都两棵深度相同的子树,且叶子节点都在最底层。

4、具有 n 个节点的满二叉树的深度为 log2(n+1)。

温馨提示:答案为网友推荐,仅供参考
第1个回答  2020-07-23

由于后序遍历序列中排在最后的是E,说明E是根结点,又由于中序遍历序列中D排在E之前,说明D为根结点E的左子树,其余的结点B、A、C在根结点E的右子树上,结构如下图所示:

后序遍历序列中B排在E之前,说明B就是根结点E的右子树的根,即B是E的右孩子,再结合中序遍历序列,可以发现B没有左孩子,那么结点A、C均在结点B的右子树上,结构如下图所示:

后序遍历序列中A排在C之前,说明A是C的孩子,而中序遍历序列中A也排在C之前,可以进一步确定A是C的左孩子,这样的话,该二叉树完整的结构图应为:

 所以,该二叉树的正确前序遍历序列应为 EDBCA.

相似回答