5.1 树

 

前面章节介绍了线性逻辑结构，本章和下一章将分别介绍树和图这两种非线性逻辑结构。线性结构中节点间具有唯一前驱、唯一后继关系，而非线性结构的特征是节点间前驱、后继关系不具有唯一性。其中在树形结构中节点间关系是前驱唯一而后继不唯一，即节点之间是一对多的关系；图结构中节点间前驱与后继可以不唯一，即节点之间是多对多的关系。直观地看，树结构是指具有分支关系的结构（其分叉、分层的特征类似于自然界中的树）。树形结构应用非常广泛，特别是在大量数据处理方面，如在文件系统、编译系统、目录组织等方面，显得更加突出。树和图的理论基础部分属离散数学内容，而在数据结构中所讨论的重点是关于树和图的结构存储及操作实现技术。

树形结构是非常重要的非线性结构，它用于描述数据元素之间的层次关系，如人类社会的族谱和各种社会组织机构的表示等。二叉树是一种典形的树形结构。由于它具有存储方便和操作灵活等优点，因此二叉树成为广泛使用的树形结构。本章介绍树和二叉树的相关概念、存储结构和基本运算算法的实现过程，以及哈夫曼树的相关知识。

本章主要内容

&        树和二叉树的递归定义与表示方式

&        二叉树的各种存储结构

&        线索二叉树的表示、基本操作

&        二叉树、树和森林之间的转换方法

&        最优二叉树的定义及带权路径长度的计算方法

&        哈夫曼树的建立过程和哈夫曼编码方法

5.1  树

本书在前面讨论了线性结构。通过削减在抽象数据类型List中定义的一些操作后，定义了两种新的抽象数据类型：栈和队列。可是，这些数据类型的下列结构是相同的：线性结构具有一个唯一的首节点，后面紧跟着唯一的第二个节点，接着是唯一的第三个节点，如此下去直至一个唯一的最后节点。线性结构是非常重要的，因为在很多情况下，信息具有自然的线性次序。但是从另一方面来说，在我们周围存在着大量的例子，其中信息并不组织成线性结构。这些结构摆脱了线性结构中一个跟着一个的严格限制，产生了更“自由”也更为复杂的非线性结构。从本章开始，我们将逐步放宽先前对抽象数据类型的限制，以产生新的和更为普遍的抽象数据类型。

树是树形结构的简称，本节讨论树的定义、表示方法和存储结构等基本概念。

5.1.1  树的定义

树包含n（n≥0）个节点，当n=0时，称为空树。树的定义如下：

T=(D,R)

其中，D为树中节点的有限集合，关系R满足以下条件：

（1）有且仅有一个节点k₀?D，它对于关系R来说没有前驱节点，节点k₀称做树的根节点。

图5-1  树的逻辑结构图

（2）除根节点k₀外，D中的每个节点有且仅有一个前驱节点，但可以有多个后继节点。

（3）D中可以有多个终端节点。

【例5-1】有一棵树T1=(D,R)，其中：

D={A,B,C,D,E,F,G,H}

R={r}

r={<A,B>,<A,C>,<A,D>,<C,E>,<C,F>,<D,G>,<E,H>}

给出其逻辑结构图。

解：该树中节点A没有前驱节点，是树根节点，该树的逻辑结构如图5-1所示。

一棵树分成几个大的分支（称做子树），每个大分支再分成几个小分支，小分支再分成更小的分支……每个分支也都是一棵树。由此可再给树下一个递归的定义：树是由一个或多个节点组成的有限集T，它满足下面两个条件。

（1）有一个特定的节点称为根节点。

（2）其余的节点分成m（m≥0）个互不相交的有限集T₁，T₂，……，T_m，其中每个集合本身又是一棵树，称T₁，T₂，……，T_m为树T的子树。

这种用树来定义树的递归定义反映了树的固有特性，也带来了很大的方便。

例如，图5-1所示的树中，A是根节点，其余节点分成3个互不相交的子集：T₁={B}，T₂={C,E,F,H}，T₃={D,G}。T1、T2、T3都是根节点A的子树，且其本身也是一棵树。

5.1.2  树的表示

树的逻辑结构表示有树形表示法、文氏图表示法、凹入表示法和括号表示法等。

（1）树形表示法。这是树的最基本的表示，使用一棵倒置的树表示树结构，非常直观和形象。图5-1就是采用这种表示法。

（2）文氏图表示法。使用集合以及集合的包含关系描述树结构。图5-2（a）是例5-1中树的文氏图表示法。

（3）凹入表示法。使用线段的伸缩关系描述树结构。图5-2（b）是例5-1中树的凹入表示法。

（4）括号表示法。将树的根节点写在括号的左边，除根节点之外的其余节点写在括号中并用逗号间隔来描述树结构。图5-2（c）是例5-1中树的括号表示法。

图5-2  树的其他表示法

5.1.3  树的基本术语

节点的度：树中每个节点具有的子树个数或者后继节点数称为该节点的度。例如，图5-1所示的树中节点A的度为3，节点D的度为1。

·    树的度：树中所有节点的度的最大值称为树的度。例如，图5-1所示的树的度为3。

·    分支节点：度大于0的节点称为分支节点。

·    叶子节点：度为0的节点称为叶子节点。例如，图5-1所示的树的叶子节点是B、H、F、G。

·    孩子节点：一个节点的后继称为该节点的孩子节点。例如，图5-1中树的节点A的孩子节点为B、C和D。

·    双亲节点：一个节点称为其后继节点的双亲节点。例如，图5-1中树的节点E和F的双亲节点均为C。

·    子孙节点：一个节点的所有子树中的节点称为该节点的子孙节点。

·    祖先节点：从树根节点到达一个节点的路径上通过的所有节点称为该节点的祖先节点。

·    兄弟节点：具有同一双亲的节点互相称为兄弟节点。例如，图5-1中树的节点E和F是兄弟节点。

·    非终端节点：有子节点的节点。

·    终端节点：没有子节点的节点称为终端节点。

·    节点层数：树具有一种层次结构，根节点为第一层，其孩子节点为第二层，如此类推得到每个节点的层数。例如，图5-1中树的节点层数是4。

·    树的深度：树中节点的最大层数称为树的深度或高度。例如，图5-1中树的深度是4。

·    树的高度：树中某节点的高度表示此节点至叶节点的最长路径（Path）长度，而树的高度为此棵树的根节点到最深层叶节点的路径长度。

·    有序树和无序树：如果一棵树中节点的各子树从左到右是有次序的，即若交换了某节点各子树的相对位置，则构成了不同的树，称这棵树为有序树，反之，则为无序树。

·    森林：0个或多个不相交的树的集合称为森林。

5.1.4  树的存储结构

在计算机中存储一棵树，不仅要存储树中每个节点的数值，而且还要存储节点之间的关系。下面介绍3种常用的存储结构。

1．双亲数组存储结构

用一个一维数组存储树中的各个节点，数组元素是一个记录，包含data和parent两个字段，分别表示节点的数据值和其双亲在数组中的下标。其类型定义如下：

typedef struct

{  

    ElemType data;

    int parent;

} ParType[MaxSize];

在这个一维数组中，树中节点可按任意顺序存放。

例如，图5-1中给出的树，它的双亲数组存储表示如图5-3所示。其中，规定下标为0的位置存储的节点是根节点。

图5-3  树的双亲数组存储结构

在双亲数组中，找某个节点的双亲或祖先是很方便的，但要找某个节点的孩子或兄弟则较麻烦，需要遍历整个数组。

2．孩子链表存储结构

把每个节点的孩子节点排列起来，构成一个单链表，称为孩子链表。n个节点的树有n个这样的孩子链表，其中，树叶的孩子链表为空表。为便于查找，n个链表的表头指针放在一个顺序表中。这个顺序表中的每个元素有两个字段：一个存放节点的值；另一个存放第一个孩子的地址。孩子链表中的每个节点也有两个字段：指示孩子节点的值存放的位置；另一个存放下一个孩子的地址。在顺序表中，各元素可以按任意顺序存放。在每个孩子链表中，各节点也可以按任意顺序链接。

单链表中每个节点的类型定义如下：

typedef struct node1

{  

    int adjvex;                             /*该节点值在顺序表中的位置*/

    struct node1 *next;

} ChildType;

顺序表的类型定义如下：

typedef struct

{  

    ElemType data;

    ChildType *children;

} Child[MaxSize];

图5-4是图5-1所示树的孩子链表存储结构。其中，规定表头中下标为0的位置存储的节点是根节点。

图5-4  树的孩子链表存储结构

显然，在孩子链表中，找某个节点的孩子很容易，但找节点的双亲则较困难。

3．孩子兄弟链表存储结构

孩子兄弟链表存储结构是一种二叉链表，链表中每个节点包含两个指针，分别指向对应节点的第一个孩子和下一个兄弟。每个节点的类型定义如下：

typedef struct node2

{  

    ElemType data;

    struct node2 *child,*brother;

} CBNodeType;

图5-5是图5-1所示树的孩子兄弟链表存储结构，其中，T₁指针指向树的根节点。

图5-5  树的孩子兄弟链表存储结构