00:00
同学们,我们来看一下树的常用术语,同学们看,这里呢,就有一棵树。这里就有一个树,那树的常用术语有哪些呢?我们来了解一下,大家看到这个图,然后再看这边给大家进行术语的解释,首先看节点。节点,那么这个节点呢,可以看到就是一个一个一个小圆圈儿,就代表一个节点,其实就是一个对象。有,有些人喜欢把它叫做节点对象。明白意思吧,那。明白这个概概念,根节点是哪一个呢?大家看,所以这个根节点就是A,就是它上面呢,没有负节点呢。他就是最先前的这个节点。这就是根节点,那么什么叫负节点呢?举个例子吧,比如说。而A就是B和C的负节点,那反过来B又是D和E的负节点。明白这意思啊,什么叫子节点呢?我们也举个例子,比如说按这个B节点来说,B这个节点呢,就是A的子节点。
01:09
C呢?C也是A的子节点,当然C它既是子节点,同时它也是负节点,对不对?那F和G它们的,它们又是C的子节点。这个关系其实通过图一下就明白了,那么我们再来看什么叫做叶子节点,所谓叶子节点就是没有子节点的节点就叫叶子节点,你比如说大家看这边哪一哪几个是叶子节点呢?同学们看这里H。E。FG这些呢,就是没有子节点,所以说他们也是叶子节点。好,那节点的权是什么呢?节点的权就叫,你可以理解成就是节点的值。打个比方,比如说现在我们有个节点是存放的employee。就是雇员,雇员假设里面有个编号,假如里面有个编号,比如这个人的编号为20,好,我们就可以简单理解成这个就是它的一个权。
02:08
好,那么有些时候这个权呢,是用路径来表示的。路径来表示的,好,你可以简单理解成就是节点的值。那么路径是什么呢?大家看,路径就是指的从根节点,这个根节点也叫root节点。Root就是根的意思嘛,就是从root节点找到该节点的一个路线,你打个比方,我们说找这个D,这个D你怎么找的,你是不是从A到B,再从B到D,这个路径就是abd,这个路径就是我们我们所说的他的他的一个路径,就是他的一个路线怎么找到的,对不对?我们再来看这个城。我换一个颜色啊,同学们换一个颜色,那么层是什么意思呢?大家看我这里直接看图就行了,比如说A就是我们的最上面这一层就是一层,B和C是位于同一层,它们就是第二层,那么DEFG呢,就是第三层,而我们的H呢,就是第四层。
03:10
这就是层的概念,也就是说我们把处于同一个级别的,或者同一个层面的这些呢,归结为同一层。大家看到没有,那什么叫指数。什么叫指数,你比如说大家看到看到这个。这个虚线。这个呢,其实它严格来讲,这个虚线的三角形就是。就是D作为根的一个指数,就是它是谁的指数呢?它是我们这个A的指数,也可以说是B的指数,明白意思吧,就是它是一个指数,那什么叫做树的高度呢?树的高度就是指的最大层,你比如说针对我们这个图形,它的层数就是几层呢?就是四层,为什么?因为它最大的高度是不是?你看这个最大高度就最大的层,最大层不是四层吗。
04:00
就是高度,就是四明白什么是森林,森林就是多棵指树就构成的森林。多棵指树就构成森林,比如说我有好几个指数,那么整个指数我们就可以构成一棵森林,就这么来的,同学们理解啊,好,这是树的常用术语,了解一下,那么树的常用术语呢,有些书上他说的比较。比较抽象,所以说我这呢,直接以一个图的方式来讲,大家理解起来比较轻松,对于比较纠结的地方,我们也不要过于的去把这个,把这个概念天天在那研究对不对,我们重点还是能够写出数这种结构,然后呢用数来解决实际问题就行了。概念上呢,我们有一个了解就OK,知道负节点,子节点,叶子节点,非叶子节点,节点的全路径成指数是什么意思就可以了。好,紧接着我们再来看二叉数,那什么是二叉数呢?刚才我们介绍的是数二叉树又又是指的什么意思呢?大家看一下,数呢有很多种,比如说后面我们还会提到B数,必加数对不对,二叉树等等,那么说有这么多这么种,那么什么是二叉树?二叉树听这个名字还是很形象的,二就代表两个,也就是说它的每一个节点最多只能有两个子节点的这样一种形式的。
05:25
我们就称之为二叉树。二叉树呢,它的子节点要明确的分为左子节点和右子节点。就是左节点或者是右节点,你比如说看这一颗。11,它的左子节点就是21,它的右子节点就31,那么这个呢,就是一棵二叉树。我们再看一,它的左边是一个二,但是它右边没有,右边没有了,它仍然是一个二叉树,为什么呢?因为说最多有吗。是不是最多那只有一个也行啊。只有一个A型,那么我们再看这棵,这边呢,它只有右子节点,没有左直节点,它仍然是一棵二叉树。
06:04
对不对,它也满足这个条件,最多只能有两个直接点的,那我没有没有超过两个就行,好,这是我们所说的二叉数,那么我们再来看二叉树的第三个需要同学们注意的,如果该二叉树的所有叶子节点什么叫什么叫叶子,叶子节点是不是刚刚刚刚讲过。就是没有没有子节点的节点,我们就就称之为叶子节点,那么所有的叶子节点,叶子节点都在最后这一层。最后这层,那而且它节点的总数是二的N次方减一。二的N次方减一啊同学们,我这稍微提一下啊,你看有时候我写的是这个解。有些地方用的是这个节,这个呢,呃,没有什么严格的区分,很多书上也没有区分,所以说我们写这个节点和这个节点你可以认为是等价的就可以了。好了,那二的N次方减1N呢为我们的乘数,我们就称之为满二差数。
07:00
你比如说看这棵树。这个树,这个树就是一棵满二叉树,为什么呢?你们有没有发现它所有的非它所有的叶子节点都在最后这一层,而且它满足节点的总数是二的N次方减一,为什么呢?你看这是第一层,这第二层,这是第三层,我们算一下啊,那就是二的三次方。减去一个一等于几呢?等于七是不是七个节点1234567正确,而且它满足所有的叶子节点都在最后这层。是不是这样子的啊?同学们好,那这就是满二叉树,那么什么叫做?呃,还有一种数叫完全二叉树,那完全二次数要满足什么条件呢?如果该二叉树的所有叶子节点都在最后一层,或者是在倒数第二层。就最后一层或者是倒数第二层,而且最后一层的叶子节点在左边是连续的,在倒数第二层的子节点右边是连续的,我们就称之为完全二叉树。举个例子,看这个数,同学们有注意观察。
08:13
看诶,我换一个颜色啊,我换一个颜色,比如说。嗯,大家看,这是叶子节点。它在最后一层,这边是叶子,叶也是叶子,叶子节点,它在倒数第二层,而且它满足什么呢?最后一层的叶子节点在左边是连续的,你看这个地方是连续的,没有断。而倒数第二层的叶子节点呢?从右边开始是连续的。对不对,它往它你看从这开始走,这走从这开始走吗?是不是它是不是也是连续的呀,右边也是连续的,那这个就是完全二叉数,那同学们我举个例子,比如说我把61这个也删掉。请问它还是一个完全二杀术吗?
09:01
各位,这时它就不是一个完全二叉数了,因为它并不满足说你的倒数第二层的节点是右边连续的,它不连续。它不连续,好同学们,那关于这一个,呃,二叉树的这么一个。概念和它的术语我们就先聊到这儿,待会儿呢,我们重点要给大家讲解的是二叉树的前序便利、后续便利和中序便利。好,各位同学这一讲呢,先给大家说到这里。
我来说两句