概念
树是什么
树(Tree)是n(n>=0)个结点的有限集。
n = 0的树是空树。
在任意一棵非空树中：
有且仅有一个称为根(Root)的结点。
当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1，T2，..., Tm。
其中每个结点本身又是一棵树，并且是根的子树(SubTree)。子树，是指父母结点的直接后代，不包含间接的。
结点的分类
结点的度（Degree）：结点拥有的子树数。注意，结点的子树，是指其直接后代。
结合下图理解。
叶结点（Leaf）或终端结点：度为0的结点。
非终端结点或分支结点：度不为0的结点。
内部结点：除根结点之外的分支结点。
树的度：树内各结点的度的最大值。
结点间关系
结点的孩子（Child）：根的子树是根的孩子。
结点的双亲（Parent）：子树的根是子树的双亲。
兄弟（Sibling）：同一个双亲的孩子之间互称兄弟。
结点的祖先：从根到该结点所经分支上的所有结点。
结点的子孙：以某结点为根的子树的所有结点是该结点的子孙。
上图中，D、B、A都是H的祖先。
树的其他概念
结点的层次(Level)：从根开始定义起，根为第一层，根的孩子为第二层。
堂兄弟：双亲在同一层的结点互为堂兄弟。
树的深度（Depth）或高度：树中结点的最大层次。
有序树：如果将树中各结点的子树看成是从左至右有次序的，不能互换的，那么这个树
就是有序树。否则，是无序树。
森林（Forest）：m(m>=0)棵互不相交的树的集合。对树中结点而言，其子树的集合，就是森林。
树的抽象数据类型
ADT 树(tree)
Data
树由一个根结点和若干子树构成。树中结点具有相同数据类型和层次关系。
Operation
InitTree(*T)：构造空树T。
DestroyTree(*T)：销毁树T。
CreateTree(*T, definition)：按definition中给出树的定义来构造树。
ClearTree(*T)：若树T存在，则将它清空为空树。
TreeEmpty(T)：若T为空树，返回true；若T不为空树，返回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+1
棵子树。
DeleteChild(*T, *p, i)：p指向T的某个结点，i为p所指结点的度，操作结果为
删除T中p指向的结点的第i棵树。
endADT
树的存储结构
双亲表示法
概念
以一组连续空间存储树的结点，每个结点除存储数据之外，还会存储一个指向该结点双亲
的指示器。
双亲表示法表示树的代码
#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;
下面是对上图的双亲表示法
只保存双亲的双亲表示法
保存双亲、长子域的双亲表示法
长子域是指结点的最左边的孩子结点。
知道了长子域，其他的孩子结点，如何获取？是紧挨长子域的这个结点吗？
保存双亲、右兄弟域的双亲表示法
孩子表示法
过渡
多重链表表示法：每个结点有多个指针域，其中每个指针指向一棵子树的根结点。
树的每个结点的度不同，对此，有两种解决方案。
一、每个结点的指针域的数量等于树的度
上图是对图6-4-1的表示，图6-4-1中的树的度是3，上图的每个结点的指针数量为何是4？
二、每个结点的指针域的数量等于该结点的度。此外，每个结点专门设置一个位置来存储该结点的度。
孩子表示法
孩子表示法的具体做法是：由一个线性表和一组单链表组成。线性表存储树的
n个结点。每个结点的孩子结点按顺序排列，存储在单链表中。n个结点，就有
n个单链表。叶结点的单链表为空。线性表的每个单元，由数据域和指向第一个
孩子的指针构成。单链表的每个单元，由数据域和指向它的兄弟结点的指针域
构成。
孩子表示法中包含两种结构的结点，具体情况看下图。
孩子表示法的一维数组图示：
孩子表示法结构定义代码
#define MAX_TREE_SIZE 100
// 孩子结点
typedef struct CTNode
{
/*1*/ int child;
struct CTNode *next;
} *ChildPtr;
// 表头结构
typedef struct
{
/*2*/ TElemType data;
ChildPtr firstChild;
} CTBox;
// 树结构
typedef struct
{
CTBox nodes[MAX_TREE_SIZE];
int r, n; // 根的位置和结点数
} CTree;
Line 1和Line 2数据类型不同的原因，从孩子表示法的定义去理解。孩子结点中，data存储
的是该结点在表头结构中的下标。
孩子结点的一些操作
查找某个结点的某个孩子。直接根据表头结构的firstChild查找。
查找某个结点的兄弟。先查到该结点在哪个单链表中，再根据该结点的next查找它的兄弟。
遍历整棵树。直接遍历表头结构。
找到某个结点A的双亲。这个操作对我有难度。思路是：两层循环。第一层，遍历整个表头结构，
如果某个表头单元等于A，那么跳过这个表头单元的单链表；否则，进入第二层循环，遍历单链
表。如果单链表中有一个元素等于A，那么，该单链表所属的表头元素，就是A的双亲。
孩子双亲表示法的改进--双亲孩子表示法
查找某个结点的双亲操作，繁琐。为解决此问题，改进孩子双亲表示法，得到双亲孩子表示法，如
下图。
孩子兄弟表示法
结点构成
孩子兄弟表示法中，一个结点由三部分组成：数据域（data），第一个孩子（firstChild）和第一个
右兄弟（rightsib）。
这样做的前提是，一个结点，若存在孩子结点和右兄弟，二者必然是唯一的。
孩子兄弟表示法，已知某个结点，下列操作：
- 查找双亲
- 查找左兄弟
- 遍历整棵树
都不好进行。有时间的话，应该想想这些该怎么做。
图示
结点图
树示意图
结点代码
typedef struct CSNode
{
TElemType data;
struct CSNode *firstChild, *rightsib;
} CSNode, *CSTree;
树的应用
文章评论数据结构的设计
需求
- 求一篇文章的所有评论数量
- 无限级评论
- 求一篇文章下的所有评论数据，包含对该文章的直接评论的的评论。
思考
之前是根据具体需求来构造满足查询需要的数据库结构，现在直接从树的几种存储结构里挑选。
先看“双亲表示法”
| id | parentId | passageId |
|---|---|---|
| 1 | 0 | 1 |
| 2 | 1 | 1 |
| 3 | 0 | 2 |
| 4 | 1 | 1 |
| 5 | 2 | 1 |
| 6 | 5 | 1 |
这个设计基本是原版的“双亲表示法”，能很好地满足第一个需求。第二个需求，若只是存储起来，也
满足了。
第三个需求，若在输出的时候，不同层次的评论，都无差别的输出，那这个设计也满足需求。但实际
需求没这么简单。
讨论两种情况。
一是分层次输出。获取数据的思路是这样的：
- 获取某篇文章下的所有第一级评论，即直接评论文章的
评论。 - 对所有的第一级评论数据进行遍历。
- 遍历的过程是这样的：获取某条评论的所有子评论，即对该评论的评论。
- 然后又对子评论进行遍历。这类似递归。遍历结束的条件是评论下面无子评论。
- 使用递归取得全部数据之后，在输出的时候，要需要使用多重嵌套循环。
如果对于不同层次的评论，页面输出为不同的层次效果，那好办。假如，有下面的评论数据
| id | parentId | passageId |
|---|---|---|
| 1 | 0 | 1 |
| 2 | 1 | 1 |
| 3 | 2 | 1 |
| 4 | 3 | 1 |
| 5 | 4 | 1 |
id为1的数据是对文章id为1的直接评论，id为2的评论是对id为1的评论，id为3的评论是对id为2
的评论的评论，id为4的评论是对id为3的评论的评论，id为5的评论是对id为4的评论。这些评论，
既可能是两个人的互相回复，也可能是多余两人之间的互相回复。
假设是两个人之间的互相回复，按照评论数据的固有层次关系输出数据可能没有必要。
假设需求：id为1的评论在第一层，其余4条评论全在第二层。
很好实现。遍历5条评论，parentId为0的评论在第一层，不为0的全在第二层。该设计可以进一步演化为
| id | parentId | passageId | parentCommentId |
|---|---|---|---|
| 1 | 0 | 1 | 0 |
| 2 | 1 | 1 | 1 |
| 3 | 2 | 1 | 1 |
| 4 | 3 | 1 | 1 |
| 5 | 4 | 1 | 1 |
在旧设计中，查询文章的一条一级评论，思路是先查出一级评论，然后使用parentId查询出一级评论的所有
子孙评论，期间多次使用遍历，出现多重嵌套循环。在新设计中，查出一级评论后，使用parentCommentId查
出一级评论的所有子孙评论，即使不借助数据库查询，也只是一层循环而已。
这里面有风险。如果需求变为根据评论数据的层次输出数据，那么，针对新设计的代码需要修改。应对这种需求
的最好方式是，把每条评论的层级存储起来，输出要求变动的时候，直接在已经获取的数据里加上层次属性，就
不必改动获取数据的代码。
数据库设计最终演变为
| id | parentId | passageId | parentCommentId | level |
|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 1 |
| 2 | 1 | 1 | 1 | 2 |
| 3 | 2 | 1 | 1 | 3 |
| 4 | 3 | 1 | 1 | 4 |
| 5 | 4 | 1 | 1 | 5 |
| 6 | 5 | 1 | 1 | 6 |
| 7 | 5 | 1 | 1 | 6 |
| 8 | 7 | 1 | 1 | 7 |
用这个结构：
- 查询一篇文章的所有评论，根据passageId。
- 查询一级评论的子孙评论，根据parentCommentId，避免了嵌套循环遍历数据。
- 一级评论及其子孙评论，输出，若有层次要求，根据level轻松满足各种层次输出要求。
避免了嵌套循环输出数据。 - 似乎也可以实现“盖楼评论”需求。它就是一级评论及其子孙评论。
孩子表示法
待思考。
孩子兄弟表示法
待思考。
二叉树
概念
二叉树是什么
二叉树(Binary Tree)是n(n>=0)个结点的有限集合。该集合可能是空的（空二叉树），也可能由
一个根结点和该根结点的左子树和右子树组成。左右子树不相交，而且都是二叉树。
二叉树的特点
每个结点最多有两棵字树，即每个结点的度和树的度不大于2。
结点的左子树和右子树是有顺序的，不能颠倒。
即使结点只有一棵子树，也是有顺序的。
二叉树的五种形态
空二叉树。
只有一个结点，即根。
只有左子树。
只有右子树。
同时有左子树和右子树。
特殊二叉树
斜树
左斜树是所有的结点都只有左子树的二叉树。
右斜树是所有的结点都只有右子树的二叉树。
左斜树和右斜树都是斜树。
满二叉树
如果一棵二叉树的所有分支结点都有左子树和右子树，并且所有的叶结点都在同
一层次上，它就是满二叉树。
完全二叉树
完全二叉树的定义（严格来说，不能称之为定义），是和满二叉树对比得出的。如果
一个二叉树，将之补充为满二叉树后，二叉树和补齐得到的满二叉树在相同位置上的
结点，序号相等，那么，这个二叉树就是完全二叉树。序号是指层级序号，在每一层，
从左至右地为结点编号。看下图。
满二叉树
非完全二叉树
树1编号11的那个结点，实际编号为10，11是该结点在满二叉树中的编号。两棵树中同
一个位置的结点，编号却不相同，所以树1不是完全二叉树。
二叉树的性质
性质一
在二叉树的第i层上至多有 $2^{i-1}$ 个结点 （i>=1）。
性质二
深度为 k 的二叉树最多有 $2^k-1$ 个结点（k>=1）。
性质三
对于任何一棵二叉树，如果终端结点的个数是为 $n_0$，度为2的结点个数是
$n_2$，那么， $n_0 = n_2 + 1$ 。
证明该性质，从两点着手，一个是树的总结点数，另一个是树的总连结线数。二者存在
一个等式。《大话数据结构》根据一个具体例子，抽象出等式，不严谨。
性质四
具有 n 个结点的完全二叉树的深度为 $「\log_2n」 + 1$ （ $「\log_2n」$ 表示不大于 $\log_2n$ 的最大整数）。
理解这个性质，花了很长时间。现在看书期间，我是没有时间可以这样恣意挥霍的！
理解 $n \geqslant 2^{k-1}$ 这个结论花了最多时间。抓住 k 是正整数这个关键点去理解！
最后推导出一个不等式
$k-1 \leqslant \log_2n \leqslant k$
由于 k 是正整数，那么， k 只能和 两头的值相等了。我不理解的是，为何取值等于后面那个而不是前面那个？
是我理解错了，性质四并不是说 k 等于 $\log_2n$，而是说把大于。这正好和上面的那个不等式吻合。
性质五
二叉树的存储结构
顺序存储结构
根据二叉树的性质五，能很快查出一个结点的双亲、左孩子和右孩子。
有些二叉树，比如右斜树，采用顺序存储结构，非常浪费空间。
二叉链表
如果一个链表的每个元素都有一个数据域和至多两个指针域，这样的链表就是二叉链表。
代码表表示：
typedef struct BiNode
{
TElemType data; // 结点数据
struct BiNode *lchild, *rchild; // 左右孩子指针
} BiNode, *BiTree;
遍历二叉树
定义
二叉树的遍历（traversing binary tree），是指从根结点出发，按照某种访问次序，访问二叉
树的所有结点。对所有的结点，都必须访问且只访问一次。
遍历方法
前序遍历
规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。
算法
void PreOrderTraverse(BiTree T)
{
if(T==NULL){
return;
}
printf("%c", T->data);
PreOrderTraverse(T->lchild); // 前序遍历左子树
PreOrderTraverse(T->rchild); // 前序遍历右子树
}
没想到遍历二叉树的代码会如此简单。受遍历示意图箭头指示方向影响，理解此代码一开始比较困惑。
中序遍历
算法代码
void InOrderTraverse(BiTree T)
{
if(T==NULL){
return;
}
InOrderTraverse(T->lchild); // 中序遍历左子树
printf("%c", T->data);
InOrderTraverse(T->rchild); // 中序遍历右子树
}
后序遍历
后序遍历方法
后序遍历图示
算法代码
void PostOrderTraverse(BiTree T)
{
if(T==NULL){
return;
}
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c", data);
}
层序遍历
层序遍历是最容易掌握和记住规则的遍历方法。
算法代码（书本没有提供，我自己写的代码）
// showData大于0时，输出数据域；否则，不输出
void LayOutTraverse(BiTree T, int showData)
{
if(T==NULL){
return;
}
if(showData){
printf("%c", T->data);
}
printf("%c", T->lchild->data);
printf("%c", T->rchild->data);
LayOutTraverse(T->lchild, 0); // 若输出数据域，会重复
LayOutTraverse(T->rchild, 0);
}
这些遍历二叉树的方法，看了并记住文字说明，也不一定能掌握。应该通过示意图去理解这些方法。文字说明作用
不大，我也就没必要通过打字加深记忆，故直接截图。
根据遍历结果推导二叉树
我不能熟练推导，需看着遍历方法说明来推导。可以多做这方面的练习。待记住遍历方法后，就可以独自推导了。
三个遍历二叉树的性质：
- 已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
- 已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
- 已知前序遍历序列和后序遍历序列，可以唯一确定一棵二叉树。
二叉树的建立
建立二叉树的方法
先将要创建的二叉树扩展为扩展二叉树，在选择遍历二叉树的方法来创建二叉树。
前序遍历法创建二叉树
代码
void CreateBiTree(BiTree *T)
{
TElemType ch;
scanf("%c", &ch);
if(ch == "#"){
*T = NULL;
}else{
*T = (BiTree)malloc(sizeof(BiNode));
if(!*T){
exit(OVERFLOW);
}else{
(*T)->data = ch;
CreateBiTree(&(*T)->lchild); // 构造左子树
CreateBiTree(&(*T)->rchild); // 构造右子树
}
}
}
中序遍历法创建二叉树
代码
void CreateBiTree(BiTree *T)
{
TElemType ch;
scanf("%c", &ch);
if(ch == "#"){
*T = NULL;
}else{
*T = (BiTree)malloc(sizeof(BiNode));
if(!*T){
exit(OVERFLOW);
}else{
CreateBiTree(&(*T)->lchild); // 构造左子树
(*T)->data = ch;
CreateBiTree(&(*T)->rchild); // 构造右子树
}
}
}
后序遍历法创建二叉树
层序遍历法创建二叉树
线索二叉树
概念
在二叉链表的一些结点，比如叶子结点，存在浪费的空间。将指向该结点的直接前驱
指针和后继指针存储在结点的空闲空间中。指向直接前驱的指针和指向后继的指针叫
“线索”。加上了线索的二叉链表叫做线索链表。相应的二叉树就是线索二叉树（Threaded Binary Tree）。
对二叉树以某种方法遍历使其变成线索二叉树的过程叫做线索化。这个过程，是在结点
的空闲空间中存储指向前驱或后继的指针。在空 rchild 中存储指向后继结点的指针，在
空 lchild 中存储指向前驱结点的指针。
线索二叉树结构代码
二叉线索存储结构代码
/**
* Link==0 表示指向左右孩子的指针
* Thread==1 表示指向前驱或后继的线索
*/
typedef enum {Link, Thread} PointerTag;
typedef struct BiThrNode
{
TElemType data;
struct BiThrNode *lchild, *rchild; // 左右孩子指针
PointerTag LTag; // 左右标志
PointerTag RTag;
}BiThrNode, *BiThrNode;
中序遍历线索二叉树代码（理解不了）
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; // 前驱右孩子指针指向后继（当前结点p）
}
pre = p; // 保持pre指向p的前驱
InThreading(p->rchild); // 递归右子树线索化
}
}
理解不了上面代码中的这部分（耗时至少半小时，无法思考，不知怎么去推理）
if(!pre->rchild){
pre->RTag = Thread;
pre->rchild = p; // 前驱右孩子指针指向后继（当前结点p）
}
为什么不是这样的？
if(!p->rchild){
p->RTag = Thread;
p->rchild = p; // 前驱右孩子指针指向后继（当前结点p）
}
原来在书中有解释！我没有看，自己白白浪费了那么多时间！
由于指针没有访问到p的后继，所以只能改变p的前驱pre的右孩子指针。仍然不能充分理解。
添加头结点后遍历线索二叉树代码（理解不了）
/**
* T指向头结点，头结点左链lchild指向根结点，
* 头结点右链rchild指向中序遍历的最后一个亮
* 点
*/
Status InOrderTraverse_Thr(BiThrTree T)
{
BiThrTree p;
p = T->lchild; // p指向根结点
while(p != T){ // 空树或遍历结束时，p == T
while(p->LTag==Link) // 当LTag==0时循环到中序序列第一个结点
p = p->lchild;
printf("%c", p->data); // 显示结点数据，可以更改为其他对结点操作
while(p->RTag==Thread && p->rchild != T){
p = p->rchild;
printf("%c", p->data);
}
p = p->rchild; // p进至其右子根树。这个说法很奇怪
}
return OK;
}
树、森林与二叉树的转换
树转换为二叉树
步骤如下：
加线。在所有兄弟结点之间加一条线。
去线。对树中的每个结点，只保留它与第一个孩子结点的连续，去掉它与其他所有孩子的连线。
层次调整。以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。注意第
一个孩子是二叉树结点的左孩子，兄弟转换过来的孩子是结点的右孩子。
这个规则最难把握好。
转换过程示意图
森林转换为二叉树
步骤如下：
把每棵树转换为二叉树。
第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点
的右孩子，用线连接起来。当所有的二叉树连接起来后就得到了由森林转换来的二叉树。
转换过程示意图
二叉树转换为树
步骤如下：
加线。若一个结点存在左孩子结点，在该结点和左孩子结点的右孩子结点、右孩子结点的右孩子结点（即
该结的的左孩子结点的所有右孩子结点）之间加线。去线。 删除树中原来的结点和右孩子结点间的连线。
层次调整。
转换过程示意图
二叉树转换为森林
步骤如下：
判断二叉树能否转换为森林。若它存在右孩子，则可以转换为森林。否则，只能转换为树。
从根结点开始，若右孩子存在，则把结点和右孩子之间的连线删除。对分离出来的二叉树执行相同的操作，
一直到分离出来的二叉树不存在右孩子为止。再将每棵分离后的二叉树转换为树即可。
转换过程示意图
树与森林的遍历
疑问：
用代码如何实现上面的遍历与转换操作？
经过转换之后，旧的结构等同于新的结构吗？对新结构的遍历等同于对旧结构的遍历吗？
赫夫曼树及其应用
概念
结点间的路径
从树中一个结点到另一个结点的分支叫做这两个结点间的路径。
路径长度
路径上的分支数目叫做路径长度。
树的路径长度
它是指从树根到每一个结点的路径长度之和。
带权的结点
不明白含义
结点的带权的路径长度
路径长度一般是对两个结点而言。结点的带权路径长度，特指该结点和根结点之间。它是该结点
到根结点的路径长度与结点上的权的乘积。
树的带权路径长度
它是指树中所有叶子结点的带权路径长度之和。
赫夫曼树的含义
设定几个条件，可以创建多个二叉树。
赫夫曼树是带权路径长度WPL最小的二叉树。
设定的条件是：权值固定，叶子结点数量固定。
赫夫曼二叉树构造方法
根据给定的
n个权值 $\lbrace w_1,w_2,w_3,...,w_n\rbrace$ 构成n棵二叉树的集合
$F = \lbrace T_1,T_2,T_3,...,T_n\rbrace$。每棵二叉树只有一个结点，且该结点的权值是
$w_n$。从
F中选取权值最小的两个二叉树，用它们创建一个新的二叉树。新二叉树的构成是：新建一个
结点，该结点的权值是两个二叉树的权值之和，权值小的那个二叉树作为新二叉树的左子树，大的那
个作为右子树。把新二叉树放到F中，替换之前选取的那两个二叉树。重复步骤 2 ，一直到
F中只包含一棵二叉树为止。这棵二叉树就是赫夫曼树。
前缀编码
若要设计长短不等的编码，那么，任意一个字符的编码都不能是其他字符的编码的前缀。这种编码叫前缀
编码。
赫夫曼编码
对要编码的字符串，分割出原子字符，按照原子字符权值构造出赫夫曼树，然后根据“左分支是0，右分支是1”
的规则，得到要原子字符的新编码，最后翻译出要编码的字符串编码后的01字符串。
