算法创作 | 二叉树遍历问题解决方法
问题描述
二叉树的先序遍历、中序遍历、后序遍历怎么求?
解决方案
给你一个二叉树(如图)那么怎么找出它的先序遍历、中序遍历、后序遍历呢?
我们先看一个简单二叉树来了解它的概念。 所谓前序,中序,后序就是指根所在的位置。比如前序遍历可以理解成根在前,简记成根-左-右。中序遍历可以理解成根在中间,简记成左-根-右。同理后序遍历即左-右-根。 知道这个简单记忆方法后我们再来看一个稍微复杂的二叉树。 要想求解这个二叉树的前序遍历、中序遍历、后序遍历显然比刚才的简单二叉树更难,但是运用原理是一样的。 那么我们是怎么得到它的前序遍历呢?分为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)