首页 > 代码库 > 那些妖术——树的遍历

那些妖术——树的遍历

这个方法有点邪门,和大家在课堂上学的有点不一样,所以blog的名字取得有点邪乎。

一般的程序员应聘技术类的笔试都会有一道题目,那就是树的遍历(前序遍历,中序遍历和后续遍历)。这里教大家玩点新鲜的,

可能和平时大家学的有点不一样。但是绝对是在考场上解决问题的神器,因为一个字快,可以帮你节省时间做其他的题目。

喜欢的小伙伴记得点赞啊。(*^__^*) 

                                                     

一.中序遍历
这个是最简单的,什么是中序遍历,那就是把我们的树压扁了就可以得到我们的中序遍历,所以中序遍历就是DBGEHACIJF。
什么是把树压扁了呢?把每一个节点想象成一个滑轮,然后把它以中间的节点为中心压扁这个树,可以把整个树折叠成一条

直线,就想象成把这个树压扁了。

                                                    

                                                             

以此类推,继续把整个树都压扁。

                                                           


再把左子树以B为中心压扁得到序列DBGEH。在这里我们可以把E这个树看做是一个整体E’,压扁之后是DBE’,其中E’是等于GEH的压的时候

保证每一个节点的左右子树是位置不变的,就是左边的永远在左边,不能出现左边的压在了右边的里面这种类似的情况。这个时候就可以发现

我们压缩右子树的时候I在J的右边所以压缩为IJ,之后在继续压缩为IJF这个时候以C为“根节点”的树在压缩就是CIJF。最后压缩得到的子树就是

中序遍历DBGEHACIJF

                                                                                           

                                                                                                

                                                                                   

二.前序遍历

                                                                     

前序遍历这里就要很清楚一个前后顺序,在这里认为左子树永远在右子树的前面。除了叶子节点的每一个节点都要遵循这个顺序。

红线左边的节点都在红线右边的前面。前序遍历在这里我取了一个名字就叫做水流法。水流是从上到下冲刷我们的树的,在前面

的节点会先受到水流的冲刷.

                                                                    


如图所示水流是从左边来的,先受到冲击的就是ABD,用于水流是先冲击A的(水是自上而下的流动的)所以A先受到冲击,

接着就是B之后就是D。随着水流的冲刷ABD节点就会冲垮,我们便把他们擦除。在前面的节点先受到冲刷,后面的节点后

受到冲刷,这个时候然后一一消失。

                                                                       

需要记住的一点就是左子树一定是在右子树的前面。所以之后不见的是EG(他们的根节点是A)之后依次消除H,CFIJ。

注意水是从上往下冲刷的。之后依次类推。

                                                                           

                                                                          

                                                                            

                                                                             

                                                                                

三.后序遍历

                                                                               

后续遍历用的也是水流法对树进行遍历,这个时候水流是从后面来的,也就是树的右边。由于水流的特性我们也认为

最上面的和最前面的最先受到伤害,最先被腐蚀,直到消失。

                                                                                  

所以最先消失的就是ACF。


                                                                                 


                                                                                    

                                                                                    

在这里由于右边的树在前面所以先消失的是G,D在最左边所以最后消失。这个时候树的节点消失的顺序就是ACFIJBEHGD,由于是后续遍历所以我们要倒过来写:DGHEBJIFCA


至此,我们已经完成了所有的前序遍历中序遍历和后续遍历。