第6章 树

树（Tree）是 n（n≥0）个结点的有限集。n=0 时称为空树。在任意一棵非空树中：（1）有且仅有一个特定的称为根（Root）的结点；（2）当 n>1 时，其余结点可分为 m（m>0）个互不相交的有限集 T₁、T₂、……、T_m，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。

树的定义

树（Tree）是 n（n≥0）个结点的有限集。n=0 时称为空树。在任意一棵非空树中：（1）有且仅有一个特定的称为根（Root）的结点；（2）当 n>1 时，其余结点可分为 m（m>0）个互不相交的有限集 T₁、T₂、……、T_m，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。

结点分类

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

结点拥有的子树数称为结点的度（Degree）。度为 0 的结点称为叶结点（Leaf）或终端结点；度不为 0 的结点称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。

结点间关系

结点的子树的根称为该结点的孩子（Child），相应的，该结点称为孩子的双亲（Parent）。同一个双亲的孩子之前互称兄弟（Sibling）。结点的祖先是从根到该结点所经分支上的所有结点。反之，以某结点为根的子树中的任一结点都称为该结点的子孙。

树的其他相关概念

结点的层次（Level）从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第 1 层，则其子树的根就在第 i+1 层。其双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度（Depth）或高度。

如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。

森林（Forest）是 m（m≥0）棵互不相交的树的集合。

线性表与树结构

树的抽象数据类型

ADT 树（tree）

Data

树是由一个根结点和若干子树构成。树中结点具有相同数据类型及层次关系。

Operation

InitTree(*T):构造空树 T。

DestroyTree(*T):销毁树 T。

CreateTree(*T, definition):按 definition 中给出树的定义来构造树。

ClearTree(*T):若树 T 存在，则将树 T 清为空树。

TreeEmpty(*T):若 T 为空树，返回 true，否则返回 false。

TreeDepth(T):返回 T 的深度。

Root(T):返回树的根结点。

Value(T, cur_e):cur_e 是树 T 中一个结点，返回此结点的值。

Assign(T, cur_e,value):给树 T 的结点 cur_e 赋值为 value。

Parent(T, cur_e):若 cur_e 是树 T 的非根结点，则返回它的双亲，否则返回空。

LeftChild(T, cur_e):若 cur_e 是树 T 的非叶结点，则返回它的最左孩子，否则返回空。

RightSibling(T, cur_e):若 cur_e 有右兄弟，则返回它的右兄弟，否则返回空。

InsertChild(T, p, i, c):其中 p 指向树 T 的某个结点，i 为所指结点 p 的度加上1，非空树 c 与 T 不相交，操作结果为插入 c 为树 T 中 p 指结点的第 i 棵子树。

DeleteChild(T, p, i):其中 p 指向树 T 的某个结点，i 为所指结点 p 的度，操作结果为删除 T 中 p 所指结点的第 i 棵子树。

endADT

树的存储结构

双亲表示法

我们假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器表示其双亲结点在数组中的位置。也就是说，每个结点除了知道自己是谁以外，还知道它的双亲在哪里。

以下是我们的双亲表示法的结点结构定义代码。

1
2
3
4
5
6
7
8
9
10
11
12
13

/* 树的双亲表示法结点结构定义 */
#define MAX_TREE_SIZE 100
typedef int TElemType; /* 树结点的数据类型，目前暂定为整型 */
typedef struct PTNode /* 结点结构 */
{
  TElemType data; /* 结点数据 */
  int parent; /* 双亲位置 */
} PTNode;
typedef struct  /* 树结构 */
{
  PTNode nodes[MAX_TREE_SIZE]; /* 结点数组 */
  int r,n;  /* 根的位置和结点数 */
} PTree

存储结构的设计是一个非常灵活的过程。一个存储结构设计的是否合理，取决于基于该存储结构的运算是否合适、是否方便，时间复杂度好不好等。

孩子表示法

由于树中每个结点可能有多棵子树，可以考虑用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点，我们把这种方法叫做多重链表表示法。

孩子表示法。把每个结点的孩子结点排列起来，以单链表作存储结构，则 n 个结点有 n 个孩子链表，如果是叶子结点则此单链表为空。然后 n 个头指针又组成一个线性表，采用顺序存储结构，放进一个一维数组中。

以下是我们的孩子表示法的结构定义代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

/* 树的孩子表示法结构定义 */
#define MAX_TREE_SIZE 100
typedef struct CTNode /* 孩子结点 */
{
  int child;
  struct CTNode *next;
} *ChildPtr;
typedef struct /* 表头结构 */
{
  TElemType data;
  ChildPtr firstchild;
} CTBox;
typedef struct /* 树结构 */
{
  CTBox nodes[MAX_TREE_SIZE]; /* 结点数组 */
  int r,n; /* 根的位置和结点数 */
} CTree;

孩子兄弟表示法

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。

结构定义代码如下。

1
2
3
4
5
6

/* 树的孩子兄弟表示法结构定义 */
typedef struct CSNode
{
  TElemType data;
  struct CSNode *fistchild,*rightsib;
} CSNode, *CSTree;

二叉树的定义

二叉树（Binary Tree）是 n（n≥0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

二叉树特点

二叉树的特点有：

• 每个结点最多有两棵子树，所以二叉树中不存在度大于 2 的结点。注意不是只有两棵子树，而是最多有。没有子树或者一棵子树都是可以的。
• 左子树和右子树是有顺序的，次序不能任意颠倒。
• 即使树中某个结点只有一棵子树，也要区分它是左子树还是右子树。

二叉树具有五种基本形态：

1. 空二叉树。
2. 只有一个根结点。
3. 根结点只有左子树。
4. 根结点只有右子树。
5. 根结点既有左子树又有右子树。

特殊二叉树

1. 斜树

所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

2. 满二叉树

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层，这样的二叉树称为满二叉树。

满二叉树的特点有：

（1）叶子只能出现在最下一层。

（2）非叶子结点的度一定是 2。

（3）在同样深度的二叉树中，满二叉树的结点个数最多，叶子树最多。

3. 完全二叉树

对一棵具有 n 个结点的二叉树按层序编号，如果编号为 i（1≤i≤n）的结点与同样深度的满二叉树中编号为 i 的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。

完全二叉树的特点：

（1）叶子结点只能出现在最下两层。

（2）最下层的叶子一定集中在左部连续位置。

（3）倒数二层，若有叶子结点，一定都在右部连续位置。

（4）如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况。

（5）同样结点的二叉树，完全二叉树的深度最小。

判断某个二叉树是否是完全二叉树的办法，就是看着树的示意图，心中默默给每个结点按照满二叉树的结构逐层顺序编号，如果编号出现空挡，就说明不是完全二叉树，否则就是。

二叉树的性质

二叉树的性质1

性质1：在二叉树的第 i 层上至多有 2^i-1 个结点（i≥1）。

二叉树的性质2

性质2：深度为 k 的二叉树至多有 2^k-1 个结点（k≥1）。

二叉树的性质3

性质3：对任何一棵二叉树 T，如果其终端结点数为 n₀，度为 2 的结点数为 n₂，则 n₀=n₂+1。

二叉树的性质4

性质4：具有 n 个结点的完全二叉树的深度为 ⎣log₂n⎦+1 ( ⎣x⎦表示不大于 x 的最大整数)。

注：⎣⎦ 向下取整运算。

二叉树的性质5

性质5：如果对于一棵有 n 个结点的完全二叉树（其深度为 ⎣log₂n⎦+1）的结点按层序编号（从第 1 层到第 ⎣log₂n⎦+1 层），每层从左到右，对任一结点 i （1≤i≤n）有：

1. 如果 i = 1，则结点 i 是二叉树的根，无双亲；如果 i>1，则其双亲是结点 ⎣i/2⎦。
2. 如果 2i>n，则结点 i 无左孩子（结点 i 为叶子结点）；否则其左孩子是结点 2i。
3. 如果 2i+1>n，则结点 i 无右孩子；否则其右孩子是结点 2i+1。

二叉树的存储结构

二叉树顺序存储结构

顺序存储结构一般只用于完全二叉树。

二叉链表

二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。

以下是我们的二叉链表的结点结构定义代码。

1
2
3
4
5
6

/* 二叉树的二叉链表结点结构定义 */
typedef struct BitNode /* 结点结构 */
{
  TElemType data; /* 结点数据 */
  struct BiTNode *lchild, *rchild; /* 左右孩子指针 */
} BiTNode, *BiTree;

遍历二叉树

二叉树遍历原理

二叉树的遍历（traversing biary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

二叉树遍历方法

1. 前序遍历

规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。

2. 中序遍历

规则是若树为空，则空操作返回，否则从根结点开始（注意不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。

3. 后序遍历

规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。

4. 层序遍历

规则是若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。

前序遍历算法

1
2
3
4
5
6
7
8
9

/* 二叉树的前序遍历递归算法 */
void PreOrderTraverse (BiTree T)
{
  if (T==NULL)
    return;
  printf("%c",T->data); /* 显示结点数据，可以更改为其他对结点操作 */
  PreOrderTraverse (T->lchild); /* 再先序遍历左子树 */
  PreOrderTraverse (T->rchild); /* 最后先序遍历右子树 */
}

中序遍历算法

1
2
3
4
5
6
7
8
9

/* 二叉树的中序遍历递归算法 */
void InOrderTraverse (BiTree T)
{
  if (T==NULL)
    return;
  InOrderTraverse (T->lchild); /* 中序遍历左子树 */
  printf("%c",T->data); /* 显示结点数据，可以更改为其他对结点操作 */
  InOrderTraverse (T->rchild); /* 最后中序遍历右子树 */
}

后序遍历算法

1
2
3
4
5
6
7
8
9

/* 二叉树的后序遍历递归算法 */
void PostOrderTraverse (BiTree T)
{
  if (T==NULL)
    return;
  PostOrderTraverse (T->lchild); /* 先后序遍历左子树 */
  PostOrderTraverse (T->rchild); /* 再后序遍历右子树 */
  printf("%c",T->data); /* 显示结点数据，可以更改为其他对结点操作 */
}

推导遍历结果

• 已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
• 已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
• 已知前序和后序遍历，是不能唯一确定一棵二叉树的。

二叉树的建立

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

/* 按前序输入二叉树中结点的值（一个字符） */
/* #表示空树，构造二叉链表表示二叉树 T。 */
void CreateBiTree (BiTree *T)
{
  TElemType ch;
  scanf("%c",&ch);
  if (ch=='#')
    *T=NULL;
  else
  {
    *T=(BiTree)malloc(sizeof(BiTNode));
    if (!*T)
      exit (OVERFLOW);
    (*T)->data=ch; /* 生成根结点 */
    CreateBiTree(&(*T)->lchild); /* 构造左子树 */
    CreateBiTree(&(*T)->rchild); /* 构造右子树 */
  }
}

线索二叉树

线索二叉树原理

指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树（Threaded Binary Tree）。

对二叉树以某种次序遍历使其变为线索二叉树的过程叫做是线索化。

线索二叉树结构实现

1
2
3
4
5
6
7
8
9

/* 二叉树的二叉线索存储结构定义 */
typedef enum (Link, Thread) PointerTag; /* Link==0 表示指向左右孩子指针 Thread==1 表示指向前驱或后继的线索 */
typedef struct BiThrNode /* 二叉线索存储结点结构 */
{
  TElemType data; /* 结点数据 */
  struct BiThrNode *lchild, *rchild; /* 左右孩子指针 */
  PointerTag LTag;
  PointerTag RTag; /* 左右标志 */
} BiThrNode, *BiThrTree;

线索化的过程就是在遍历的过程中修改空指针的过程。

如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择。

树、森林与二叉树的转换

树转换为二叉树

将树转换为二叉树的步骤如下

1. 加线。在所有兄弟结点之间加一条连线。
2. 去线。对树中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线。
3. 层次调整。以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。注意第一个孩子是二叉树结点的左孩子，兄弟转换过来的孩子是结点的右孩子。

森林转换为二叉树

步骤如下：

1. 将每个树转换为二叉树。
2. 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。当所有的二叉树连接起来后就得到了由森林转换来的二叉树。

二叉树转换为树

1. 加线。
2. 去线。
3. 层次调整。

二叉树转换为森林

1. 从根结点开始，若右孩子存在，则把右孩子结点的连线删除，再查看分离后的二叉树，若右孩子存在，则连线删除……，直到所有右孩子连线都删除为止，得到分离的二叉树。
2. 再将每棵分离的二叉树转换为树即可。

树与森林的遍历

树的遍历分为两种方式。

1. 一种是先根遍历树，即先访问树的根结点，然后依次先根遍历根的每棵子树。
2. 另一种是后根遍历，即先依次后根遍历每棵子树，然后再访问根结点。

森林的遍历也分为两种方式：

1. 前序遍历
2. 后序遍历

赫夫曼树及其应用

赫夫曼树定义与原理

从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称做路径长度。

树的路径长度就是从树根到每一个结点的路径长度之和。

带权路径长度 WPL 最小的二叉树称做赫夫曼树。

赫夫曼编码

一般地，设需要编码的字符集为{d₁,d₂,…,d_n}，各个字符在电文中出现的次数或频率集合为 {w₁,w₂,…,w_n}，以 d₁,d₂,…,d_n 作为叶子结点，以 w₁,w₂,…,w_n 作为相应叶子结点的权值来构造一棵赫夫曼树。规定赫夫曼树的左分支代表 0，右分支代表 1，则从根结点到叶子结点所经过的路径分支组成的 0 和 1 的序列便为该结点对应字符的编码，这就是赫夫曼编码。