已知一颗二叉树，如果先序遍历的节点顺序是：ADCEFGHB，

[问答题]

已知一颗二叉树，如果先序遍历的节点顺序是：ADCEFGHB，中序遍历是：CDFEGHAB，则后续遍历序列的结果为_________________

abserver

参考答案后序序列无误，所画的二叉树有误，对其进行中序遍历不能得到题中所给条件。

正确画法如下：

/ \

D B

/ \

C E

/ \

F G

发表于 2019-07-11 10:46:52 回复(1)

ajune

根据先序遍历结果，可以推出A为根节点，B为左子树的第一个节点，根据中序遍历结果推出以A为父节点的右子树只有一个节点B。再次向下推，先序中的C应为D的左子节点。接着看E和F，在先序和中序中E和F的先后顺序不同，所以可以推出F为E的左子节点，再看G和H，由于先序中序结果中顺序一样，则H为G的右子节点。个人总结，如果先序中序结果中挨着的两个节点顺序一样，那么后一个结点是前一个节点的右子节点。否则先序结果中后一个结点是前一个节点的左子节点。

发表于 2019-06-02 19:00:14 回复(0)