vlambda博客
学习文章列表

算法创作 | 二叉树遍历问题解决方法

问题描述

二叉树的先序遍历、中序遍历、后序遍历怎么求?


解决方案

给你一个二叉树(如图)那么怎么找出它的先序遍历、中序遍历、后序遍历呢?

 

我们先看一个简单二叉树来了解它的概念。

所谓前序,中序,后序就是指根所在的位置。比如前序遍历可以理解成根在前,简记成根--右。中序遍历可以理解成根在中间,简记成左--右。同理后序遍历即左--根。

知道这个简单记忆方法后我们再来看一个稍微复杂的二叉树。

要想求解这个二叉树的前序遍历、中序遍历、后序遍历显然比刚才的简单二叉树更难,但是运用原理是一样的。

那么我们是怎么得到它的前序遍历呢?分为5个步骤:

1)根据口诀,前序就是根在前,即根左右(2)再从上往下把这个二叉树拆解成“ABC”“BEF “CGH”三棵简单的二叉树(3)确定大范围,从上往下是(根左右):AB______C_______4)再锁定到拆解成的另外两棵树BEF “CGH”,注意这两棵树的顺序是先左后右,所以先看“BEF”。可以确定在这棵简单二叉树里它的前序就是BEF。根据先左后右,再看树“CGH”,可以确定在这棵简单二叉树里它的前序就是CGH(5)现在我们已经确定每棵树的前序,那么就可以直接回填了,即AB_EF_____C_GH______

同理,我们怎么得到它的中序遍历呢?同样分成5个步骤:

1)根据口诀,中序就是根在中间,即左根右(3)确定大范围,从上往下是(左根右):___B___A___C___(4) 再锁定到拆解成的另外两棵树BEF “CGH”,注意这两棵树的顺序是先左后右,所以先看“BEF”。可以确定在这棵简单二叉树里它的中序就是EBF。根据先左后右,再看树“CGH”,可以确定在这棵简单二叉树里它的中序就是GCH(5)现在我们已经确定每棵树的前序,那么就可以直接回填了,即

__E_B_F__A_G__C__H_

那么最后我们怎么得到它的后序遍历呢?同样用5个步骤来看:

1)根据口诀,后序就是根在最后,即左右根(2再从上往下把这个二叉树拆解成“ABC”“BEF “CGH”三棵简单的二叉树(3)确定大范围,从上往下是(左右根):

____B____CA(4) 再锁定到拆解成的另外两棵树BEF “CGH”,注意这两棵树的顺序是先左后右,所以先看“BEF”。可以确定在这棵简单二叉树里它的后序就是EFB。根据先左后右,再看树“CGH”,可以确定在这棵简单二叉树里它的后序就是GHC(5)现在我们已经确定每棵树的前序,那么就可以直接回填了,即_EF___B_GH___CA

到这里,它的前序遍历、中序遍历、后序遍历就全部求解完成了。

结语

本文章讲了怎么找一棵二叉树的遍历结构,画了两棵比较简单的树,讲述了其原理,其实还有更多复杂的树在等着我们去探索和发现,但是授人以鱼不如授人以渔,只要掌握其原理和方法,加上足够的耐心和细心,再复杂的二叉树都会被我们肢解成一些些简单的“小树枝”然后去破解它!




实习编辑:李欣容 

稿件来源:深度学习与文旅应用实验室(DLETA)