某二叉树的中序遍历序列为CBADE,后序遍历序列为CBADE,则前序遍历序列为...

发布网友发布时间：2024-03-04 04:52

共2个回答

热心网友时间：2024-03-07 10:10

某二叉树的中序遍历序列为CBADE，后序遍历序列为CBADE，则前序遍历序列为EDABC。

首先，后序遍历的意思是先访问父节点的左右两个子节点，最后访问父节点。因此后序遍历序列的最后一个元素就是二叉树的根节点，即E，于是CBAD为E的后代节点。现在继续查看中序遍历，中序遍历的意思是，先访问父节点的左孩子，再访问父节点，最后访问右孩子。因此在根节点E的左边的CBAD为它的左孩子，它没有右孩子。然后再次回到后序遍历序列，因为我们已经知道E为根节点了，所以只需要考虑CBAD。于是D为E的直属左孩子，即D为左子树的根节点。然后继续检查中序遍历，可以发现D没有右子树，只有左孩子CBA。依次类推，可以发现这个二叉树的所有节点都没有右孩子，从上到下分别为EDABC，因此其前序遍历为EDABC。

二叉树特点：

1、每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。

2、左子树和右子树是有顺序的，次序不能任意颠倒。

3、即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

热心网友时间：2024-03-07 10:07

这道题可以这样思考。首先，后序遍历的意思是先访问父节点的左右两个子节点，最后访问父节点。因此后序遍历序列的最后一个元素就是二叉树的根节点，即E，于是CBAD为E的后代节点。现在继续查看中序遍历，中序遍历的意思是，先访问父节点的左孩子，再访问父节点，最后访问右孩子。因此在根节点E的左边的CBAD为它的左孩子，它没有右孩子。然后再次回到后序遍历序列，因为我们已经知道E为根节点了，所以只需要考虑CBAD。于是D为E的直属左孩子，即D为左子树的根节点。然后继续检查中序遍历，可以发现D没有右子树，只有左孩子CBA。依次类推，可以发现这个二叉树的所有节点都没有右孩子，从上到下分别为EDABC，因此其前序遍历为EDABC。