00:00
各位,我们继续来看关于二叉树的前续便利,后续便利和呃,前续中续和后续,那首先呢,我们看一下这个需求,先对便利做一个说明,我们这个二叉树呢,它的便利方式有三种,前续,中续和后续,我先把这个前续中续,后续便利的概念给各位同学说一下,什么叫前续,什么叫中续,什么叫做后续来看一下。首先看这概念,所以情绪便利呢,指的是先输出负节点的这个内容,然后再便利左指数和右指数。那么中虚变利是什么意思呢?先便利着指数。然后再输出。负节点,然后再便利幼指数。后续变利呢,是先变利左指数,再变利右指数,最后输出负节点,那大家有没有发现它的特点,怎么去区分是前序、中序还是后续呢?主要是看你这一个负节点输出的秩序顺序是什么,如果负节点是先输出,那就是前去,如果负节点是最后输出,就是后续,那如果负节点是在中间输出,那就是中续。编离明白这意思了,好,现在呢,我一会儿会把前续、中续、后续。
01:24
这个给大家进行一个编码代码的编程,在代码编程之前,我要先做一个思路分析,就是怎么来写这个二叉树的编译,打开我们的Excel表。我们现在来分析一把。各位同学,那么一会儿呢,我们来,我们来分析一下,我们分析分析二叉树的。啊,钱钱旭。中旭。中旭。中旭啊中旭还有后续。后续的一个便利啊,便利的一个步骤,或者是他一个思路,好,首先呢,我们肯定第一步是不是我们要先建立一个二叉树啊。
02:11
这个肯定是要有的,所以说我把这个呢,先挪到这边来。好,首先我们要创建,创建一棵一棵二叉树。这是第一步,你没有二叉树,你怎么去编译呢?好,那么假设,假如现在我们有一棵二叉树,这个二叉树呢?假如我们这已经有了啊,我把这个图拿过来。好,这个图就放到这了。待会呢,我们可以看到,目前我们这棵二叉树有四个节点,四个节点呢,是呃,有这个人物的,我们还是用hero load来写好吧,He load,那hero load呢,它有编号和他的名字就可以了,比如说这个人的编号和他的名字,我们就作为一个节点信息,那你如果是前序便利,我们应该怎么做呢?
03:06
就说如果我们是前序便利追星前序便利的,它的步骤应该是这样子的,首先呢,你先输出输出这个。这个当前这个节点。是不是,当然这个你得判断是不是空了,就是这样子的啊,先输出输出当前节点。是不是,然后然后呃,然后如果如果它的左子节点,注意听啊,左子节点不为空。不为空,则则干什么呢?则。则向。向,然后干什么呢?继续情绪便利有递归。递归注意听啊,用递归的方式,用递归继续。继续前续便利。情绪便利对不对,这是第一步,第二步,第二步。
04:03
啊,这是应该这样子先输出。当前节点。第二步呢,就是判断它的左支节点是不是为空,如果不为空,如果左支点不为空,则递归继续前续变力,那这个做完了过后干什么呢?如果它的右子节点,右子节点。不为空,你还要继续判断不为空。干什么呢?则地归。递归继续继续便利啊,继续前序便利。前序便利就可以了,那么我要说说明一点,就是同学们看到的这一个所谓的这个当前节点,它出第一,第一个应该是根节点后面呢变化的对不对,这个节点呢。第一次就是刚开始的时候,初始的时候,初始的时候是是什么呢?根节点就是我们所说的root节点,因为你你肯定是从这个root节点开始往下走的嘛。
05:05
对不对,是从root节点开始往下走的,这点大家要清晰,然后呢,我们再来看,如果我们是中序便利。如果我们是中续便利的话,他的思路应该是什么样的呢?我把这个加个颜色。对,这样看起来比较清晰,如果是中序便利,我把这段代码拿过来稍微用一下啊,如果是中序便利,它是怎么做的呢?他这样子的。好,我们写这它先输出,先先判断,如果左支节点这样子的啊,如果左子节点不为空,再向递归干什么呢,他先往。它的柚子树去找。OK,如果当前节点的这样写啊,当前节点的左止节点不空,则递归。递归进行什么呢?递归。
06:01
这个中需便利。能理解啊,递归中区便利。那么编定完了过后呢,第二步就是输出当前这个节点。输出当前这个节点。好,呃,这句话我就不要了,就是就是输出当前节点,当前节点输完了过后呢,就再继续判断它的这个右子数是不是为空。你看没有好,这样继续判断,如果什么呢?如果当前节点的右子节点。右子节点不为空,则递归进行什么呢?中去便利。啊,递归进行中序遍历写错了。中学。便就完事,那如果是后续便利呢?好,我把这个也给大家拿过来,大家有没有发现它唯一变化的就是我们这个当前节点输出的一个时机好,第四一个我们讲的后续编利。
07:02
后续编历,那后续变利的话呢,它是干什么呢?如果当前节点的左止节点不空,则递归进行什么呢?进行这个后续编辑,这是第一步,这个做完了以后,他的下一步就应该是这样子的。我把这个复制一份。复制一份。注意啊,它总是要判断一下的,如果当前节点的右子节点。右子节点不空,则递归后续便利,然后第三一步就输出我们这个当前节点。好,现在这个就完事了,大家看大体的步骤就是第一步先创建二叉树。然后前序编辑的思路这样子的。中续遍历的思路这样子的,后续编利思路这样子的比较简单,对不对,那待会呢,我们就来用代码来走一遍,注意。在便利的时候,我们肯定事先是从根节点开始读的,不管你是前续、中续还是后续,你始终是中。
08:05
根节点开始往下走,才能把整棵二叉树遍历完毕,是这样子的吧?好,同学们,这个呢,就是我们讲的这个二叉排序数的一个便利步骤,我们先写到这。它的便利步骤的一个分析和它的一个图解,待会呢,我们就照着这个思路来编写代码。好,关于它的思路,我们先说到这里。
我来说两句