已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历为
已知一棵二叉树前序遍和中序遍历分别为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。
扩展资料:
先序遍历2113的第一个结点是根结点,所以5261A是根,然后在中序遍历中4102找到A,(DBGE)A(CHF),由中序遍1653历的定义知(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
从中序遍历中,可将整棵树按根节点分为左子树,包括DBGE四个节点;右子树包括CHF三个节点
再从前序遍历的顺序分析出,B为A左孩子节点,C为A右孩子节点,再逐一节点分析,即可得该树:
A
╱ ╲
B C
╱ ╲ ╲
D E F
╱ ╱
G H