设某二叉树的前序序列为ABC,中序序列为CBA,则后序序列为? 求过程

wzhappysnail · 2018-4-30 02:32:12

前序遍历过程是根左右
中序遍历过程是左根右

所以根据前序可以很快确定根，然后可以查看根在中序中位置，将中序分为左右两部分，左边和右边两颗树，在按照上述方式递推出确定左子树的根和右子树
如本题
根据前序，可以确定A为根，A在中序中的位置，可以确定CB为A的左子树上的结点，没有右子树。
确定A之后，再看中序第二值为B，查看B在中序中的位置，C在B左边，确定C为B的左子树。所以本题的具体二叉树如下：

聽聽聽聽聽A
聽聽聽聽/
聽聽 B
聽 /
C

所以后序是CBA

设某二叉树的前序序列为ABC,中序序列为CBA,则后序序列为? 求过程

1 个回复