[TOC]
# 树的概念
树（Tree）：树是n（n>=0）个结点的有限集T，T为空时称为**空表**，否则它满足一下两个条件：
+ 有且仅有一个特定的称为**根（root）**的结点
+ 其余的结点可分为m(m>=0)个互不相干的子集T1、T2、T3...Tm，其中每个子集本身又是一棵树，称为**子树**。
**树的图形表示**
结点：通常使用**圆圈**表示
结点名字：一般写在圆圈旁边（有时写在圆圈内），如图：
通常有四种表示法：树形表示法、嵌套集合表示法、凹入表表示法、广义表表示法。
**树结构常用的基本术语**
+ 度（Degree）：一个树拥有的子树数。
+ 叶子（Leaf）或终端结点：度为零的结点。
+ 分支结点或非终端结点：度不为零的结点
+ 内部结点：除根结点之外的分支结点
+ 开始结点：根节点又称为开始结点。
> 一棵树的度指的是该树结点的最大的度数。
> 如上图中的A、B、E的度分别为3、2、0。
> 树的度为 3 。
> C、E、G、H、I、J均为叶子。
+ 孩子（Child）或儿子：树中某个结点的子树之根，该结点称为**双亲**或父亲。
+ 兄弟：同一个双亲的孩子
> 例子：
> 上图中，B是A的子树T1的根，B是A的孩子，A是B的双亲。
> B、C、D互为兄弟。
+ 路径（Path）或道路：若树中存在一个结点序列k<sub>1</sub>,k<sub>2</sub>,k<sub>3</sub>....k<sub>j</sub>，使得k<sub>1</sub>是k<sub>i+1</sub>的双亲，则称该结点是从 k1 到 kj的一条路径。路径的长度为：j-1。
> 例子：
> 如上图：
> 结点 A 到 I有一条路径： `ABFI`，它的长度为 3。
+ 祖先（Ancestor）：树中结点 k 到 k<sub>s</sub>存在一条路径，那么k是k<sub>s</sub>的祖先，k<sub>s</sub>是k的子孙（Descendant）
约定：结点 k 的祖先和子孙不包含结点 k本身。
> 例子：
> `F` 的祖先：A、B；
> `F` 的子孙：I、J。
+ 结点的层数是从 根 算起的，设层数为 1。
+ 堂兄弟：双亲在同一层的结点互为**堂兄弟**。
+ 树的高度（Height）或深度（Depth）：树种结点的最大层数。
> 例子：
> A的层数：1，I、J的层数：4；
> E、F和G、H互为堂兄弟，该树的高度：4
> Note：很多书上树根定义的层数为 0.
+ 有序树（Ordered Tree）：树中的每个结点的各子树看成从左往右有次序的，则该树称为**有序树**，否则称为**无序树**。
> 例子：
> 下图中的两棵树，如果作为有序树则它们是不同的，因为A结点的两个孩子的左右次序不一样。作为无序树，它们是相同的。
+ 森林：m(m>=0)棵互不相交的树的集合。
> 删去一棵树的根，就得到了一个森林。
> 加上结点作为树根，森林变成了一棵树。
# 二叉树
二叉树（Binary Tree）：n (n>=0)个结点的有限集，它或者是空集(n=0)，或是由一个根节点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。
二叉树的五种基本形态：
+ 空二叉树
+ 仅有一个根节点的二叉树
+ 右子树为**空**的二叉树
+ 左子树为**空**的二叉树
+ 左右子树均为*非空***的二叉树
> 二叉树中每个结点最多只能由两颗子树，并有左右之分。（只有一颗子树也有左右之分）
## 二叉树的性质
+ **性质 1** 二叉树第 i 层的结点数目最多为`2<sup>i-1</sup>(i>=1)`。
+ **性质 2** 深度为 k 的二叉树至多为`2<sup>k</sup>-1(k>=1)`个结点。
+ **性质 3** 在任意一颗二叉树中，若终端结点的个数为 n<sub>0<sub>，度为 2 的结点数为n<sub>2<sub>，则 `n<sub>0<sub> = n<sub>2<sub> + 1`
**满二叉树**
一棵深度为 k 且有 2<sup>k-1</sup> 个结点的二叉树。
特点：每一层上的结点数达到最大值；满二叉树不存在度数为 1 的结点，每个分支结点均有两棵高度相等的子树。
**完全二叉树**
若一颗二叉树至多只有最下面的两层上的结点的度数小于2，并且最下层上的结点都集中在最左边的若干位置。
> 满二叉树是完全二叉树，反之则不成立。
在满二叉树的最下一层，从最右边开始**连续删去**若干结点后得到二叉树仍是一棵完全二叉树。
+ **性质 4** 具有 n 个结点的完全二叉树的深度为 └lgn┘ + 1或者┌lg(n+1)┐。
## 二叉树的存储结构
**1. 顺序存储结构**
完全二叉树使用顺序结构存储既简单又节省空间。一般二叉树使用顺序结构存储也会按照完全二叉树的存储结点，会造成空间的浪费。
**2. 链式存储结构**
|lchild|data|rchild|
|-----|----|----|
数据结构的说明为：
```c
typedef char DataType;
typedef struct node{
DataType data;
struct node *lchild, *rchild; // 左右孩子指针
}BinType; // 结点类型
typedef BinType * BinTree;
```
二叉链表：二叉树的链式存储结构。
> 一个二叉链表由根指针 root 唯一确定。
> 若二叉树为空，则 root = NULL
> 若结点的某个孩子不存在，则相应的指针为 空。
具有 n 个结点的二叉树的二叉链表表示中，一种有 `2n` 个指针域，其中只有`n-1`个用来表示结点的左右孩子，其余`n+1`个指针域为空。如图：
## 二叉树的遍历
给定任意结点，可以按照某种次序执行三个操作：
+ 访问结点本身（N）
+ 遍历该节点的左子树（L）
+ 遍历该结点的右子树（R）
以上这三种操作还有六种执行顺序：
+ NLR
+ LNR
+ LRN
+ NRL
+ RNL
+ RLN
前三种次序是左子树总是先于右子树被遍历。
我们将这三种遍历分别称为：
+ **前序遍历(Preorder Traversal)**或**先序遍历**： NLR（先根遍历）
+ 中序遍历（Inorder Traversal）:LNR（中根遍历）
+ 后续遍历（Postorder Traversal）:LRN（后根遍历）
N(Node)、L(Left subtree)、R(Right subtree)可理解为根、根的左子树、根的右子树
### 中序遍历
递归算法定义为：
+ 遍历左子树
+ 访问根节点
+ 遍历右子树
递归的终止条件为：二叉树为空
使用二叉链表作为存储结构，算法如下：
```c
void Inorder(BinTree T) {
if (T) {
Inorder(T->lchild);
printf("%c", T->data); // 访问结点
Inorder(T->rchild);
}
}
```
**构造二叉链表**
```c
void CreateBinTree(BinTree *T) {
char ch;
if ((ch = getchar()) == ' ') {
*T = NULL; // 写入空格，将相应指针置空
} else {
*T = (BinTree *)malloc(sizeof(BinTree)); // 生成结点
(*T)->data = ch;
CreateBinTree(&(*T)->lchild); //构造左子树
CreateBinTree(&(*T)->rchild); //构造右子树
}
}
```
时间复杂度为： O(n)， n表示树的结点数
## 线索二叉树
用二叉链表作为存储结构时，它只有左右孩子的指针域，没办法存储结点的前趋和后继结点的指针，这种附加的指针称为**线索**。加上线索的二叉链表为**线索链表**，相应的二叉树为**线索二叉树（Threaded Binary Tree）**。
其结构如下：
| lchild | ltag | data | rtag | rchild |
| --- | --- | --- | --- | --- |
左标志：ltag
+ 0: lchild是指向结点的左孩子的指针
+ 1：lchild是指向结点的前趋的左线索
右标志：rtag
+ 0: rchild是指向结点的右孩子的指针
+ 1：rchild是指向结点的前趋的右线索
一个结点是叶结点的充要条件：它的左、右标志均为1
线索化：二叉树变成二叉线索树的过程。
> 按照某种次序将二叉树线索化，只要按该次序遍历二叉树，在遍历过程中用线索代替空指针。
二叉树线索化的算法：
```c
typedef enum {Link, Thread} PointerTag; // 枚举值Link、Thread分别为0,1
typedef struct node {
DataType data;
PointerTag ltag, rtag; //左右标志
struct node *lchild, *rchild;
} BinThrNode;
typedef BinThrNode *BinThrTree;
BinThrNode *pre = NULL; //全局量，始终指向刚刚访问过的结点
// 将二叉树 p 线索化
void InorderThreading(BinThrTree p) {
if (p) {
InorderThreading(p->child); // 左子树线索化
// 以下相当于遍历算法中访问结点操作
// 左指针非空左标志为Link(即0)，否则为Thread（即为1）
p->ltag = (p->lchild) ? Link : Thread; p->ltag = (p->lchild) ? Link : Thread;
p->rtag = (p->rchild) ? Link : Thread;
if (pre) { // 若*p的前趋*pre存在
// *p的前趋右标志为线索
if (pre->rtag == Thread) {
pre->rchild = p; // 令*pre的右线索指向中序后继
}
// *p的左标志为线索
if (p->ltag == Thread) {
p->lchild = pre;// 令*pre的左线索指向中序前趋
}
}
pre = p; // 令pre的下一访问结点的中序前趋
InorderThreading(p->rchild); //右子树线索化
}
}
```
**二叉树上常见的运算**
1. 查找某结点 *p 在指定次序下的前趋和后继结点
中序线索二叉树求**中序后继结点**的算法：
① 若 *p 的右子树空（即p->rtag == Thread），则p->rchild为右线索。直接指向 *p 的中序后继。
② 若 *p 的右子树非空（即p->rtag == Link），则*p的中序后继必是其右子树中第一个中序遍历结点（从*p的右孩子开始，沿着孩子的左链往下找，直到找到一个没有左孩子的结点为止）。
```c
// 在中序线索树中找结点 *p 的中序后继。设p非空
BinThrNode * InorderSuccessor(BinThrNode *p){
BinThrNode *q;
// *p的右子树为空
if (p->rtag == Thread ) {
return p->rchild; // 返回右线索指的中序后继
} else {
q = p->rchild;// 从*p的右孩子开始查找
while(q->ltag == Link) {
q = q->lchild; // 左子树非空时，沿左链往下查找
}
return q; // 当 q 的左子树为空时，他就是最左下结点
}
}
```
2. 遍历线索二叉树
中序遍历算法:
```c
void TraverseInorderThrTree(BinThrTree p) {
if (p) {
while (p->ltag == Link) {
p = p->lchild;
}
do {
printf("%c", p->data); // 访问结点
p = InorderSuccessor(p); // 找*p的中序后继
}while( p );
}
}
```
解释：中序序列的终端结点的右线索为空，所以do语句的终止条件是 `P == NULL`。
## 树和森林
### 树、森林到二叉树的转换
**1. 树、森林到二叉树的转换**
**树转换为二叉树**
树中的每个结点可能有多个孩子，但二叉树种每个结点最多有两个孩子。
树中每个结点最多只有一个最左的孩子和一个右邻的兄弟。
所以将**将树转换成相应的二叉树为**：
+ 在所有的兄弟结点之间加一些线；
+ 对每个结点，除了保留其长子的连线外，去掉该结点与其他孩子的连线。
**森林转换为二叉树**
+ 先将森林中的每棵树变为二叉树；
+ 将各二叉树的根连接视为兄弟结点从左往右连在一起。
**2. 二叉树到树、森林的转换**
+ 若结点 x 是其亲 y 的左孩子，则把x的有孩子，右孩子的右孩子，... 都与y用线连接起来
+ 最后去掉所有双亲到右孩子的连线。
### 树的存储结构
+ 双亲链表表示法
+ 孩子链表表示法
+ 孩子兄弟链表表示法
**1. 双亲链表表示法**
在树中，每个结点的双亲是唯一的。
形式说明如下：
```c
#define MaxTreeSize 100
typedef char DataType;
typedef struct {
DataType data;
int parent; // 双亲指针，指示结点的双亲在向量中的位置
}PTreeNode;
typedef struct {
PTreeNode nodes[MaxTreeSize];
int n; //结点总数
}PTree;
PTree T; // T是双亲链表
```
若 `T.nodes[i].parent == j`，则`T.nodes[i] == T.nodes[j]`。如E、F所在结点的双亲域是1，表示它们的双亲结点在向量中的位置是 1，即B是它们的双亲。
> 根无双亲，其`parent`为-1
**2. 孩子链表表示法**
```c
// 孩子链表结点
typdedef struct cnode{
int child; // 孩子结点在向量中对应的序号
struct cnode *next;
}CNode;
typedef struct {
DataType data; // 存放树中的结点数据
CNode * firstchild; // 孩子链表的头指针
}PTNode;
typedef struct {
PTNode nodes[MaxTreeSize];
int n, root; // n为结点总数，root指出根在向量中的位置
}CTree;
CTree T; // T为孩子链表表示
```
上图使用孩子链表表示如下：
说明：
当结点
**3. 孩子兄弟链表表示法**
