某二叉树的中序、先序遍历序列分别为20,30,10,50,40、10,20,30,40,50,则该二叉树的后序遍历序列为

请先 登录 后评论

1 个回答

亚里士德
擅长:互联网

知识点:数据结构-二叉树的遍历

位于章节3.3.3。

只要是计算机相关专业的同学,应该就没有没学过的。

读懂题:

说一下简单理解,一棵最小树中,先序就是先排根,顺序是(根、左孩子、右孩子)。中序就是根排在中间,顺序是(左孩子、根、右孩子)。后续就是根排在最后面,顺序是(左孩子、右孩子、根)。所以左孩子一定排在右孩子前面,前中后序都只是在说根卡在它们之间的哪里而已。

所以有结论:整棵树的先序中,根一定在排在最前面。整棵树的中序中,根在中间,根的两边的数值就是依次整棵树的两边的数值。

解题:

解题过程是先构建二叉树,然后后续遍历。

构建二叉树步骤是根据先序遍历确定中根,根据中根在中序中的位置确定两边,然后两边分别再重复前面两个步骤,最终构建出二叉树。本题构建出的二叉树是10左边20,20右边30,10右边40,40左边50。所以后续遍历结果是:30,20,50,40,10

------

这题还有一个坑,就是把中序遍历写在前序遍历前面,不注意看题就会搞错。

------

过程:按时间顺序:

先序中10在第一个,说明10是根。

中序中10左边是20、30,右边是50、40,说明这棵树中就是这样的,先看左边子树两个数字的顺序。

先序中20在前,所以20要么在最左边,要么在中间且左边为空,30在后,所以30一定在20的右边(也就是1、左边是20且30在中间,或者2、20在中间且30在右边)。

中序中20在前,30在后,又因为只有这两个元素,所以20一定在中间,30在它右边。

左边子树完毕。

右边子树同理。



请先 登录 后评论