二叉树的遍历 |
您所在的位置:网站首页 › 什么是二叉树的遍历 › 二叉树的遍历 |
接上回树结构 二叉树是一个程序,总不能是我们人为的去说吧,所以我们要用专门的程序来对二叉树进行遍历,并用程序来表达,让我们每一个元素去用电脑来运用,这就是我们今天要说的主题——二叉树的遍历![]() ![]() 这里呢我们举了3个结点的遍历方法,分别为先序,中序和后序 通过这些遍历方法我们可以把拥有3个结点的数遍历出来,至于比较大的树,我们可以把他拆成很多3个结点的小树,再用上面的方法遍历出来。 ![]() 这里呢我们先学习先序遍历 我们以一颗九个结点的二叉树来进行讲解 ![]() 先遍历根节点,再遍历左子树。即:1是根节点先遍历1,1的左子树是2,4,5,7,而4又是2的左子树,所以遍历4,最后再遍历4的左子树,7,则这部分答案为1,2,4,7 ![]() 遍历完左子树就到右子树了,而4没有右子树,所以直接来到2,2的右子树是5,遍历5 则这部分结果为5 ![]() 遍历完1的左子树以后就应该到右子树了,即3,6,8,9,而3,6,8,9里面3是这课树的根节点,所以遍历3,3没有左子树,所以遍历右子树即6,而6的左子树是8,所以遍历8 则这部分答案为3,6,8 ![]() 最后遍历右子树,9 最后呢我们的答案是124753689. 正如上面的知识点所说,先序遍历有3个原则: 1.先访问根结点; 2.先序遍历左子树; 3.先序遍历右子树。 其实遍历就可以总结为3个字“根,左,右”(根节点,左子树,右子树) 通过上面的讲解也可以很清晰的看出来了 巩固一下,我们再来做一道题 用先序遍历以下的树。 ![]() 做做试试 答案是:1,2,4,5,8,9,3,6,7,10 你做对了吗? ![]() 学完了先序,我们再来看中序 图都一样,我们挨个看看 中序的遍历方法就有点逆向了,大家看看 ![]() 图一:我们先遍历左子树(最左最下的(注意是先最左在最下)),是7,而7又是4的左子树,左子树遍历完了,就应该遍历根节点了,所以下一个为4,。根节点以后就应该是右子树,但是我们发现这里的4没有右子树,所以我们直接跳过。来看到4,4又是2的左子树所以我们下一个应该遍历的是根节点即2.所以第一部分的结果为7,4,2 ![]() 图二:接上面,左子树,根节点都遍历完了,就应该到右子树了,右子树只有5,所以我们直接输出5就行,所以接着就是7,4,2,5 ![]() 图3:一样的,我们发现1的左子树遍历完了,接下来就是根节点,1所以目前是7,4,2,5,1 ![]() 图4:接下来就应该遍历有右子树了,而这里右子树的根节点3没有左子树,那么久遍历根节点即3,所以接下来就是7,4,2,5,1,3 ![]() 图5:3遍历完左子树和根节点就到了右子树,即6,而6作为8,9的根节点那就应该先遍历左子树即8,接下来就是根节点6,左后是左孩子9,所以最后结果是7,4,2,5,1,3,8,6,9 我们也是遵守了以下的3个规律: 1.中序遍历左子树; 2.访问根结点; 3.中序遍历右子树。 总结起来就是“左,根,右”(左子树,根节点,右子树) 这个中序是很难的,经常会考,大家需要牢记。 我们在做1道题巩固一下吧: ![]() 还是之前那副图。大家做一下 答案是:4,2,8,5,9,1,6,3,10,7 怎么样,做对了么?没做对那就再看一遍吧(这道题挺难的) ![]() 看图 ![]() ![]() 根据后序遍历的规则,我们先遍历左子树再遍历右子树,而这课大树的根节点为1,而1的左子树是2,而2的左子树又是4,以此类推,则最后一个左孩子是7,而隶属于7这个小树没有右子树所以直接遍历根节点,4,最后2这个根节点的左子树遍历完了就应该到右子树,则遍历出5,最后遍历根节点2.所以这个部分的答案是,7,4,5,2 ![]() 遍历完左边就应该到右边了即3,6,8,9,像之前一样,先遍历左子树,而3没有左子树所以直接遍历右子树6,而6的左子树是8,遍历8,接下来就是右子树9,遍历9,遍历根节点6,最后遍历1的右子树这个树的根节点,3,则这部分的结果是,8,9,6,3 ![]() 最后遍历根节点1.。所以答案如下 ![]() 7,4,5,2,8,9,6,3,1. 所以 后(根)序遍历规则如下: 1.后序遍历左子树; 2.后序遍历右子树; 3,。访问根结点。 做题。 ![]() 思考 答案是:4,2,8,5,9,1,6,3,10,7 ![]() 现在我们已经学会了树的3种基本遍历方法 接着努力吧 下一节课我们来说关于树建立的代码灰常重要,记得来看 点个赞吧,谢谢你们! |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |