(此文为王道数据结构学习笔记，只供个人后续复习使用，若有错误，还望指出我改正，谢谢）
中序线索化：
找中序前驱，从根结点开始，对整个二叉树进行中序遍历，并用pre指针指向当前访问结点的前驱，当当前访问结点指向想要找的结点时，pre指针指向的即是该结点的中序前驱。
typedef struct ThreadNode{
ElemType data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag;//线索标志
}ThreadNode, * ThreadTree;//线索二叉树结点
void InThread(ThreadTree T){
if(T!=NULL){
InThread(T->lchild);
visit(T);
InThread(T->lchild);
}//进行中序遍历
}
void visit(ThreadNode *q){
if(q->lchild==NULL){ //如果当前结点没有左子树
q->lchild=pre;//左孩子指向前驱
q->ltag=1;//将ltag置1，表面该左孩子为线索
}
if(pre!=NULL&&pre->rchild==NULL){//右孩子指向后继
pre->rchild=q;
pre->rtag=1;
}
pre=q;//pre向下一个结点移动
}
void CreateInThread(ThreadTree T){//建立线索树
pre=NULL;
if(T!=NULL){//如果线索树不为空，进行中序遍历
InThread(T);
if(pre->rchild==NULL)
pre->rtag=1;//处理最后一个结点的右孩子
}
}
ThreadNode *pre = NULL;//全局变量pre，指向当前访问节点的前驱结点先序线索化的原理与中序线索化大致一致，只需将遍历流程改为前序遍历即可。但容易出现以下情况：对于一个无左孩子的结点，由于先进行根结点（即该结点的）访问，此时经过 visit 操作，已将该结点的左孩子指向了该结点前驱。再按照先序遍历流程，此时又应该访问该结点的左子树，而由于该结点左孩子指向前驱，就会导致函数进行循环。此时需要加个判断条件，如果该节点的 ltag =1（即该左孩子为线索），就不对左子树进行遍历，而直接执行下一条语句，遍历右子树。
void PreThread(ThreadTree T){
if(T!=NULL){
visit(T);
if(T->ltag==0)
InThread(T->lchild); //判断是否左孩子已是线索
InThread(T->lchild);
}//进行前序遍历
}
后序线索化只需将遍历改为后序遍历即可。
线索二叉树找前驱/后继
中序线索二叉树找中序后继：
对于一个有线索的结点，其右孩子结点指向即为其中序后继；
对于一个没有线索的结点，中序遍历的后继结点必然是其右子树中的结点，那么则沿着其右子树，开始判断是否有左孩子，有的话以该左孩子为根结点，继续判断是否有左孩子，直到左孩子为线索时，该结点即为初始结点的后继。逻辑上即为中序遍历顺序为? ：左 根 右——》左 根 （左 根 右）——》左 根 【（左 根 右）根 右】。
代码实现一个中序线索树的线索遍历：
//找一个结点的最左下的结点
ThreadNode *Firstnode(ThreadNode *p){
while(p->ltag==0)
p=p->lchild;//如果左孩子不为线索，即继续往左孩子遍历
return p;
}
//寻找一个中序线索树的结点的后继
ThreadNode *Nextnode(ThreadNode *p){
if(p->rtag==0)//如果该结点右孩子不为线索
return Firstnode(p-rchild);//则找最左下结点为后继
else return p-rchild;//如果为线索，则该右孩子指向后继
}
void Inorder(ThreadNode *){
for(ThreadNode *p=Firstnode(T);p!=NULL;p=Nextnode(p))
visit(p);
}
//利用线索实现对中序线索二叉树的中序遍历
//由于不使用自身调用递归，此函数的空间复杂度为O(1)中序线索二叉树找中序前驱：
对于一个有线索的结点，其左孩子结点指向即为其中序前驱；
对于一个没有线索的结点，中序遍历的前驱结点必然是其左子树中的结点，那么则沿着其左子树，开始判断是否有右孩子，有的话以该右孩子为根结点，继续判断是否有右孩子，直到右孩子为线索时，该结点即为初始结点的前驱。逻辑上即为中序遍历顺序为? ：左 根 右——》（左 根 右）根 右——》【左 根 （左 根 右）】 根 右。
//找一个结点的最右下的结点
ThreadNode *Lastnode(ThreadNode *p){
while(p->ltag==0)
p=p->rchild;//如果右孩子不为线索，即继续往右孩子遍历
return p;
}
//寻找一个中序线索树的结点的前驱
ThreadNode *Prenode(ThreadNode *p){
if(p->ltag==0)//如果该结点左孩子不为线索
return Firstnode(p->lchild);//则找最右下结点为前驱
else return p-lchild;//如果为线索，则该左孩子指向前驱
}按照这个方式，可以对中序线索二叉树实现逆向遍历
先序线索二叉树的前驱/后继：
先序遍历顺序是 根 左 右
如果有线索，则左孩子线索为前驱，右孩子线索为后继。如果没有线索，则有：
后继：
对于一个先序线索二叉树的结点，如果有左孩子，其后继则为左孩子，如果其没有左孩子，则后继为其右孩子；
前驱：
对于一个先序线索二叉树的结点，其前驱一定不会在自己的左右孩子中，而是有以下可能：
1.该结点为其父结点的左孩子，按照 根 左?右，其父结点则为其前驱；
2.该结点为其父节点的右孩子，但其父结点无左孩子，按照 根（无左）右 其父结点为其前驱；
3.该结点为其父节点的右孩子，其父结点有左孩子，按照 根 左 右，从其左兄弟的子树中找最下方的那个结点，即为其前驱；；
4.该结点为根结点，其无前驱；
只通过先序线索二叉树，无法找到某结点的前驱，如果有父结点指针，则可找到。
后序线索二叉树的前驱/后继：
后序遍历顺序是 左 右 根
如果有线索，则左孩子线索为前驱，右孩子线索为后继。如果没有线索，则有：
后继：
对于一个先序线索二叉树的结点，其后继一定不会在自己的左右孩子中，而是有以下可能：
1.该结点为其父结点的右孩子，按照 左 右 根，其父结点则为其后继；
2.该结点为其父节点的左孩子，但其父结点右孩子，按照 左（无右）根?其父结点为其后继；
3.该结点为其父节点的左孩子，其父结点有右孩子，按照 左 右 根，从其右兄弟的子树中找最下方的那个结点，即为其后继；
4.该结点为根结点，其无后继；
只通过后序线索二叉树，无法找到某结点的后继，如果有父结点指针，则可找到。
前驱：
对于一个后序线索二叉树的结点，如果其有左孩子，而无右孩子，则左孩子为其前驱；如果其有右孩子，则右孩子为其前驱；
普通树的存储结构：
双亲表示法（顺序存储）：每个结点中保存指向保存双亲的指针。用静态数组存放。
#define MAX_TREE_SIZE 100
typedef struct {
ElemType data;
int parent;
}PTNode;//树结点的结构体
typedef struct{
PTNode nodes[MAX_TREE_SIZE];
int n;
}PTree;//树的结构体孩子表示法（顺序+链式存储）：每个结点保存指向自己第一个孩子的指针。用静态数组存放。
struct CTNode{
int child;//存放该孩子的位置
struct CTNode *next;//指向下该孩子的下一个兄弟结点
};//每个结点的第一个孩子指针的结构体
typedef struct {
ElemType data;
struct CTNode *firstChild;//指向第一个孩子
}CTBox;//结点的结构体
typedef struct{
CTBox nodes[MAX_TREE_SIZE];
int n , r;//结点数，根结点位置
}CTree;//用数组存放结点
孩子兄弟表示法（链式存储）：每个结点保存指向自己第一个孩子和右边第一个兄弟的指针。
typedef struct CSNode{
ElemType data;
struct CSNode *firstchild,*nextsibling;
//第一个指针指向自己的第一个孩子，第二个指针指向自由右边的兄弟
}CSNode,*CSTree;如果将结构体中的两个指针分别用【*lchild】与【*rchild】替换，则可把普通树转化成二叉树。
森林转化二叉树（本质为孩子兄弟表示法）
先将普通树转为二叉树，再同过根结点的右指针连接。
?
对树的遍历：
先根遍历：先访问根结点，再访问所有子树；
后根遍历：先访问所有子树，再访问根结点；
层序遍历：一层一层进行访问。（广度优先）
对于一个普通树，用孩子兄弟法转化为二叉树，先根遍历等于其二叉树的先序遍历；后根遍历等于其二叉树的中序遍历；
森林的先序遍历：对每个子树依次进行先根遍历。
森林的中序遍历：对每个子树依次进行后根遍历。
通过孩子兄弟法，有以下关系：
?
二叉排序树（BST）（二叉查找树）
左子树的值比根结点的值小，右子树比根结点的值大，同样的，每个子树也有这样的特点；
对二叉排序树进行中序遍历，可以得到一个递增序列。
查找二叉排序树的某个值：
循环算法：空间复杂度为O(1)
BSTNode *BST_Search(BSTree T,int key){
while(T!=NULL&&key!=T->key){//若结点空或者找到了结束循环
if(key<T->key)
T=T->lchild;//小于则从左子树找
else
T=T->rchild;//大于则从右子树找
}
return T;
}递归算法：空间复杂度为O(h)
BSTNode *BST_Search(BSTree T,int key){
if(T==NULL)
return NULL;//失败
if(key==T->key)
return T; //找到
else if(key< T->key)
return BST_Search(T->lchild,key);//小于则从左子树找
else
return BST_Search(T->rchild,key);//大于则从右子树找
}二叉排序树的插入
若原二叉排序树为空，则直接插入结点；否则，若关键字小于根结点则插入左子树，大于则插入右子树。
int BST_Insert(BSTree &T,int k){
if(T==NULL){
T=(BSTree)malloc(sizeof(BSTNode));//给新结点分配空间
T->key=k;
T->lchild=T->rchild=NULL;
return 1;//插入失败
}
else if(k==T->key)
return 0;//插入的值原树已有，插入失败
else if(k<T->key)
return BST_Insert(T->lchild, k);
else if(k>T->key)
return BST_Insert(T->rchild, k);
}构造一个二叉排序树（按照序列 str[] 建立BST）
void Create_BST(BSTree &T,int str[],int n){
T=NULL;//初始时树为空
int i=0;
while(i<n){//将每个关键字插入
BST_Insert(T,str[i]);
i++;
}
}删除结点：
1.删除的是叶子结点，直接找到删除即可；
2.删除的结点只有一个子树，直接删除该结点后，用子树替补自己的位置；
3.删除的结点有两个子树，直接删除该结点后，可以：A.用左子树的最大元素（即左子树最右下元素，同时为该结点的中序遍历前驱）顶替该结点；B.用右子树的最小元素（即右子树最左下元素，同时为该结点的中序遍历后继）顶替该结点。
平均查找长度（ASL）：
在查找运算中，需要对比关键字的次数为查找长度，反映了查找操作的时间复杂度，与其高度相关，高度越低，查找效率越高，即越平衡。
平均成功查找长度：把每种可能的情况查找次数加起来除以结点数；
平均失败查找长度：把到每个空链域的长度加起来除以空链域个数；
平衡二叉树（AVL）：
结点平衡因子：左子树高度-右子树高度
当每个结点平衡因子的绝对值小于等于1时，该树为平衡二叉树。
平衡二叉树的插入：
插入后，每个结点的平衡因子可能发生变动，此时从插入元素向前寻找，找到第一个平衡因子绝对值大于1的结点，以该结点做根结点的子树，即为最小不平衡子树，对该树进行调整，即可让整个树重新恢复平衡。
调整最小不平衡子树
?
?
?
?
?
?
?
?平衡二叉树的平均查找长度为O(LOG2N)，n为结点数，即O(h)，h为树高
哈夫曼树
结点的权：有某种显示含义的数值
结点的带权路径长度：从树的根到该结点的路径长度（边数）与结点权乘积
树的带权路径长度（WPL）：树中所有叶结点的带权路径长度之和
在n个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也成为最优二叉树
1.每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越长
2.哈夫曼树的结点总数为2N-1
3.哈夫曼树中不存在度为1的结点
4.哈夫曼树不唯一，但WPL必然相同且为最优
哈夫曼编码
可变长度编码，可根据数据出现频率（权值），让不同字符用不等长的二进制位表示
图
顶点>0，边>=0
无向图：无向边 （v，w）=（w，v）
有向图：有向边（也称弧），从V到W，则有V是弧尾，W是弧头，<V，W>
简单图：不存在重复边，不存在顶点到自身的边
多重图：可以存在重复边，结点可以自己关联自己
无向图：顶点的度为依附于该顶点得到边的条数
有向图：入度：其为终点的边的数量；出度：其为起到的边的数量。顶点的度等于其出度入度之和
路径：经过的顶点的序列，有向图的路径必须方向正确
回路：终点与起点相同的路径
简单路径：顶点不重复出现的路径
简单回路：除了终点和起点，顶点不重复的回路
路径长度：路径上边的数量
点到点的距离：两点之间的最短路径长度为点到点距离，若不能形成路径，则无穷
无向图中，若两点间有路径，则称它们是连通的
有向图中，若两点互相之间有路径，则称它们是强连通的
连通图：无向图中，每两个点之间均连通。强连通图至少n-1条边。非连通图，最多
强连通图：有向图中，每两个点之间均强连通。强连通图最少n条边（回路）
子图：从原图中找到几个顶点，同时合法的几条边，形成的图为新图。若选取了所有顶点，则为生成子图
连通分量：（无向图）
?强连通分量：（有向图）
?生成树：包含图中的全部顶点的一个极小连通子图（边尽可能地少，n-1），且不唯一
生成森林：
?边的权：每条边有数值
带权图/网：边上带有权值的图为带权图，也称网
带权路径长度：一条路径所有边的权值之和
无向完全图：任意两点之间都有边
有向完全图：任意两点之间都有方向相反的两条边
稀疏图与稠密图，相对的，前者边少
树：不存在回路的连通无向图（N-1条边，如果大于N-1，则一定有回路）
有向树：
?
图的存储：
邻接矩阵法：空间复杂度为O()
用二维数组来表示两个点之间的关系
#define MaxVertexNum 100
typedef struct{
char Vex[MaxVertexNum]; //顶点表
int Edge[MaxVertexNum][MaxVertexNum];//邻接矩阵、边表
//此处除了int 还可以是bool，因为只需要0和1，bool占空间更少
int vexnum,arcnum;//当前顶点数和边数
}MGragh;对于无向图，结点该行/列的邻接矩阵非零元素个数，即为它的度
对于有向图，结点的行元素个数为出度，结点列元素个数为入度，结点度为行列相加
带权图：
?
#define MaxVertexNum 100
#define INFINITY 最大int值
typedef char VertexType;//顶点数据类型
typedef int EdgeType;//权数据类型
typedef struct{
VertexType Vex[MaxVertexNum];
EdgeType Edge[MaxVertexNum][MaxVertexNum];
//边的权，若为0代表自己，INFINITY代表不连通
int vexnum,arcnum;//顶点数、弧数
}MGragh;邻接矩阵的性质
设图G的邻接矩阵为A(矩阵元素为0/1），则的元素 A?[ i ] [ j ] 等于由顶点 i 到顶点 j 的长度为n的路径的数目
?
邻接表法（顺序+链式存储）数组存放每个结点，类似于树的孩子指示法。邻接表不唯一
每个结点存其数据和指向第一条边的指针，每个边存储指向的结点序号和指向下一条边的指针
typedef struct VNode{
VertexTyoe data;//数据
ArcNode *first;//指向第一条边
}VNode,AdjList[MaxVertexNum];//结点结构
typedef struct ArcNode{
int adjvex;//该边指向的结点序号
struct ArcNode *next;//指向下一条边
InfoType info;//边的权值
}ArcNode;//边结构
typedef struct{
AdjList vertices;//数组存储每个结点
int vexnum,arcnum;//顶点数、边数
}ALGragh;//图结构?
?
十字链表法：
?
?
存在的问题：?
邻接多重表：?
?
?
?
图的多种存储结构的优劣：
?
图的基本操作：
?
