本文最后更新于：2020年9月29日 上午

6.2 树的定义

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

• n > 0 时根节点是唯一的，不可能存在多个根节点
• m > 0 时，子树的个数没有限制，但它们一定是互不相交的

1. 结点的分类

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

2. 结点间的关系

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

3. 树的其他相关概念

• 结点的层次（Level）从根开始定义起，根为第一层，根的孩子为第二层
• 双亲在同一层的结点互为堂兄弟
• 数中结点的最大层次称为树的深度（Depth）或高度
• 森林（Forest）是 m(m>=0)棵互不相交的树的集合

6.3 树的抽象数据类型

ADT 树（Tree）
Data
	树是由一个根节点和若干棵子树构成。树中结点具有相同数据类型及层次关系。
Operation
	InitTree(*T); 构造空树 T。
	DestoryTree(*T); 销毁树 T。
	CreateTree(*T, definition); 按 definition 中给出树的定义来构造树。
	ClearTree(*T); 若树 T 存在，则将树 T 清空。
	TreeEmpty(T); 若 T 为空树，返回 true 否则返回 false。
	TreeDepth(T); 返回 T 的深度。
	Root(T); 返回 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

6.4 树的存储结构

1. 双亲表示法

• 以一组连续空间存储树的结点，在每个结点中，附设一个指示器指示其双亲结点到链表中的位置

• 根节点的位置域设置为 -1

data	parent
数据域：存储结点的数据信息	指针域：存储该结点的双亲在数组中的下标

双亲表示法的结点结构定义代码

/* 树的双亲表示法结点结构定义 */
#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;

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

2. 孩子表示法

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

孩子表示法的结构定义代码

/* 树的双亲表示法结点结构定义 */
#define MAX_TREE_SIZE 100
typedef int TElemType;              // 树结点的数据类型, 目前暂定为整型

/* 树的孩子表示法结构定义 */
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;

3. 孩子兄弟表示法

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

结点结构如表

data	firstchild	rightsib
数据域	指针域：存储该节点的第一个孩子结点的存储地址	指针域：存储该结点的右兄弟结点的存储地址

结构定义代码如下

/* 树的双亲表示法结点结构定义 */
#define MAX_TREE_SIZE 100
typedef int TElemType;              // 树结点的数据类型, 目前暂定为整型

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

6.5 二叉树的定义

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

1. 二叉树的特点

• 每个结点最多有两棵子树
• 左子树和右子树是有顺序的，次序不能任意颠倒
• 即使树中某个结点只有一棵子树，也要区分它是左子树还是右子树

2. 特殊二叉树

• 左斜树：所有的结点都只有左子树
• 右斜树：所有的结点都只有右子树

• 线性表结构可以理解为是树的一种极其特殊的表现形式

• 满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上

• 完全二叉树：对一棵具有 n 个结点的二叉树按层序编号，如果编号为 i (1<=i<=n)的结点与同样深度的满二叉树中编号为 i 的结点在二叉树中位置完全相同，则这颗二叉树称为完全二叉树

6.6 二叉树的性质

• 在二叉树的第 i 层上至多有 $2^{i-1}$ 个结点（i>=1）
• 深度为 k 的二叉树至多有 $2^k-1$ 个结点 (k>=1)
• 对任何一颗二叉树 T，如果其终端结点数为 $n_0$ ，度为 2 的结点数为 $n_2$，则$n_0=n_2+1$
• 具有 n 个结点的完全二叉树的深度为 $[log_2n]+1$，[x]表示不大于 x 的最大整数
• 如果对一颗有 n 个结点的完全二叉树（其深度为$[log_2n]+1$）的结点按层序编号（从第 1 层到第$[log_2n]+1$层，每层从左到右 ），对任一结点 i（1<=i<=n）有：
  • 如果 i=1，则结点 i 是二叉树的根，无双亲；如果 i > 1，则其双亲是结点 [i/2]
  • 如果 2i>n，则结点 i 无左孩子（结点 i 为叶子结点）；否则其左孩子是结点 2i
  • 如果 2i+1 > n，则结点 i 无有孩子；否则其右孩子是结点 2i+1

6.7 二叉树的存储结构

1. 二叉树顺序存储结构

• 二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系。

• 一种极端的情况，一棵深度为 k 的右斜树，它只有 k 个结点，却需要分配 $2^k-1$ 个存储单元空间，显然是对存储空间的浪费，所以顺序存储结构一般只用于完全二叉树。

2. 二叉链表

二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域，这样的链表叫做二叉链表

二叉链表的结点结构定义代码

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

6.8 遍历二叉树

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

1. 二叉树的遍历方法

• 前序遍历：若二叉树为空，则空操作返回，否则先访问根节点，然后前序遍历左子树，再前序遍历右子树。
• 中序遍历：若树为空，则空操作返回，否则从根节点开始（注意并不是先访问根节点），中序遍历跟结点的左子树，然后访问根节点，最后中序遍历右子树
• 后序遍历：若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后访问根节点
• 层序遍历：若树为空，则空操作返回，否则从第一层，也就是根节点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问
• 这四种遍历方法都是把树中的结点变成某种意义的线性序列，给程序的实现带来了好处
• ps : 前序中序后序其实指的是根节点的位置

2. 前序遍历算法

二叉树的定义是用递归调用的方式，实现遍历算法也可以采用递归

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

3. 中序遍历算法

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

4. 后序遍历算法

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

5. 推导遍历结果

• 已知一棵二叉树的前序遍历序列为 ABCDEF，中序遍历序列为 CBAEDF，请问这棵二叉树的后序遍历结果是什么？CBEFDA
• 二叉树的中序序列是 ABCDEFG，后序序列是 BDCAFGE，求前序序列？ EACBDGF
• 注意：已知前序和后序遍历，不能确定一棵二叉树。

6.9 二叉树的建立

• 扩展二叉树：将二叉树中每个结点的空指针引出一个虚结点，其值为一特定值 “#”。

前序遍历：

//按前序输入二叉树中结点的值（一个字符）
// #表示空树，构造二叉链表表示二叉树 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;	//生成根节点
        CreatBiTree(&(*T)->lchild);		//构造左子树
        CreatBiTree(&(*T)->rchild);		//构造右子树
    }
}

6.10 线索二叉树

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

• 线索二叉树等于是把一棵二叉树转变成了一个双向链表
• 对二叉树以某种次序遍历使其变成线索二叉树的过程称做是线索化
• 在每个结点增设两个标志域 ltag 和 rtag，只存放 0 或 1 数字的布尔型变量

1. 线索二叉树结构实现

二叉树的线索存储结构定义代码

typedef enum {Link, Thread} PointerTag;	//Link==0表示指向左右孩子指针
										//Thread==1表示指向前驱或后继的线索
typedef struct BiThrNode
{
    TElemType data;						//结点数据
    struct BithrNode *lchild, *rchild;	//左右孩子指针
    PointerTag LTag;
    PointerTag RTag;
}BiThrNode, *BiThrTree;

由于前驱和后继的信息只有在遍历该二叉树时才能得到，所以线索化的过程就是在遍历的过程中修改空指针的过程。

中序遍历线索化的递归函数代码：

BiThrTree pre;	//全局变量，始终指向刚刚访问过的结点
void InThreading(BiThrTree p)
{
    if(p)
    {
        InThreading(p->lchild);		//递归左子树线索化
        if(!p->lchild)
        {
            p->LTag = Thread;	//前驱线索
            p->lchild = pre;	//左孩子指针指向前驱
        }
        if(!pre->rchild)	//前驱没有右孩子
        {
            pre->RTag = Thread;	//后继线索
            pre->rchild = p;	//前驱右孩子指针指向后继
        }
        pre = p;
        InThreading(p->rchild);		//递归右子树线索化
    }
}

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

6.11 树、森林与二叉树的转换

树的孩子兄弟法可以将一棵树用二叉链表进行存储，所以借助二叉链表，树和二叉树可以相互进行转换。

1. 树转换为二叉树

• 加线。在所有兄弟结点之间加一条连线
• 去线。对树中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线。
• 层次调整。注意第一个孩子是二叉树结点的左孩子，兄弟转换过来的孩子是结点的右孩子。

2. 森林转换为二叉树

• 把每个树转换为二叉树
• 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根节点作为前一棵二叉树的根节点的右孩子，用线连接起来

3. 二叉树转换为树

• 加线。若某结点的左孩子结点存在，则将这个左孩子的 n 个右孩子结点都作为此结点的孩子。将该结点与这些右孩子结点用线连接起来
• 去线。删除原二叉树中所有结点与其右孩子结点的连线。
• 层次调整

4. 二叉树转换为森林

看这棵二叉树的根节点有没有右孩子，有就是森林，没有就是一棵树

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

5. 树与森林的遍历

• 森林的前序遍历和二叉树的前序遍历结果相同，森林的后序遍历和二叉树的中序遍历结果相同
• 当以二叉链表作树的存储结构时，树的先根遍历和后根遍历完全可以借用二叉树的前序遍历和中序遍历的算法来实现

6.12 赫夫曼树及其应用

最基本的压缩编码方法 - 赫夫曼编码。

1. 赫夫曼树定义与原理

• 从树中一个结点到另一个结点之间的分支构成两个结点之间的路径
• 树的路径长度就是从树根到每一结点的路径长度之和
• 带权路径长度WPL最小的二叉树称做赫夫曼树，也称为最优二叉树

2. 构造赫夫曼树的赫夫曼算法描述

• 根据给定的 n 个权值{w1,w2,…,wn}构成 n 棵二叉树的集合F={T1,T2,…Tn}，其中每棵二叉树Ti中只有一个带权为wi根节点，其左右子树均为空
• 在 F 中选取两棵根节点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根节点的权值为其左右子树上根节点的权值之和
• 在F中删除这两棵树，同时将新得到的二叉树加入 F 中
• 重复2和3步骤，直到F只含一棵树为止，这棵树便是赫夫曼树