计算机二级二叉树前序中序后序(二叉树前序中序后序)
大家好,我是小曜,我来为大家解答以上问题。计算机二级二叉树前序中序后序,二叉树前序中序后序很多人还不知道,现在让我们一起来看看吧!
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
本文到此讲解完毕了,希望对大家有帮助。