• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

遍历二叉树的前序、中序和后序(个人笔记)


Recommended Posts

引文:https://zhuanlan.zhihu.com/p/73438175

二叉树的前中后顺序遍历

相关概念请参考:二叉树_百度百科。

二叉树:

fg23okhfira3316.jpg

预序遍历A-B-D-F-G-H-I-E-C

按中间顺序遍历F-D-H-G-I-B-E-A-C

按照倒序遍历F-H-I-G-D-E-B-C-A

前部(左右根部)、中部(左右根部)和后部(左右根部)

例题1:

已知二叉树的一阶遍历是A-B-D-F-G-H-I-E-C,中阶遍历是F-D-H-G-I-B-E-A-C,请恢复此二叉树。

思考解决问题:

从前面的顺序遍历,我们确定了根节点是A,从中间的顺序遍历,我们得到F-D-H-G-I-B-E在根节点的左边,C在根节点的右边,这样就可以建立我们二叉树的原型了。

4l4tuxv0tyx3317.png

那么剩下的前序遍历是B-D-F-G-H-I-E,中序遍历是F-D-H-G-I-B-E,B是我们新的“根节点”。从中序遍历得出F-D-H-G-I在B的左边,E在B的右边,继续建。

bqdgvxkickq3318.jpg

那么剩下的前序遍历是D-F-G-H-I,中序遍历是F-D-H-G-I,D就是我们新的“根节点”。从中序遍历得出F在D的左边,H-G-I在D的右边,继续建。

sxyaj3c05o13319.jpg

那么剩下的前序遍历是G-H-I,中序遍历是H-G-I,G就是我们新的“根节点”。从中序遍历得出H在G的左边,I在G的右边,继续建。

ogqkcyjhgif3320.jpg

例题2:

已知二叉树的中序遍历为F-D-H-G-I-B-E-A-C,逆序遍历为F-H-I-G-D-E-B-C-A,请还原此二叉树。

思考解决问题:

从逆序遍历中我们确定了根节点是a,从中序遍历中我们发现F-D-H-G-I-B-E在根节点的左侧,C在根节点的右侧,这样就可以建立我们二叉树的原型了。然后是新的根节点B,根的左边是FDHGI,右边是E。在那之后,是新的根D,左边是F根,右边是HGI根,然后就差不多了。

就像恢复前中顺序的二叉树一样,我们也可以恢复中后顺序的二叉树。

4ltmu3qvx4w3321.jpg

你不能用光学前序遍历和后序遍历来恢复二叉树。

编辑于2021-11-11 22336005

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now