6.1 树的定义和基本术语在线视频

同学们大家好，我是云南大学信息学院教师孔兵

这一章我们讨论树和二叉树

树形结构是一类非常重要的非线性结构

它的特点是结点之间有分支

并且有明显的层次关系

就形态上来说

有点类似于自然界中

倒着长的树

在很多现实问题中

都可以利用树来描述数据元素之间的关系

比如说常见的家谱

一个家族内部成员之间的关系表面上看是很复杂的

描述很困难

经过抽象，我们注意到

家族成员最核心的关系是父子关系

其它很多关系都被父子关系所蕴含

比如说，A是B的父亲，B是C的父亲

蕴含了A是C的爷爷这样的关系

A是B的父亲，A是C的父亲

蕴含了B和C是兄弟的关系

基于父子关系

可以建立描述一个家族成员之间父子关系的一个树形结构

行政组织机构中

成员之间最核心的关系是领导的关系

同样可以建立描述领导关系的一个树形结构

树形结构的特点是一个前驱

多个后继

家谱中，一个成员的双亲是唯一的

只有一个前驱，但是该成员可能有多个孩子

那么就是有多个后继

回忆一下线性结构

它的特点是一个前驱一个后继

从描述上看，线性结构是树结构的一种特殊情况

例如，如果一个家族每代都只有一个孩子

该家族的家谱就是一个线性结构

我们首先讨论一下

树的定义和本章当中要用到的基本术语

树是n个结点的有限集

在任意一颗非空的树中

有且仅有一个特定的我们称为根的结点

当n大于1的时候，也就是说树中除了根还有其它的结点

那么其余结点可以分成m个互不相交的有限集

T1,T2,....,Tm。其中每个有限集本身又是一棵树

并且称为根的子树

从树的定义，我们注意到

定义树这个概念的时候

又用到了子树的概念

这是一个明显的递归的定义

下面我们结合图示看一下

图中有2课树，上面一棵树是只有根结点的树

也就是树中只有一个结点

下面这棵树，A是树根

其余结点分为3个互不相交的有限集

这三个有限集就是3棵子树

3颗子树的根是B, C, D

这样的递归定义可以继续下去

例如D为为根的这棵子树，有三棵子树

树根A和子树根B,C,D之间是前驱和后继的关系

A是B，C, D的前驱，B，C, D是A的后继

A有3个后继

从图中可以看出，树结构明显的一个前驱

多个后继的关系

例如，D有一个唯一的前驱A

D有三个后继H, I, J

通过观察可以看到

树有明显的层次关系

例子当中，A可以看作一层

B，C, D可以看做一层

同样可以看出下面还有两层

图示中是树结构的图形表示

这里关系用一条线表示

实际上关系同样的有向的

我们同样可以用形式化的方式描述树结构

树的数据结构也是用两个集合来描述

描述数据元素的集合D

描述数据元素之间关系的集合R

如图所示，元素的集合D中

有A,B，到m这些树中的元素

元素之间的关系仍然用有序对来描述

在关系集R中

我们用有序对描述了这棵树当中所有的前驱和后继的关系

例如，前三个有序对描述了

A有三个后继B，C, D

对应的B，C, D有一个共同前驱A

根A是没有前驱的，它是比较特殊的一个点

其它所有结点都有唯一的前驱

下面看一下树的抽象数据类型定义

仍然是用三个集合定义抽象数据类型

数据元素集和关系集前面已经说过

这里不重复了

树的基本操作集中

包含很多基本操作

同学们可要参看教材

这里简单的列举了3个

第1个基本操作是求树的深度

第2个基本操作是求树中某一个结点的双亲

最后一个是对树的遍历操作

下面我们介绍一下本章中的一些基本的术语

结点，结点是包含一个数据元素及若干指向其子树的分支

在树中，我们把每个数据元素看成为一个结点

并利用所谓的分支描述结点之间前驱和后继的关系

结点的度，指的是一个结点拥有的子树的树目

树中每个结点都有一个度

比如图中，A的度是3

它有B，C, D为根的三棵子树

B结点的度为2，它有两棵子树

F的度为0，它没有子树

基于结点度的概念，定义了叶子或终端结点

我们把度为零的结点称为叶子或终端结点

图中的树有L,F,G,M,I,J六个叶子结点。

度不为零的结点，也就是有后继的结点

我们称为非终端结点，或者叫分支结点

树的度是指树中各结点的度的最大值

就这个示例的树来说

各结点度的最大值是3

那么这棵树的度就是3

孩子和双亲

是树中前驱和后继结点对应的一个叫法

结点子树的根，称为该结点的孩子

比如说，A有孩子B，B是A的后继

对应的该结点，就称为孩子的双亲

A有孩子B

那么对应的A称为B的双亲

一个结点的双亲，实际上就是它的前驱

树中每个结点的前驱是唯一的

兄弟，同一双亲的孩子之间，称为兄弟

比如H,I,J就是兄弟，它们有共同的双亲D

祖先和子孙

一个结点的祖先是从根到该结点所经分支上的所有结点

以结点L为例

从根结点A开始到L

所经分支的结点有A,B,E

那么，A,B,E都称为L的祖先

反之，以某结点为根的子树中的任一结点

都称为该结点的子孙

比如对A结点来说

其余所有结点都是它的子孙

而对C结点来说，它只有一个子孙G

层次，树是有明显的层次结构的

结点的层次从根开始定义

根为第1层，根的孩子为第2层

以此类推

示例中的这棵树有4层

堂兄弟

其双亲在同一层的结点

互为堂兄弟

如图中F,G,H这三个结点

它们的双亲，B，C, D在同一层

所以它们三个互为堂兄弟

深度是树中结点的最大层次

图中，树的最大层次是4

所以这个树的深度为4

森林是m棵互不相交的树的集合

示例中，有三棵树

这三棵树构成了所谓的森林

有序树和无序树

树中结点的各子树

如果能看成从左至右是有次序的

它们的位置不能互换

则称该树为有序树

否则该树为无序树

一棵树是否有序，主要和它描述的问题背景有关

例如，描述的如果是家谱

那么应该是有序树

因为，同一双亲的孩子之间

可能隐含着长幼之序

这样的子树位置是不能互换的

好同学们，今天这节课就讲到这里

下次课再见。