您的位置:首页 >综合知识 >

计算机二级二叉树前序中序后序(二叉树前序中序后序)

导读 大家好,我是小曜,我来为大家解答以上问题。计算机二级二叉树前序中序后序,二叉树前序中序后序很多人还不知道,现在让我们一起来看看吧!...

大家好,我是小曜,我来为大家解答以上问题。计算机二级二叉树前序中序后序,二叉树前序中序后序很多人还不知道,现在让我们一起来看看吧!

1、对于例题的后序遍历的答案是,gdbehfca.

2、解答过程:

3、1)定义解释:树的遍历的三种情况,是根据左子树、右子树、根这3者的不同访问次序来定义的。根左右(根先访问),则为先序遍历;左根右,则为中序遍历;左右根,则为后序遍历。

4、2)已知先序和中序遍历结果,求树的结构和后序遍历结果:

5、先序遍历结果给我们带来的信息是,根在哪。

6、中序遍历结果给我们带来的信息是,左、右子树在哪。

7、所以树结构的还原过程是,根据先序找到一个根;然后根据这个根和中序遍历结果找到它的相应的左、右子树;依次往下。

8、对于例题而言:

9、先序遍历的第一个节点是a,则说明a是整棵树的根。然后在中序遍历结果中,由a断开,找到a的左子树和右子树,即dgb是a的左子树中的节点集合,echf是a的右子树集合。(dgb)a(echf)

10、然后开始递归求解:还原(dgb)和(echf)

11、(dgb)的先序遍历结果是:bdg(从题目中的先序遍历中,截取)

12、(dgb)的中序遍历结果是:dgb(从题目中的中序遍历中,截取)

13、所以b为根,(dg)为左子树,右子树为空。即(dgb)= (dg)b

14、同理:(echf)=(e)c(hf)

15、第3次递归:(dg)= d(g);(hf)= (h)f

16、最后得到的结果就是:

17、((d(g))b)a ((e)c((h)f))

18、(在这种表示中,括号的层数代表在树中的层数)

19、 a

20、 b c

21、 d e f

22、 g h

23、根据这个树,后序遍历为先左、右,最后根

24、先访问(dgb) (echf) 然后是a

25、(dgb)这棵树的后序遍历为gdb

26、(echf)这棵树的后序遍历为ehfc

27、所以最后结果为gdb ehfc a

本文到此讲解完毕了,希望对大家有帮助。

免责声明:本文由用户上传,如有侵权请联系删除!