...中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历是什么...

发布网友发布时间：2024-10-03 14:59

共5个回答

热心网友时间：2024-10-27 21:16

已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历是DGEBHFCA。

前序遍历的第一个节点为根节点，由前序遍历可知，A为根节点。中序遍历的根节点前面的节点均为左子树的节点，所以左子树上的节点为DBGE。去掉根节点和左子树节点，右子数节点为CHF。前序遍历的第二个节点为B，由2知B为左子树节点，所以B为左子树的根节点。

由前序遍历，DEG在B节点下面，由中序遍历，D是B的左节点，GE是B的右节点。由前序遍历，E是G的根节点，由中序遍历，G是E的左子节点。由前序遍历，C是二叉树的右根节点，由中序遍历，C不含左子节点，HF为C的右子节点。由前序遍历，F为H的根节点，由中序遍历，H为F的左子节点。

在二叉树中，求后序遍历，先左后右再根，即首先遍历左子树，然后遍历右子树，最后访问根结点。则该二叉树的后序遍历是DGEBHFCA。

扩展资料：

后序遍历的非递归算法是三种顺序中最复杂的，原因在于，后序遍历是先访问左、右子树,再访问根节点，而在非递归算法中，利用栈回退到时，并不知道是从左子树回退到根节点，还是从右子树回退到根节点，如果从左子树回退到根节点，此时就应该去访问右子树。

而如果从右子树回退到根节点，此时就应该访问根节点。所以相比前序和后序，必须得在压栈时添加信息，以便在退栈时可以知道是从左子树返回，还是从右子树返回进而决定下一步的操作。

热心网友时间：2024-10-27 21:10

先序遍历的第一个结点是根结点，所以A是根，然后在中序遍历中找到A，（DBGE）A（CHF），由中序遍历的定义知（DBGE）是左子树的中序遍历，（CHF）是右子树的中序遍历。然后在先序遍历中把左子树和右子树划开，A（BDEG）（CHF），所以B是左子树根，C是右子树根。然后继续在中序遍历中找到B和C，（（D）B（GE））A（C（HF））。对于DBEG，B是根，D是左子树，EG是右子树的中序遍历，对于CHF，C是根，HF是右子树的中序遍历。因为仍然有没划分完的部分，所以继续看先序。对于BDEG，B是根已知，D是整个左子树已知，所以EG是右子树的先序遍历，E是右根，再对照中序可知G是E的左子树，CHF同理。

所以树的结构是A（B（D，E（G，）），C（，F（H，）））
把它画成图，后序遍历就是DGEBHFCA

虽然说起来很麻烦但是递归表达其实很简单的..

总之先序序列是用来确定根结点，中序序列是用来划分出左右子树。

热心网友时间：2024-10-27 21:15

我懂些数据结构,有这样的题.你要先了解前序、中序、后序遍历的基本性质，例如你的提问，前序中A在前、证明A是树的根，由此再看中序遍历A的位置，由此可知CHF在A的右端其余的在A的左端，依此类推。如果不会再发信息给我。祝你考试过关！

热心网友时间：2024-10-27 21:14

A
B C
D E F H
G
后序遍历就是DGEBHFCA

热心网友时间：2024-10-27 21:11

后序遍历顺序：DGEBHFCA

热心网友时间：2024-10-27 21:13