00:00
下面我们来给大家介绍一下顺序存储二叉树的下一个内容,什么呢?线索化二叉树。呃,那还是用一个问题来引出我们这个线索化二叉树的,呃,一个必要性,大家先看一个问题,同学们看,现在呢,这里有有一个数列啊,你可以理解成就是一个数组,那么一共有这么六个数,这么六个数,如果我们把它构建成一个二叉树,是不是就变成这样一棵二叉树?大家有发现啊,我在把这个数列。构建成二叉树的时候,我是按顺序来进行构建的,比如说第一个节点是一,第二第一个呃,一这个节点的左边,左支节点就是三,右子节点就是六。对吧,按顺序来的,那么八呢,就放在。这个三的左子节点,十放在三的右指节点六,呃,十,14放在六的左子节点。
01:01
这个就是一棵什么树啊?大家发现没有?其实它是一个我们前面讲过的一种树,什么树。对,这就是我们前面讲过的完全二叉树,对不对,那么大家有没有发现这个树它有一个问题,它有什么问题,大家有没有发现就是这棵树呢?有很多指针我们没有充分的利用,你比如说吧,同学们看。我们这一个八是不是这个指针,我们空着没有用。这个指针是不是我们也没有用,这个月没有用,下面十十四也有两个。两个指针没有使用,包括六呢,这边有一个指针我们也没有使用,那这样子呢,就在一定程度上浪费了我们这个指针,于是我们就提出了一个问题,大家看问题是什么呢?当我们对上面二叉树进行中序遍历式,数列应该是八三四十幺六四,中序遍历式不是个顺序,我就不讲为什么了吧。中序遍列是不是先把。
02:05
先把这个右边的指数编辑完,再输出当前节点,再遍历左边的这个指数,所以说它的顺序是八,三、11,六、14,那么有发现六、八、十、14这几个节点的左右指针没有完全利用上,那么假如说我们希望充分利用各个节点的左右指针,让各个节点可以指向自己的前后节点,怎么办呢?这时就提出了一个新的解决方案,叫做线索化二叉树。那么我们继续来看线索化二叉树的基本概念。我们聊一聊。大家看我这里总结了四句话,大家有一个印象啊,当有N个节点的二叉链表,还有就是说对于N个节点的二差链表中,会含有N加一个空指针。与这个N加一是怎么算出来的,它的公式我写到这啊,这这方是我们的一个公式推导。
03:05
它的公式是这样推导出来的,就是二乘以N减去。一个N减一。得到N减12N加一,那么我们看是不是前面的,前面这棵二叉树是不是有七,如果按这个算算的话,他现在一共有几几个。几个呢?大家看它现在有六个,他现在有几个节点,是六个节点,那么N加一。就应该有七个。空的指针域是不是有七个,我们算一下。一个两个三个四个五个六个七个对吧,完全正确,所以说它这个公式没有问题。那么如果我们利用二叉链表的空子针距存放,注意听这句话有有有点不好理解,就是存放指向该节点的。
04:00
应该是把这个写个该就好了啊,就是指向该节点的某种便利秩序下的前驱和后继节点的指针,我们就称之为。这这种附加指针的这种操作就称之为线索。那有时候老师你这个说的有点不太明白。呃,我我这样说吧,比如说我我我举一个例子,打个比方。假如现在呢,我做这样一个工作,我把这个八的右右面这个指针指向它的前面这个三,为什么呢,按照中序来说啊,后面这个啊,应该是后面这个八,后面这个是不是三呢?假如说我。假如啊。把这个格式拿过来,假如现在呢,我想办法让八的右指针。指向它的下一个节点,就是按照中序便利的下一个节点是三吗?这种行为就是让他这个空域指向了这个指针,指向谁呢?指向这个三这个节点,这种操作呢,我们就叫做线索化,只是我这个呢只写了一个而已,后面呢每一个节点都要操作。
05:11
明白这意思吧,这个就叫现实化,也就说刚才我连线的这个行为,就是刚才老师写写的这个,这句话的理解就是当我们把一个节点的空指针域存放指向该节点,我这样写啊。把这个该加上吧,该节点这个理解起来就比较明确一点,对不对,指向该节点的在某种秩序下的前驱和后继节点的指针,这样就就是我我把这个我把这个控指针域存放什么呢?存存放的就是按照下,按照这个秩序下的它的前驱或者后继,至于具体怎么放,后面我们再说。明白,这个就叫线索化,线索化那么这种加上了线索二叉链表的线索链表呢?相应的二叉树就称之为线索二叉树,叫surrounded battery tree。
06:04
那么根据线索性质不一样呢?我们又把它分成三种,一种叫前序。线索二叉树、中续线属二叉树和后续线组二叉属三种。那么为什么分三种呢?因为这里提的是某种便利秩序。那如果说你是按照前序便利的方式来线索化我们这棵二叉树,那就是前序线索二叉树,如果你是按照中序便利的方式来线索化这棵二叉树,就叫中序线序线索二叉树,明白意思吧,因为你不同的便利方式就会对我们这个节点,哪个节点呢?就是你你的这个节点。哦,回到这儿就是会对你线索化的时候,到底这一个八。这个八的这个地方是指向三呢,还是指向一呢,还是指向别的节点呢?有影响是不是,所以说它这里提到的概念是不同的便利方式,就会得到不同的线索化二叉树明白。
07:07
那么还有个概念大家要清楚,一个节点的前一个节点,我们称之为前驱节点。你比如说我举这个例子,比如说按照这个来看啊,那么三的。前区节点就是八。就是按照中序边理来说,三的前驱节点就是八。那么我们再看下句话,一个节点的后一个节点呢,称为后继节点啊,不叫后驱啊,不要乱讲,有些啰说为什么不叫后驱呢?它不能叫后驱,就叫后继节点啊,打打个比方,我们还以这个三为例,那么呃,三的后继节点就是十。明白意思吧,那就说14呢,14就没有后继节点了,同样八呢,没有前驱节点,明白。就是这个意思,好,同学们,那关于我们线索化二叉树的一个概念,先给同学们聊到这里,大家看理不理解,一会儿呢,我们写一个实际的案例,帮助同学们来真实正呃,更加深入的掌握线索二叉树这个知识点。
08:08
好,这个线索二叉树的概念先给同学们聊到这里。
我来说两句