大家好。
数据结构与算法这一讲开始第六章数的学习。
我们首先定下树的一些基本术语,特别介绍一下
森林跟二叉数之间的转换。 那树呢,它是这么一个结点的有限集合,
那其中呢有一个特定的结点称为根。
那么在根底下呢,其它的结点被划分为
若干个不相交的有限集合,而每一个集合呢,
又都是这个树的子树。 那这就是一个递归的定义。在数据结构与算法里面,
我们定义的树一般都是有向有序的,也就是说,
子树的相对顺序是非常重要的。那可以说呢,
我们这个度为2的有序数,它并不是二叉数。
因为我们在度为2的有序数里面呢, 第一棵子树它被删掉以后呢,
它的第二个结点呢,它自然就成为第一。
那在二叉数里面,我们删掉了左结点以后,
那右结点它还是右结点,它一定在右边,所以不能够
去替代左结点。那我们来看一下数的逻辑结构。
数它是n个结点的有穷集合。
那这个集合之上呢,我们还有一个关系。
那这个关系里面呢,它有这么一个特点就是,
有一个结点是根结点,它没有任何的前驱,
那除了这个根结点以外呢,其它的结点都是只有一个唯一的前驱。
那我们表达这个结点集合是这样的,那在这上头的
关系集合,实际上是我们用有序对来表达,这个
尖括号呢就表示它是有方向的。那在我们的
数据结构里面,这个树我们一般都是看着从根往叶的方向。
因此,因为它这个方向呢是都从根往叶,
我们就不去画那个箭头了。
树有一些相关的术语,首先是结点。那结点里面呢,子节点,父节点
跟二叉数里面是类似的。那也就是说,如果两个结点它们是有序对,
那其中靠近根的那个呢就是父,然后靠近叶的方向呢就是
子结点。还有呢,我们有兄弟结点里面的前兄弟和后兄弟这样的概念。
所谓前兄弟后兄弟呢,也就是说在这个
树里面它们的排行,第一第二第三,那紧邻着的那就是互相是 前后兄弟的关系。
还有分支和叶。那如果是说 没有任何的子结点了,那就是叶;
那如果说它有结点,那就是分支。
树的根也是一个独特的一个分支结点。
关于边的一些定义呢,我们
首先就是边呢,它其实就是这个有序对,那
如果是从根往这个树叶的方向,
这里面有那么一个结点的序列, 那我们就称为这是一个路径,
那这个结点序列里面当然它都是这个树里面的
合理的这种有序对。那在这个
路径里面我们任何结中间的一段,它也是路径了。
那在这个路径里面靠近根的方向呢,就是称为祖先结点,
反过来呢就是,靠近叶的这个方向呢,就是后代结点。
结点的度数呢,在树里面是非常重要的,
因为在二叉数里面我们反正只有两个结点。
那在树里面,这个每一个结点的子树个数
可能有多大,那我们预计着这个树它大概会有多宽。 还有层数,我们定义根为第0层,
其它的结点所在的层次呢,就是它的负结点 的层数加1。
那深度其实就是层数最大的那样一个叶结点的层数。
高度呢是层数加1,我们也可以这么说,
深度呢实际上可以看作是这个
边的这样的层数;那高度呢,我们可以看作是 结点有多少层。
树有以下各种形式,那我们来看一下它的表达形式。
最传统的就是一个倒挂的树,那根在上面,叶在下面,这是非常形象的一种表达。
那我们还有形式化的这种表达,实际上就是用集合论来
表达的这集点集,然后关系集,注意这个关系呢,是有向的
边的关系。我们还可以用文氏图来表达,
因为数呢,它是一个 层次化的一个有向无环图。因此呢,
如果用文氏图来表达,我们就可以看到
它这些圈圈代表的这些集合呢,它们是互相嵌套的,
不会相交。那如果我们在这个文氏图中,
我们把它们的这个圈圈都排在同一个水平线上,
然后中间划一刀,我们把这些圈圈呢,都把它展成括号的形式,
就变成了嵌套括号的表达。 那这个嵌套括号的表达呢,它其实就是
对树这么一个复杂的非线性结构的一个
线性化,也就是序列化的工作。那序列化了以后,我们就可以把整棵树呢,存在文件里面,
保存起来。我们也可以从文件里面把这么一个序列读出来,
恢复成为内存里面表达的一个树的结构。