384_尚硅谷_Go核心编程_数据结构和算法-二叉树三种遍历方式.avi原创

好，下边呢，我们接着来讲一个二叉树，那二叉树呢，这里面我们重点就是给大家讲一下这个所谓的这个前序便利，还有这个中续便利和后续便利的一个概念啊，这个呢啊，我们做一个介绍。那么什么叫做二叉树呢？二叉树它是这样子一个概念，就是说。一个节点。一个节点，我们前面讲的一个节点呢，它只有一个指针指向下一个的，但它是指指向下一个节点，但是有些情况下，我们这一个节点呢，可能会有两个。指针，甚至有些地方是有三个都有可能。那如果说我们每一个节点，就是我们每一个节点都有一个左指针和一个右指针。对，有个左指针和右指针，那么它的下一个节点呢，又有一个左指针和右指针，那么这个呢，我们就把它称之为什么呀，把它称之为二叉树。

啊，把它称之为二叉树，呃，那么我们来看它的一个关系，比如说哎，这样子，这个就是第一层，这第二层，第三层，第四层，他们关系可以这样理解，最上面这个A呢，我们把它叫做根节点。如果说我们在变利的时候，要从这个根节点开始变利，对，要从根点变利，然后呢，呃，这个这个BB下面有两个节点啊，D和E，所以说我们会怎么说呢。就可以这样写，就说我们说D的这个负节点是B，对吧，它的上一个负节点是A。那么你看这儿还有一句话，诶这句话呢，大家可以理解，看这。他说的C是F和G的负节点，是A的子节点，就负子的关系呢，这个就很明显，那如果说看这句话啊，就说AEFG没有子节点呢，我们就称为夜节点，就说A，看这个AEFG如果没有子节点，就成为夜节点，假设是没有的啊，它是称为夜节点。

那么我们来根据这个呢，我们来构建，呃，一个简单的二叉树，我们来便利一下啊，便利一下就是主要是看这个二叉树的便利，那有时候呢，面试官他会问你什么叫前续便利，什么叫后续便利，什么叫这个中续便利，他会大概问一下这个他的这个含义是什么，那么我们来讲一个小案例大看啊。呃，使用现在呢，我们使用前续中续和后续便利，对下面二叉树进行一个便利，那么二现在二叉树长的是这样子的啊，有一个hero节点。它左边指向一个。英英雄它这个下面就没有没有此节点呢，我构建的比较简单，然后呢，它的右右节点呢，指向另外一个节点，这个节点下面呢，又它的右节点又还有一个零冲。然后呢，要求分别用前序。或中旭。

还有后续。对什么呢？对我们的这一个二叉数进行一个便利，他就是要求完成这么一个案例。那一般来说这种呢，它是比较简单的啊，就说就说它主要是考察点就是这个什么是前序，中序，后序，那么我简单说一下什么叫前序，前序指的是就说先。把这个根节点。的内容输出来，再去输出左边的指数，再去输右边的指数，这个呢我们称之为前序，中序就是指的先把这个根节点的左边全部遍利出来，再遍历根节点啊，再显示根节点，再显示根节点的右右边的这个指数，那么这个叫中续，那后续是什么呢？后续是先便利这边。啊，先便利它的这个这个指数，然后再便利它的右边这条这个右右边的这个数，然后呢，再遍利它的根节点，这个就叫后续变利，其实就这么一点概念，那么我们来写一下啊，我们先简单构建一下。

好，我们主要是把这个便利说一说，那现在呢，我们写一个案例。哦，几个案例。好，那么就叫binary binary tree。好，然后呢，我们写一个案例来走一下命。点够好的，来，朋友们package。May rather import。Import mind，好，然后呢，我们写一个呃，主函数。好，既然，既然我们要去构建一个英雄节点，所以说我先写个结构体。Type。He，然后呢，它是一个structure，呃，它有编号，编号呢我们用int。然后呢，它有一个名字啊，名字呢，我们用啊这个十寸来表示。好这诶这个没有没没有这个逗号啊，没有这个逗号。

然后呢，我们来构建它一下啊，构建一颗。啊，构建一个二叉树。二叉树。啊呃，简单构建一下，我们先把这个呃几个节点先创建起来，比如说hero，我们先借鉴这个根啊根节点，根节点呢，我这样写啊，对，这边还少了两个东西啊，左左左边的指向左边的这个指针，还有指向右边这个指针，先把它写出来left。Left，然后呢，Hero啊，指向左边的这个节点的指针，然后呢，还有一个right对指向右边的这个节点的指针，好一一左一右一左一右，好，现在呢，我们来构建这个。根节点，那怎么写呢？很简单，这样写啊，Hero，那么我给他一个no。啊，他是编号为一的，然后呢，他的名字叫宋江。

Name。好，给他一个值啊，叫宋江。好，这又建起来了啊，那么然后呢，我们再建右面的，再创建这个右边的这个无用啊，这就复制一份就行了。好，那么我写一个right右边的啊，左边的这个无用是左边的啊，LEFT1。那么这边我把名字改一下，吴用为编号为二，然后是吴用。好，先把大家写起来，然后呢，再把再把什么呢，我我这里面就没有书了啊，我就直接把它构建起来，然后呢，右边的这个节点也写出来，Right。一。右边这个呢，是编号为三的，对，叫卢俊义。好，我们也把它建起来，卢俊义三，然后呢，是卢俊义，卢俊义。好。

大家看一下啊，这是根节点，根节点在创建的时候呢，它左右里面节点默认为空，说它们之间没有形成这个二叉树，那现在呢，我把它指向一下这样子。Root。点。他的left。我们就让它指向。LIFE1。哎，这样子它就指向了左边这个节点，然后呢，同样道理，右边的。Rid，当然我们这一方写上一个什么呢？啊，RIGHT1啊，只有直接指向的啊，我这是直接指向的，没有写程序，当然紧接着我们还要建一棵这个树。这边还有一个林冲，林冲呢，我们也建起来，林冲也建起来，好，我再写一个右边的第二个节点。第二个节点啊，是叫林冲。好，我们看看到时便利能不能成功啊。林冲。哎，走。

林冲。呃，那么这个时候。右边这个节点它是谁的子节点呢？哎，它是卢俊义的右边这个子节点，所以说把它关系写清楚，那就是找到RIGHT1。点。Right right写一下啊，RI等于right。二好，其实到这一步呢，我们这个这个二叉数，一个就是按照他的这个要求的一个二叉数就已经啊，就已经写成了，就是按照这个要求的二叉树又写成了，那么我们主要是看一下便历啊，看一下怎么遍历，因为有时候他会问这个概念。那么怎么便利呢？来，我写一段代码。我写一个代码啊。首先，我先写一个前序遍历。情绪便利。前序变利指的意思，一定要清出。前序便利说先把这个根节点输出，再输出左指数，再输出右指数，把这个概念先搞清楚。所谓前绪便利是先输出。

先输出这个根节点。仙书。Root节点。然后再输出。再输出哪里呢？再输出它的右右呃左左指数。浊指术。指数。啊，然后再输出又指数。然后再输出。柚子树。哎，这个呢，这个概念有呃指数啊。指数。好，我们来看看这个怎么写，同学们，那现在呢，首先我写一个方法。Bank。好，那这个前序遍历，它这个有一个专业的这个词啊，叫P啊order。

Order，它里面就是便利的意思了。前面便利，那么你要给我一个什么呢？很简单，你给我一个根节点，你把这个根节点给我，我就可以搞定它怎么做。非常简单，他这样写的，如果你传进来的，哎，这个最好不要叫。呃，叫根据点也可以啊，是因为这样它会不停的往下走嘛。它会不停的往下走，所以说我们做一个判断，判断如果它只要不等于。这个就叫load吧，不要叫root，那叫root，容易容起一一一些误会，比如说这个节点，它只要不等于那样。它只要不等于零二，就是它只要不等于零二，我们就可以输出，那就怎么输呢？来，咱们把它输出来一下。就是format。P。好把它信息输出来啊，那我这样说吧，就是编号等于多少百分D。

就可以啊，然后行，待会大家可以看到它这个输出的情况。啊，名字也把它输出来吧，名字name等于百分之S，编号呢，就是这个node里面的no，名字就是node里面的name。好输完了，输完过后呢，紧接着咱们输出它的左指数，左指数怎么输出呢，非常的简单。你把这个P往这一写，再把这个node给他就可以了。再把这个note给他，同时再做一件事情。再往他的。右面去便利。右面去变利，注意它在进去的时候呢，它是一个递归的过程啊，递归的过程我们先来看这个效果是一个什么样子的情况，来看一下。我们输出一下看一下啊。来，现在呢，我用pre order。

来输出，我把这个根节点给他。就说我把这个，因为我我们来看看这个二叉树到底有没有成功嘛，那么如果输出的话，他顺序应该是什么样子，大家大家可以先想象一下，他应该这样输出啊，先输出宋江。再输出无用，无用再往下面走的时候呢，无用下面左指数没有了，所以他就。就就会回溯到上面，又把这个卢金义输出来，卢俊义他本身想往左边走，但是左边是空的，他又输出这个林冲。也就是说，如果你在下面有还有这个指数，它还是仍然遵循这个，呃，先打中间再再打两边的啊这个规则啊，因为我这这个数呢，比较少啊，如果多一点的话，可能看的效果更明显，那顺序就应该是这样子啊，宋江，吴用，卢俊义，林冲。好，我们看效果是不是这样子的。好，我们跑一下代码，我先退出CD，点点CD到刚才我们写的banner tree。

好的，各位同学go。Run man.go走。好，我们这边有个死的啊，哪里出错了，大家看一下。嗯，出错的原因是哪里呢？我们看看这个地方是数没有见对还是什么，就问题在这儿啊同学们。嗯，这个地方问题在哪里呢？是这我们这地方没有往这边取直接打的啊，就是你往左边打，那这应该取一个，呃，要一个left。对，Left这边呢，往右边走还要right一下，不然的话确实要死在这儿，好，我们再来输出一下。走。好，这个时候我们看效果。好，这次呢，就跟我们想象的是一样的，刚才原因大家要想啊，因为你没有去去访问它左边的或者右边指数呢，它肯定就死在这儿了，看他先打印出宋江，再打印出吴用，再打出卢俊义，再打印出林冲。

OK，那我问大家一个问题啊，有一个比如说做一个选择题，我出一个选择题，假如我们这个表是这样子的，我请同学们思考一下它会怎么输出。哎，比如说现在。假如我在这儿。又吃出去。两根。两个节点，各位两个节点，那那这两个节点呢，我假如这样写的啊各位朋友。OK，待会儿呢，我要来做一个测试。OK，那假如我这边呢，有一个节点叫十吧，这边有一个节点叫做假如啊，叫这个十一十二。那么如果我们这个二叉树它是这样子的，那么它输出的顺序应该是什么样子的呢？首先我们来看一下啊。

前序便利。先输出。宋江。然后往下走。左边的左边呢，这地方它输入什么呢。无无用他接着往十号走，他输出十输输出这个十过后，然后再输出是，然后再输出零进去，然后再这样子的啊，所以大家要要把这个选对，因为这有时候经常做这种选择题啊，那刚才那个顺序我们可以去简单的验证一下，简单验证我把我在无用下面再挂两个，再挂两个节点啊，再挂两个节点，我们做一个小测试，看看跟我们分析的是不是一样的。来，我快速的在无用下面挂两个节点。啊啊，我就简单的写一下啊，比如说这个NOTE10，我就简单写一个NOTE10和NOTE11。我这写了一个NO10和LOAD12，快速的走一下。就是验证一下我们这个顺序是不对的。

好，我复制一份。好，我复制一份，同学们。好，来一个no的十。NO10，然后呢，这边给他一个十号。对，这边名字呢，我们就就随便吧，叫汤姆。然后呢，再建一个NOTE12。再建一个ROAD12。NO12这边呢，也给他一个12号，然后这边呢叫Jackie。好，然后把这两个节点挂在无用的左右两边。它的左边。等于60。好，然后无用L一点它的右边。RI等于no 12完事了。好，我们看看这个跟我们刚才想象的这个结果是不是一样的啊，来运行一下。好，我们发现呢，跟我们想的是不一样的呢，我们看一下，呃，我们刚才分析的是这样一个顺序，看看对不对啊同学们。

OK，我们看看先先输出了，先输出了宋江这个是对的，然后往左边边力输出吴用，再往左边边力输出十，输出十过后呢，下面没有了，他就开始回速，它回溯到上面，诶回到回到这个位置，接着往无用的右边这条数打余数打出12，这也是正确的。然后这边相当于这边吴用宋江的左左边这个字数全部打完了，然后呢，又开始往他的右边打，他先打出了卢俊义，卢俊义的左边没有，所以就没法打了，然后呢，往卢俊义的右边打出林冲，这个顺序跟我们想的是一样的，好，这个呢，我们就叫做什么呀，前续便利，就前续变的概念就出来了啊，别人问到你前续便利是什么意思，你要清楚的告诉他，好，紧接着呢，我们再来看一下它的中续便利。

啊，中续变力，那么中续变力是什么意思呢？来看一下，中续变力是先输出着指数。他是这样子的，先输出。啊，先输出。先输出这个root的着指数。啊，然后再输出。啊啊，我们这也行啊，再输出这个，再再输出root节点。啊，再输出这个root节点，最后输出它的右指数。最后。最后输出这个root的右子数。好，那如果这样写的话呢，这个中序便利，它有个专业的名词叫infe。Infe，好，那么这个时候咱们怎么走啊？还是这样判断，它唯一的变化就在这一点。把它放在了。中间然后呢，这边也要做一个变化。

好，这个就可以了，那么我们先看看啊，如果我用中序遍历它这个结果应该是什么样子的，我们先来做一个啊，做一个这个测试。来我们看看，我们先不打啊，我们先不打，我们我们自己先来推一下，看看它这个结果应该是什么。哎，同学们看一下它应该是什么，同样把这个根节点传进去，我们来分析一下。如果是我们的中序便利。啊，他应该怎么走呢？他先把这边输出来，所以说这个宋江先不会打。他先。到这边来这个呢，对不对，也不对，因为怎么还没到底头呢。挨到底的，于是他会打这边，所以他会打出这个十。十打出来过后打出这个无用。再往这边跑。哎，打出什么呢，12。

然后再打出一，好，先把这个顺序定下十二十二一，十二十二一，我们先来运行一下，到这边呢，也是一样的道理啊，我们来跑一下。走。日日。好，我们看一下这个结果好像跟我们有点小区别是吧，看他打出是十。二。十二一好像给我们分析的是对的吧。一样的啊，一样的，我我说的是十二十二一正确，那下面这个一样的，这个就叫中续变利啊，这个中续变利它总是先把这个数，它相当于一直往下跑，跑到这个这边这个右子数的最右边，把它打出来啊，然后再这样子做，这个呢就要中续便利，还有一个呢，就是后续变历，后续便利呢，它一样的概念就是最后打出这个我就不说了啊，概念是一样的，我就把这个写一下就可以了，Post。

The post order。Post order，那post order呢，也是做一个判断，然后把这个地方往后面再挪一下。好，然后post order。Post order好也是这样做的，那这个顺序呢，我们可以来推一下，它是应该怎么打的啊，后续面积是先打左边。再打右边，最后打中间，就最后打这个中间，那么我们来看它顺序应该是怎么样子的，我们推推。好，如果是用的后续遍历，我们认为它的顺序应该是这样子的。先打，先把左边的全部打完。啊，大家看这个顺序应该怎么打啊。往下走，左边还没有结束，往下走，哎，东西到左边，左边没有了。左边没有了，于是把这个十打出来，然后呢，回头再打这边的右边12。OK，然后这边也打完了，过后再打这个，最后这个这个节点二。

好，这边就相当于全部打完了，全部打完再打出这个一。好，一打完了过后呢，往下走，卢俊义，卢俊义下面有，所以说不能不能打卢俊义往左边走，左边没有往右边走，打出四。打出四过后再打，最后打这个中间这个三，所以说它这个顺序是十。12。二然后呢是这个四，最后是这个三啊。好，我们看看这个顺序对不对啊，这个顺序对不对，我们。好，我们把它跑一下。好，然后呢，我把它调一下啊，Post order。把它调用一下走。然后呢，我们这边。把这个root节点输进去。这个我们用的是后续遍历，对后续遍历来玩一把。看代码啊走。

哦哦，我刚才这个是有问题啊，我刚才这分析是有问题，我们大家看一下。是我们再再确认一下这个顺序啊。啊，首先把这个顺序再再重新走一下。好，呃，宋江这个地方因为是最后打的对，他因为是最后才是，他因为是先把左边全部打完，再打右边这个，所以说他这个下面走实施先打的对，没问题，这第一。第一个这个打完过后打的是12，这个分析的也是正确的，然后这个做完了过后呢，再打谁打这个。无用，好，这个是三三打完了过后，这个宋江还不能打。宋江不能打，因为他要把宋江左边的这个也全部做完才能做，所以他往下面走，卢俊义，卢俊义还不能打，因为他左边有，所以他这个时候应该打出林冲。这个应该是第四个，这个打完了后呢，相当于卢俊义的左右指数全部都打完了，所以说这个呢是第五个，第五个打完了过后呢，相当于这个宋江的左右主数全部打完了，最后才打出这个宋江，这个是第六个。

好，确确实是这样子的啊，这个就是我们所说的前续中续后续便利啊，那么这个呢，呃，就是在面试的时候，如果面试官问到这个前序后续中心便利，他这个呃，他是一个什么样的一个顺序，大家能够把这个题给他答上来，就是有可能是一个面试题或者是一个选择题啊，大家看一下好了，那现在这个呢，我们就说到这里啊，说到这里。好，我们截取一段。