本文共 3609 字，大约阅读时间需要 12 分钟。

为什么需要树结构

• 线性结构中的顺序存储和链式存储的优缺点

  1）数组存储方式的分析
  优点： 通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。
  缺点： 如果要检索具体某个值，或者插入值（按一定顺序）会整体移动，效率较低。

  2）链式存储方式的分析

  优点： 在一定程度上对数组存储方式有优化，插入，删除元素效率比较好。
  缺点： 在进行检索时，需要进行整个遍历，效率较低 。

• 所以为了提高数据的存储和读取效率，引入树结构

  3）树存储方式的分析

\quad \quad 能提高数据存储，读取的效率，比如利用二叉排序树，既可以保证 数据的检索速度，同时也可以保证数据的插入、删除、修改的速度。

一.树的定义

树： 树是一种**抽象数据类型（ADT）**或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是n($n>=0$)个结点的有限集合。当n=0时，称为空树。

任意一棵非空树满足以下条件：

1）有且仅有一个特定的结点称为根的结点

2）当n>1时，除根结点之外的其余结点被分成m(m>0)个互不相交的有限集合$T_1,T_2,...,T_m$,其中每一个集合又是一棵树，并称为这个根结点的子树。

二.树的基本术语

结点的度：结点所拥有的子树的个数即有几个孩子

树的度：树中各结点度的最大值

叶子结点：度为0的结点，也称为终端结点。

分支结点：度不为0的结点，也称为非终端结点。

孩子、双亲：树中某结点子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点

兄弟：具有同一个双亲的孩子结点互称为兄弟。

路径：如果树的结点序列$n_1,n_2,...,n_k$有如下关系：结点$n_i$是$n_i+1$的双亲（1<=i<k),则把$n_1,n_2,...,n_k$称为一条由$n_i$至$n_k$的路径，路径上经过的边的个数称为路径长度。

祖先、子孙：在数中，如果有一条路径从结点x到结点y,则x称为y的祖先，而y称为x的子孙。

结点所在层数：根结点的层数为一，对其余任何结点，若某结点在第K层，则其孩子结点在第K+1层。

树的深度：树中所有结点的最大层数， 也称高度。

层序编号：将树中结点按照从上层到下层、同层从左到右的次序依次给他们编号以从1开始的连续自然数。

有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的，称这棵树为有序树；反之，无序树。

森林：m(m>=0)棵互不相交的树的集合。

在图6—1中，A是祖先，L则是它的子孙；树的高度为4；

三.树的抽象数据类型（ADT Tree)

Data

树是有一个根节点和若干棵子树构成， 数中结点具有相同数据类型及层次关系 Operation InitTree:初始化一棵树 DestroyTree:销毁一棵树，释放内存空间 PreOrder:前序遍历 PostOrder:后序遍历

树的遍历：

\quad \quad 从根结点出发，按照某种次序访问数中所有结点，使得每一个结点被访问一次且仅被访问一次

遍历的实质：

\quad \quad 树结构(非线性结构)–>线性结构

前序遍历：根结点、左子树结点、右子树结点

1.若树为空，则空操作返回 2.否则，访问根结点，按照从左到右的顺序前序遍历根节点的每一颗子树。 前序遍历上图：A B D E H I F C G 含有递归原理

后序遍历：左子树结点、右子树结点、根节点

1.若树为空，则空操作返回 2.按照从左到右的顺序后序遍历根节点的每一颗子树。 后序遍历上图：D H I E F B G C A

层次遍历：

从树的第一层（即根节点）开始，自上而下逐层遍历，在同一层中，按照从左到右的顺序对结点逐个访问。 层次遍历上图：A B C D E F G H I

四.树的存储结构

\quad \quad 实现树的存储结构，关键是如何表示树中结点之间的逻辑关系；

\quad \quad 存储结构就是数据元素以及数据元素之间的逻辑关系在存储器中的表示； \quad \quad 顺序存储结构：用一段地址连续的存储单元依次存储线性表的数据元素。这对于线性表来说是很自然的，对于树一对多的结构不适合。

\quad \quad 充分利用顺序存储和链式存储结构的特点，可以实现对树的存储结构的表示。

4.1 双亲表示法

基本思想:

用一维数组来存储树的各个结点（一般按层序存储），数组中的一个元素对应树中的一个结点，包括结点的数据信息以及该结点的双亲在数组中的下标。

data	parent

data:存储树中结点的数据信息

parent：存储该结点的双亲在数组中的下标

树的双亲表示法实质上是一个静态链表

例子：

-1表示空值，即其结点没有双亲，当parent指针为-1时，表示此结点为根结点。

查找双亲结点:

根据parent指针很容易就能找到它的双亲结点； 时间复杂度：O(1) 例如：B结点的parent指针为0，则B的双亲为下标为0的A。

查找孩子结点：

遍历整个结构，寻找parent指针为其在数组中的下标所对应的数据域为孩子结点。比较复杂。

因此我们可以再加一个最左边孩子的域，就可以很容易找到结点的第一个孩子。

例如：B结点的firstchild指针为3，则B的第一个孩子结点为下标为3的D。 此时，时间复杂度为：O（1）

查找兄弟结点，所有孩子结点：

在上面的基础上，加上一个右同胞的域。 例如：

B结点的rightSib指针为2，则B的兄弟结点为下标为2的C。

A的firstchild指针为1，则A的第一个孩子结点为下标为1的B。又B结点的rightSib指针为2，则B的右兄弟结点为下标为2的C。又C结点的rightSib指针为-1，则C无右兄弟。则A的所有孩子结点为B,C。

-1模拟链表中的空指针的概念，往往表示链表的结束。

4.2 孩子表示法

如何表示孩子？

链表中的每一个结点包括一个数据域和多个指针域，每个指针域指向该结点的一个孩子结点。

方案一：指针域的个数等于树的度。

其中：

data:数据域，存放该结点的数据信息

child1~childn:指针域，指向该结点的孩子

优点:比较直观 缺点：浪费空间，指针域为空就比较浪费空间

方案二：指针域的个数等于该结点的度。

链表中的每一个结点包括一个数据域和多个指针域，每个指针域指向该结点的一个孩子结点。

缺点：结点结构不一致，编写程序比较困难。

方案一与方案二都有彼此的缺点，都不太好。

方案三——孩子链表表示法

将结点的所有孩子放在一起，构成线性表。

孩子链表的基本思想：

把每个结点的孩子排列起来，看成是一个线性表，且以单链表存储，则n个结点共有n个孩子链表，如果是叶子结点则此单链表为空。这n个单链表共有n个头指针，这n个头指针又组成了一个线性表，为了便于进行查找采用顺序存储。最后，将存放n个头指针的数组和存放n个结点的数组结合起来，构成孩子链表的表头数组。

此存储结构需设计两种结点结构

孩子结点

其中child是数据域，用来存储某个结点在表头数组中的下标。next是指针域，用来存储指向某个结点的下一个孩子结点的指针。

表头结点

其中data是数据域，存储某结点的数据信息。firstchild是头指针域，用来存储该结点的孩子链表的头指针。

分析：A结点的第一个孩子是B，其在表头数组中的下标为1，故头指针指向1;A结点的第二个孩子是C，其在表头数组中的下标为2，故next指针指向2。 D、F、G、H、I均为叶子结点，没有孩子，故头指针为空。

查找孩子结点

时间复杂度为O(1)

查找双亲结点

需要从上到下偏历，时间性能比较低。

双亲孩子表示法：

是孩子链表表示法的改进，可以快速的查找孩子结点以及双亲结点。在孩子链表的基础上增加一列，存放双亲结点在数组中的下标。

以链表的静态存储模式表示双亲结点，链表的方式存储孩子结点。 这种存储方式，查找孩子以及双亲都是很方便的

4.3 孩子兄弟表示法

某结点的第一个孩子是唯一的；某结点的右兄弟是唯一的。

因此，可以设置两个分别指向该结点的第一个孩子和右兄弟的指针。

结点结构：

五.树结构与线性结构的比较

	线性结构	树结构
第一个数据元素	无前驱	又称根节点（只有一个）：无双亲
最后一个数据元素	无后继	叶子结点（可以有多个）：无孩子
其他数据元素	一个前驱，一个后继	其他结点：一个双亲，多个孩子
关系	一对一	一对多