数据结构与算法(二)：二叉树与图

递归问题

递归和迭代是程序设计中的两种基本思想，从数列的思想中可以进行理解：迭代就是给出某个数列的位置（如第i个），就需要使用通项公式来进行计算；而递归则不关心这个通项公式是什么，它只关心邻近项（前一项、前两项......）进行计算，虽然对人脑而言，从第一项去推断成百上千的计算量是很大的，但是用于是固定形式的计算，这种方式对计算机却很友好，尽管有时候会导致不必要的计算，但是这种思想下的代码却显得十分简洁易写。

另一方面，迭代是一种for循环的思想，它需要用户知道需要迭代多少次，什么时候进行停止和计算，就像数组的查找一样。而递归类似while循环思想，给定退出的条件，我们并不关心它究竟执行了多少次，只要退出时是我们需要的结果，递归就算成功，就像链表索引，无论链表多长，我们总可以通过指针去索引后面的值直到最后一位。但是在树和图中，数据元素之间不再具有线性表这种一对一关系，使用迭代对程序员的思维而言过于庞大，因此大量的递归将在这两种数据结构中体现。

汉诺塔问题

汉诺塔是经典的递归问题：A柱子中有64个圆盘，分别有64个大小，现在需要把A柱子中的所有圆盘移动到C柱子，移动过程每根柱子必须遵循小圆盘在上、大圆盘在下的原则，这就决定了必须引入多一根柱子B柱。这是一个体验网站:汉诺塔游戏 我总结的最简单汉诺塔移动的规律是： 1. 为了得到64个圆盘在C柱子，要先得到63个圆盘（1-63）在B柱，于是此前要先得到62个圆盘（1-62）的在C柱，61个在B、60个在C......直到第一步是第一个在B。

2. 有了第一个规律，那么我们只关心一个过程，就是当B柱有了63个圆盘后，如何移动这63个圆盘使得64个圆盘都移动到C柱呢？

第一步的答案是显而易见的：就是把A中的第64个圆盘移到C柱作为最底部，剩下的63个B柱是不是要经过很复杂的移动呢？答案是肯定的，如果使用迭代，过程是相当复杂的。而递归则不然：现在B柱有63个圆盘，C柱有一个，A柱为空，目的是把B柱的盘移到C。 对比一下一开始的问题：A中64个圆盘，B柱为空，需要全部移到C。假如忽略C柱那一个盘（事实上确实忽略了），我们现在只要移动63个盘。是的，问题被降维了；同样的，如果这些你看懂了，那么下面的代码你也会明白：

#include <stdio.h>
int ret=0;  //记录步骤

//函数：把num个圆盘从a通过b移到c
void move(int num,char a,char b,char c){
    if(num==1){
        ret++;  //步数记录
        printf("No. %d Step:\n",ret); 
        printf("%c->%c\n",a,c); //如果只有1个，a直接移到c（或者b到c）
    }
    else{
        move(num-1,a,c,b); //对应规律1：把num-1个圆盘从a通过c，移到b（因为要先确保b有num-1个圆盘）
        ret++;  //步数记录
        printf("No. %d Step:\n",ret);
        printf("%c->%c\n",a,c); //规律2第一步：b有num-1个圆盘后，把a的圆盘（也就是最大的盘）移到c做底
        move(num-1,b,a,c); //规律2第二步：把b的num-1个圆盘通过a移到c
    }
}

int main(){
    int temp=0;
    printf("Please Input Layer_num:");
    scanf("%d",&temp);
    move(temp,'a','b','c');
return 0;}

所以移动64层汉诺塔需要多少步？答案是2^64-1步，这就是棋盘放米粒也能让全部粮食出口国破产的数字，假如移动一个盘子仅仅需要1秒，最快也要耗费5849亿年，人类诞生不过一百多万年，宇宙的年龄也只有大概138亿年。迭代解走错一步（而事实上也很难不走错），就要花费数倍于这个时间去弥补，使用递归的意义就是把复杂的问题降维，构建出简单的递归模型和算法，交给计算机解决。

当然上面的描述是过于割裂递归和迭代的关系，递归的本质也是一种栈结构，所以递归一定能使用迭代的栈来实现，很多时候递归的运行效率也不一定比迭代更加优秀，递归的最大特点就是简洁而已。

树

树结构是常见的数据结构，从根结点出发，连结其他结点，同级结点不能相连，每个结点有且只有一个前驱结点，一个结点可以再连接多个结点，也即一对多的结构。

1. 概念术语

1. 度：一个结点连接的结点数（子树）称为该结点的度，一个树的度指的是树内所有结点的度的最大值。度为0的结点称为叶结点（Leaf）或者终端结点，度非零的结点称为非终端结点或者分支结点或者内部结点。

2. 结点关系：结点的子树称为结点的孩子（child），对应的，该结点称为子树的双亲（Parent），同一结点的两个孩子互称为兄弟（Sibling），结点的祖先是从根结点开始到该结点经过的所有结点。树有分层结构，根结点为第一层，双亲在同一层的结点称为堂兄弟，树的最大层次称为树的深度或者高度。

3. 有序树：如果树中结点的子树从左往右是有次序、不能互换的，则称该树为有序树，否则称为无序树。

4. 森林：是n棵互不相交的树的集合。例如树中有某个结点有多棵子树，子树的集合即为森林。一个树把根结点去掉就成为了森林，给森林加上根结点就成为了一棵树

2. 结点的编号

由于遍历算法不同，树的结点编号也是不一样的，总体而言有按层编号、按子树编号： 按层编号：根结点为0，先从上到下，再从左往右（无论是否同一个双亲）
按子树编号：根结点为0，先遍历左子树，从左往右，从上到下，再遍历右边的子树。

在二叉树中，根据前序（根结点）、中序、后序，又对应了三种遍历和编号方法。

3. 树的存储结构

树的存储结构同样分为了链式存储和顺序存储，而由于树的结构比较复杂，应用场景不同，衍生出了不同角度的结点关系描述：双亲表示法、孩子表示法、双亲孩子表示法。结合起来如下：

1. 双亲表示法

引入顺序表的思想，使用顺序表来存储当前数据以及双亲的编号，根结点的双亲为-1。这种方法能使结点快速找到其双亲直至根结点，但是如果需要找到一个结点的孩子，只能遍历整个数组。

树的编号：按照先从上到下，再从左到右的规则进行编号。即A0、B1、E2、H3...

如果关心它的孩子，或者兄弟关系，可以引入孩子、兄弟的编号。

数据结构：

#define MAXSIZE 10
typedef int data_t;

typedef struct PTNode_t{  //一个结点的结构
    data_t data;  //结点数据
    int parent;   //双亲编号
    //optional:
    //int child;
    //int sibling;
}PTNode;

typedef struct {
    PTNode node[MAXSIZE];//树内结点最大空间（表长）
    int r;  //根结点编号
    int n;  //现有的结点数目
}PTree;

2. 孩子表示法

树的编号：按照先从左到右，再从上到下的规则进行编号。即A0、B1、C2、D3...

引入链表的思想来存储树结构：在鱼C小甲鱼的数据结构中提出了两种方案： 方案一：根据树的度为链表开辟空间： 缺点是显而易见的，大量的链表空间被浪费。

方案二：根据子结点的数目开辟链表空间： 缺点是维护困难，而且初始化时不能使用同一化的语句进行空间开辟，需要对子树进行统计。

常用方案： 利用了孩子之间的关系，只有最左边的孩子直接与双亲联系，其他孩子分别由其左孩子索引，实际上像是引入了多个链表的结构，这种方案以少量的空间浪费（指针本身也浪费了空间）换取了高的可维护性。

3. 双亲孩子表示法

把前面两种方法综合起来，就得到了双亲孩子表达方法，这种结构便利结点快速索引到其双亲和孩子，而无需遍历整个树结构。

2、3两种数据结构可以描述为：

#define MAXSIZE 10
typedef int data_t
//首先需要孩子的链表结构:用于描述所有孩子的联系
typedef struct CNode{
    int child; //孩子结点的编号
    struct CNode *next; //指向右孩子的next指针
}*CLink;
//表头结构：用于存放所有结点数据、双亲编号（仅双亲孩子表示法）
typedef struct {
    //optional:
    //int parent;
    data_t data; //数据
    CLink *next; //用于双亲指向孩子链表
}PTable;
//树结构
typedef struct{
    PTable ptable[MAXSIZE] //链表，MAXSIZE代表最多能有几个链表数
    int r,n; //根结点、结点数

}PCTree;

注意，这里描述的是对树结构最优存储方法的介绍，这种顺序表+链表的方式是比较优的方案，而对于下面要介绍的二叉树结构，存储结构则要简明很多。

4. 二叉树的存储

二叉树是最常用的树结构，使用链式存储的方式，这是因为顺序存储的二叉树只适用于完全二叉树，当遇到非完全二叉树时要加入大量的虚结点，特别是遇到斜树这种结构，内存利用十分糟糕。所以常用的链式二叉树结构如下：

typedef int data_t;
typedef struct biNode_t{
    data_t data;
    struct biNode_t *lchild,*rchild;

}biNode,*biTree;

5. 链式二叉树的初始化

树的二叉树初始化通过递归的方式进行，退出循环的条件是有使用足够多的能构成完整二叉树的元素和“#”（代表空）

bitree * tree_create(){
    data_t ch;  //data_t暂定是char型
    //printf("Please Input char:");
    scanf("%c",&ch);  //输入二叉树数据元素
    if(ch=='#'){    //#代表该位置为空
        return NULL;
    }
    bitree *r =(bitree *)malloc(sizeof(bitree)); //不是空则开辟结点空间
    if(r==NULL){   
        printf("malloc failed!\n");
        return NULL;
    }
    r->data=ch; //填入数据元素	
    r->lchild=tree_create();//递归创建左结点
    r->rchild=tree_create(); //递归创建右结点
     return r; //返回创建的结点元素
}

最简单的树结构是A##（只有根结点A），初始化图中的二叉树数据为：AB#CD###E#FGH##K###，单次输入，scanf会自动以char型分割字符。注意这种初始化方法的初始化顺序，是前序的初始化方法，从根结点到左结点、右结点。

6. 二叉树的遍历

二叉树的遍历一般有递归和栈两种方法，下面记录的是递归访问的方法。 前序遍历（根左右）：ABCDEFGHK
中序遍历（左根右）：BDCAEHGKF
后序遍历（左右根）：DCBHKGFEA
层序遍历：ABECFDGHK

1. 二叉树的前序遍历(先序遍历)

遍历顺序：根结点、左结点、右结点。代码是统一的，先序、中序、后序的不同在于递归和打印顺序的不同：

void preorder(bitree *r){
    if(r==NULL){
        return;  //遇到空结点返回不打印即可
    }
    printf("%c\t",r->data);//打印根结点
    preorder(r->lchild); //递归左孩子
    preorder(r->rchild); //递归右孩子
}

2. 二叉树的中序遍历

遍历顺序：左结点、根结点、右节点。

void inorder(bitree *r){
    if(r==NULL){
        return;  
    }
    inorder(r->lchild);//递归左孩子
    printf("%c\t",r->data);//打印根结点
    inorder(r->rchild);//递归右孩子
}

3. 二叉树的后序遍历

遍历顺序：左结点、右结点、根结点。

void postorder(bitree *r){
    if(r==NULL){
        return;
    }
    postorder(r->lchild);//递归左孩子
    postorder(r->rchild);//递归右孩子
    printf("%c\t",r->data);//打印根结点
}

4. 二叉树的层序遍历

从上到下逐层输出数据元素，选择的方案是队列的辅助形式。其中队列数据元素的数据类型为bitree*:思路，首先是根结点入队，打印元素，如果队列不为空，开始循环：队列出队（根结点）记为r，看它的左右孩子是否为NULL，如果不是则入队并打印，下一次循环的时候出队继续查看其左右孩子，这种FIFO的遍历就构成了层序遍历。

void layerorder(bitree *r){
    if(r==NULL){
        return;
    }
    linkqueue *q=queue_create();
    if(q==NULL){
        return;
    }
    En_queue(q,r);  //初始时根结点入队
    printf("%c\t",r->data); //打印根结点
    while(queue_isempty(q)==0){ //队列不为空（不断有左右孩子结点入队直至叶结点）
        r=De_queue(q); //出队作为r
        if(r->lchild!=NULL){ //查看其左孩子
            printf("%c\t",r->lchild->data);
            En_queue(q,r->lchild);
        }
        if(r->rchild!=NULL){  //查看右节点
            printf("%c\t",r->rchild->data);
            En_queue(q,r->rchild);
        }
    }
}

7. 线索二叉树

线索二叉树是为了优化传统二叉树效率引入的一种数据结构，其中最常用的为中序线索二叉树：中序遍历适应了二叉搜索树的排序要求，对二叉搜索树而言，左子树存放了比根结点小的元素，右子树存放了比根结点大的元素，使用中序遍历恰巧直观获取树的元素排序；此外中序遍历左、根、右顺序，体现了树结构关于根结点的对称性，任意给定一个结点，其前驱是左子树最右边的结点，其后继是其右子树最左边的结点。

线索二叉树优化了寻找某个结点的前驱、后继的效率，利用结点空余的左右孩子空间，用于记录结点的前驱和后继元素，利用了传统二叉树的空闲空间。为了区分结点连接的是左右孩子还是前驱后继，线索二叉树的结构引入了标志位ltag和rtag作为区别，当标志位置0时认为连接的是左右孩子，为1则认为连接的前驱后继元素，数据结构：

typedef char data_t;
typedef struct threadNode_t{
    data_t data;       //二叉树数据
    struct threadNode_t* lchild,*rchild; //左右孩子
    int rtag,ltag; //标志位，1表示连接线索，0表示连接普通子树结点
    
}threadNode,*threadTree;

extern threadTree pre;//全局变量，用于记录前驱和后继

定义了

1. 中序线索二叉树的初始化

初始化方法和普通二叉树一致，只是加入了两个标志位的初始化。

threadTree threadTree_create(){
    threadTree r;
    data_t ch;
    scanf("%c",&ch);
    if(ch=='#'){
        return NULL;
    }
    r=(threadTree)malloc(sizeof(threadNode));
    if(r==NULL){
        printf("malloc failed!\n");
        return NULL;
    }
    r->data=ch;
    r->lchild=threadTree_create();
    r->ltag=0;
    r->rchild=threadTree_create();
    r->rtag=0;
    return r;
}

2.线索二叉树的中序线索化

该步骤用于将二叉树线索化，也即利用空余的左右子树来记录结点的前驱后继线索。采用了最为常见的中序方法，首先递归到最左结点，

threadTree pre=NULL; //初始前驱指针，记为NULL

void inthreading(threadTree r){//中序线索化二叉树
    if(r==NULL){
        return;
    }
    inthreading(r->lchild);//递归左子树
    if(r->lchild==NULL){  //左子树为NULL
        r->lchild=pre;   //没有左子树lchild，把前驱记为lchild
        r->ltag=1;      //标志位置为1
    }
    if(pre&&pre->rchild==NULL){  //pre的右孩子为空
        pre->rchild=r;  //r指向的是中序中pre的下一个结点，即pre的后继
        pre->rtag=1;   
    }
    pre=r;  //pre为空（第一次的时候），或者左右孩子都存在的时候，直接移动pre
    inthreading(r->rchild);//递归右子树
}

3. 线索二叉树的中序遍历

用于引入了线索，可以无需使用递归或栈结构遍历二叉树，结合使用线索和孩子即可完成遍历。

void inorder(threadTree r){ //中序线索遍历二叉树
    if(r==NULL){
        return;
    }
    while(r!=NULL){
        while(r->ltag==0){ //碰到了有左子树的结点
            r=r->lchild; //遍历到左结点，因为打印根结点前先打印左节点
        }
        printf("%c",r->data);//打印左子树的结点
        while(r->rtag==1&&r->rchild!=NULL){ //线索寻值：右孩子存在且为线索
            r=r->rchild;   //移动到下一个线索（也就是中序的下一个结果）
            printf("%c",r->data);//直接打印
        }
        r=r->rchild;//右子树为元素，直接移动
    }
}

4. 线索二叉树的元素查找

实现元素查找是为了验证前驱和后继结点查找的代码，思路和遍历一样，只不过将输出打印变成了字符串的比较。

threadTree find_Node(threadTree r,data_t value){
    if(r==NULL){
        return NULL;
    }
    while(r!=NULL){
        while(r->ltag==0){ //中序遍历，从左结点开始
            r=r->lchild;
        }
        if(r->data==value){  //比较数据
        //	printf("Found!\n!");
            return r;
        }
        while(r->rtag==1&&r->rchild!=NULL){  //右孩子是线索，直接比较
            r=r->rchild;
            if(r->data==value){
            //	printf("Found!\n!");
                return r;
            }
        }
        r=r->rchild; //右孩子是元素，直接移位（然后重新遍历到左结点开始）
    }
    return NULL;
}

5. 线索二叉树的查找结点前驱、后继元素

线索二叉树的前驱分为两种情况：其一，标志位ltag为线索，lchild直接就是前驱，返回即可；其二，标志位ltag是元素，即有子树，结点的前驱就是左子树lchild的最右的结点，因此只需要不断遍历左子树的右子树的右子树......直到遍历到rtag=1的情况(代表原来就没有了子树)即可。

 threadTree find_Predecessor(threadTree p){
    if(p->ltag==1){ //前驱是线索，直接返回
        return p->lchild; 
    }
    else{ 
        threadTree pl=p->lchild; //保存左子树
        if(pl!=NULL){  //左子树不是空树（排除故障）
            while(pl->rtag==0){//直到最右子树的最右结点
                pl=pl->rchild; //遍历所有的右子树
            }
            return pl;//已到达最右结点返回
        }
    return NULL;//没有前驱,故障、第一元素
    }

}

线索二叉树的后继是同理的：情况一是rtag为线索，rchild就是后继；情况二标志位rtag是元素，即rchild为子树，结点的后继是右子树rchild最左边的结点，因此遍历右子树的左子树的左子树...直到ltag=1;

threadTree find_Successor(threadTree p){
    if(p->rtag==1){ //后继为线索，直接就是rchild
        return p->rchild;
    }
    else{
        threadTree pr=p->rchild;
        if(pr->lchild!=NULL){
            while(pr->ltag==0){ //后继在右子树的最左结点
                pr=pr->lchild;
            }
            return pr;
        }
    return NULL;//没有后继，故障、最后一位元素
    }                                                   
}

8. 赫夫曼树（Huffman）

赫夫曼编码是一种重要的不等长编码，能够根据某个信息出现的频率进行编码，高频信息使用短码，低频信息使用长码，大大节省了编码空间，提高编码效率。此外，赫夫曼编码是一种前缀码，也即没有码字是其他任何码字的前缀，在数据接收解码时就不会发生多义性。

赫夫曼编码规则是基于赫夫曼树（也称最优二叉树）来进行的，每个元素都带有一个权值（代表某段数据该元素出现频率高低）。假设元素任意排列构成二叉树。从根结点出发到某个结点的经过的路径数称为该结点的路径长度，所有结点的路径长度乘上结点权值之和称为该树的带权路径长度（WPL，Weighted Path Length），赫夫曼树是使得树的带权路径长度最小的树，赫夫曼树并不唯一（例如大小左右摆放顺序不同就是新的二叉树，也是赫夫曼树），找到赫夫曼树的方法是：

1. 首先把每个元素按权值大小排序，取出权值最小的两个元素作为最底层的叶子结点；

2. 将元素权值求和，得到两个结点的根结点，如果权值和大于第三个元素的权值，那么第三个元素放在该根结点的左侧，反之放在右侧，根结点和第三个元素结点求和生成新的根结点，再和第四个元素结点比较一次类推，最后加上一个根结点，就构成了一个赫夫曼树。

3. 定义二进制不等长编码，从根结点出发，往左子树走记为0，往右子树走记为1，走到结点得到的编码就是赫夫曼编码。

这种方法得到的赫夫曼树的数据结点都是叶子节点，这也是哈夫曼编码拥有前缀码的特性的原因。赫夫曼编码是很多压缩算法的基石，能带来20%-90%的压缩率。

9. 二叉排序树（BST）

二叉排序树又称二叉查找树（Binary Search Tree,BST）,任一个结点大小关系都满足左孩子<根结点<右孩子，因此如果结合中序遍历就能得到一个增序的序列。且注意：二叉排序树是不允许重复元素存在的。

1. 二叉排序树的插入（初始化）

每次插入都涉及对树进行操作，需要改变存储结构，C语言要么采用双重指针的方式作为参数传递，要么采取返回值的方式影响实参，而如果C++中则简便，直接使用引用即可。这里采用的是C语言双重指针递归实现的方式，根据插入的值递归到要插入的位置，小于某个结点就去左子树，大于就去右子树，开辟空间，填入数据，每次插入的结点一定是一个叶子结点，因此设置lchild、rchild均是NULL；

int Bst_insert(BstTree**T,data_t value){
    if((*T)==NULL){
        (*T)=(BstTree*)malloc(sizeof(BstTree));
        if((*T)==NULL){
            printf("malloc failed!\n");
            return -1;
        }
        (*T)->data=value;
        (*T)->lchild=NULL;
        (*T)->rchild=NULL;
        return 0;
    }
    else if((*T)->data==value){
        printf("Not Allow Same Elem!\n");
        return -1;
    }
    else if((*T)->data>value){
        return Bst_insert(&((*T)->lchild),value);
    }
    else{
        return Bst_insert(&((*T)->rchild),value);
    }
}

2. 二叉排序树的查找

二叉排序树查找原理很简单，从根结点出发，要查找元素大于根结点就去右子树找，小于就去左子树找，遍历到某个点却为NULL就说明没有这个元素。实现方式分为迭代和递归两种，且迭代的性能较为优异。这里均给出了两种实现：

//二叉排序树查找:递归法
BstTree* Bst_search_recur(BstTree* T,data_t value){
    if(T==NULL){
        printf("NULL!\n");
        return NULL;
    }
    else if(T->data==value){
        printf("Found:%d\n",T->data);
        return T;
    }
    else if(T->data>value){
        return Bst_search_recur(T->lchild,value);
    }
    else{
        return Bst_search_recur(T->rchild,value);
    }

}

//二叉排序树查找：迭代法
BstTree* Bst_search_iter(BstTree *T,data_t value){
    if(T==NULL){
        printf("No Tree!\n");
        return NULL;
    }
    while(T!=NULL){
        if(T->data==value){
            printf("Found:%d\n",T->data);
            return T;
        }
        if(T->data>value){
            T=T->lchild;
        }
        else{
            T=T->rchild;
        }	
    }
    printf("Not Found!\n");
    return NULL;
}

查找长度：二叉排序树的查找成功和失败平均查找长度最优是,最差是O(n)，因此如果需要尽量提高查找效率，因该尝试构造分布均匀的树而不是斜树，这就是下节需要介绍的平衡二叉树的应用意义。

3. 二叉排序树的删除

要删除结点而不破坏二叉排序树的结构特性，需要知道删除的结点可以分为四类情况： 1. 删除的结点是叶子结点，直接删除即可。
2. 删除的结点没有左子树：直接让右孩子结点代替删除结点即可。
3. 删除的结点没有右子树，直接让左孩子结点代替删除结点即可。 4. 删除的结点既有左子树又有右子树，一种策略是让左子树的最右孩子（左子树最大的）代替删除节点，并且让其左孩子（如果有的话）代替原来最右孩子位置；另外一种也即让右子树的最左孩子（右子树最小的）代替删除结点，并且让其右孩子（如果有的话）代替原理最左孩子的位置。

这里采用了右子树最小元素代替删除结点的写法，使用递归实现删除。findrch_min用于调用查找右子树最小结点，注意不能像链表操作一样写在主函数，如果需要在同一个函数中则需要使用parent、child两个指针交替访问到叶子结点，较为麻烦。

//找到右子树的最小元素结点并且返回
BstTree* findrch_min(BstTree* T){
    while(T->lchild){
        T=T->lchild;
    }
    return T;
}

void Bst_deleteTNode(BstTree**T,data_t value){
    //递归到要删除结点的左子树或者右子树
    if((*T)->data>value){    
        Bst_deleteTNode(&((*T)->lchild),value);
    }
    else if((*T)->data<value){
        Bst_deleteTNode(&((*T)->rchild),value);
    }
    //else此时*T指向的就是要删除的结点
    else{
        if((*T)->lchild==NULL){  //情况2，没有左子树
            BstTree *temp=(*T)->rchild;
            free(*T);
            *T=temp;
        }	
        else if((*T)->rchild==NULL){ //情况3，没有右子树
            BstTree *temp=(*T)->lchild;
            free(*T);
            *T=temp;
        }	
        else{
            BstTree *temp=findrch_min((*T)->rchild); //找到右子树的最小元素结点
            (*T)->data=temp->data;  //最小元素值代替要删除的结点
            Bst_deleteTNode(&((*T)->rchild),(*T)->data); //在右子树执行删除最小结点操作
        }
    }
}

11. 平衡二叉树（AVL树）

平衡二叉树指的是树上任一点的左子树和右子树的高度之差不超过1，定义结点:

平衡因子等于左子树高-右子树高，平衡二叉树的平衡因子取值只可能是1、0和-1。

1. 最小不平衡子树

计算每个结点的平衡因子，以-2或者2为根结点的子树就是最小不平衡子树。

2. 平衡二叉树的插入调整思想

平衡二叉树实际上就是基于二叉排序树插入或者删除元素后，将因为插入、删除结点带来的“不平衡”现象给去除，这要通过调整结点的位置实现，而且调整的结点只是最小不平衡树的结点，假设我们插入了某个结点导致出现了某个最小不平衡子树，调整情况分为以下四类：
1. LL类：向左孩子的左子树插入结点导致不平衡； 解决方法：插入后将左孩子右旋，左孩子的右孩子重新去排序；

2. RR类：向右孩子的右子树插入结点导致不平衡； 解决方法：右孩子左旋，右孩子的左孩子重新去排序；

3. LR类：向左孩子的右子树插入结点导致不平衡； 解决方法：左孩子的右孩子（C）先左旋，CL去与左孩子（B）排序，然后C右旋为最小不平衡树根结点，CR去和A排序。

4. RL类：向右孩子的左子树插入结点导致不平衡； 解决方法：右孩子的左孩子（C）先右旋，CR去和右孩子（B）排序，然后C左旋为最小不平衡树根结点，CL去和A排序。

3. 平衡二叉树的删除调整思想

#include <iostream>
using namespace std;

using DataType = int;

typedef struct AvlNode_t{
    DataType data;
    int height;
    struct AvlNode_t* lchild;
    struct AvlNode_t* rchild;
} *AvlNode;

int getTreeHeight(AvlNode node){
    if(node)
        return node->height;
    return 0;
}

void updateHeight(AvlNode node){
    if(node == nullptr)
        return;
    else
        node->height = max(getTreeHeight(node->lchild), getTreeHeight(node->rchild)) + 1 ;
}

//左孩子的左子树插入结点，整树右旋即可
void llRotate(AvlNode* a){
    AvlNode b = (*a)->lchild;
    (*a)->lchild = b->rchild;
    b->rchild = *a;
    updateHeight(*a);
    updateHeight(b);
    *a = b;
}

//右孩子的右子树插入结点，整树左旋即可
void rrRotate(AvlNode* a){
    AvlNode b = (*a)->rchild;
    (*a)->rchild = b->lchild;
    b->lchild = (*a);
    updateHeight((*a));
    updateHeight(b);
    (*a) = b;
}

//左孩子的右子树插入结点，右子树左旋，然后整树右旋
void lrRotate(AvlNode* a){
    AvlNode b = (*a)->lchild;
    AvlNode c = b->rchild;
    
    (*a)->lchild = c->rchild;
    b->rchild = c->lchild;
    c->lchild = b;
    c->rchild = (*a);

    updateHeight((*a));
    updateHeight(b);
    updateHeight(c);

    (*a) = c;
}

//右孩子的左子树插入结点,左子树右旋，然后整树左旋
void rlRotate(AvlNode* a){
    AvlNode b = (*a)->rchild;
    AvlNode c = b->lchild;

    (*a)->rchild = c->lchild; 
    b->lchild = c->rchild;
    c->lchild = (*a);
    c->rchild = b;

    updateHeight(*a);
    updateHeight(b);
    updateHeight(c);
    *a = c;
}

bool avlInsert(AvlNode* root, DataType data){
    if((*root)==nullptr){
        (*root) = new AvlNode_t;
        (*root)->data = data;
        (*root)->height = 1;
        (*root)->lchild = (*root)->rchild = nullptr;
        return true;    
    }
    else if((*root)->data == data){
        return true;
    }
    else if(data < (*root)->data) {
        if(avlInsert(&((*root)->lchild), data) == false)
            return false;
        updateHeight(*root);
        if(getTreeHeight((*root)->lchild) - getTreeHeight((*root)->rchild) == 2){
            if(getTreeHeight((*root)->lchild->lchild) > getTreeHeight((*root)->lchild->rchild)){
                llRotate(root);
            }
            else{
                lrRotate(root);
            }
        }
        return true;
    }else{
        if(avlInsert(&((*root)->rchild), data) == false)
            return false;
        updateHeight((*root));
        if(getTreeHeight((*root)->lchild) - getTreeHeight((*root)->rchild) == -2){
            if(getTreeHeight((*root)->rchild->lchild) > getTreeHeight((*root)->rchild->rchild)){
                rlRotate(root);
            }
            else{
                rrRotate(root);
            }
        }
        return true;
    }
}

void inorder(AvlNode r){
    if(r==nullptr)
        return;  
    inorder(r->lchild);//递归左孩子
    printf("%d\t",r->data);//打印根结点
    inorder(r->rchild);//递归右孩子
}

int main(){

    AvlNode root = nullptr;
    avlInsert(&root, 1);
    avlInsert(&root, 5);
    avlInsert(&root, 3);
    avlInsert(&root, 4);
    avlInsert(&root, 2);
    avlInsert(&root, 6);
    if(root == nullptr){
        cout << "111" << endl;
    }
    inorder(root);

    cout << "done" << endl;
    return 0;
}

12. 红黑树

13. B树

14. B+树

15. 并查集

并查集常常被用于识别某个结点、或者某个结点的集合是否属于另一个集合，在图论算法中比较有用。关于判断一个点是否属于某个集合，容易想到的是集合的数据结构，例如set、map等，但是这些数据结构无一例外都需要遍历全部元素来查找集合的某个元素，并查集的思想就是使用一个一维数组，就能够记录点集合的关系。

这个思想的基本原理来自树的结构表示，即双亲表示法；在树的双亲表示结构中，每个结点使用数组记录父节点的编号（见2.3）；在并查集，如何表示A、B、C同属一个集合呢？实际上就是在一维数组中记录Array[A] = B,Array[B]=C，这种操作就称为“并”；如何判断B、C是否同属一个集合呢？这里只需要一个伪函数find,find(B)/find(C)，它们会递归地查找其父结点，如果结点都是A，说明B、C同属一个集合。可见最后并完，同一个集合的元素都有一个共同的“根”。

并查集的并和查操作都能进行优化，为了防止混淆最后仅给出一种代码，对并操作优化仅描述思路，对查操作优化会落实到最后代码。

并操作的优化：

并操作主要是将某个结点或者结点的集合加入另一个集合，最坏的情况是将一个n-1长度的结点加入到一个新结点，新结点作为根，遍历n-1长度的结点需要O(n)复杂度；优化思路只有一点：确保总是将小树融合进大树，例如一个树高为4的树，另一个集合是树高为3的树，将小树加入大树，最大树高不会改变，仍然为4，而不是原来的7，这种情况下并操作，查找的时间复杂度是logn的数量级。但这种方法需要额外引入一个秩，用于记录和判断树高，带来额外的开销。

查操作的优化：路径压缩

这个就比较重要了，在并查集中总是需要判断一个元素和另外一个元素是否同属于一个集合，导致总是要遍历它们的根节点，因此在查找操作时，除了查找其根结点，我们还会利用递归，将该节点直接接到根结点上，这样下一次查找时，只需要一次就能找到其根结点。而且代码上仅仅多了一个赋值操作，这种策略的平均时间复杂度是一个反阿克曼函数，即O(α(n))，其中一般有α(n)<=4，比logn增长更慢，几乎是一个常数级的复杂度。

具体实现：采用路径压缩的并查集初始化、并查、判断算法：

void init(int unifind[]){
    for(int i=0; i<size; ++i){
        unifind[i] = i;  //自己指向自己，代表一开始都是独立集合
    }
}

//查操作：查找u在集合的根
int find(int u){
    if(u==unifind[u])  // 根就是自己
        return u;
    else return unifind[u] = find(unifind[u]); //unifind[u]是u的父节点（双亲表示），找父亲，并且插入到父亲
    //如果没有路径压缩为：
    //else return find(unifind[u])
}

//并操作，u、v本身可以是孤立元素，也可以是来自不同集合的元素
int union(int u,int v){
    u = find(u);  //找根
    v = find(v); //找根
    if(u==v)  //同一个根，无需合并
        return;
    unifind[u] = v; //大小树不定
}

//判断两个元素是否同一个集合
bool isSame(){
    u = find(u);  //找根
    v = find(v); //找根
    return u==v;
}

图

图结构的数据元素存放的点称为顶点（Vertex），和树结点、线性表元素等类似。一般图结构的定义是有穷非空，即一个图中顶点数量是有限的且不为0。不同的顶点相互链接，就是图结构，是一种多对多的结构。

1. 图论相关术语（非严格定义，仅作理解）：

1. 无向边：两个顶点Vi、Vj的链接是没有方向的，使用无序偶（Vi，Vj）表示；全部无向边构成的图称为无向图。

2. 有向边（弧）：两个顶点Vi和Vj的链接是有方向的，使用有序偶<Vi,Vj>表示,表示从Vi指向Vj，Vi是弧尾，Vj是弧头。有向边构成的图称为有向图。

3. 简单图：不存在顶点自身到自身的边，两个顶点有且只有一条平行边（针对无向图就是一条边而言，有向图两条边有时候也认为是简单图），称为简单图，以下所有记录都是基于简单图结构。

4. 无向完全图：在无向图中，任意两个顶点都要链接关系，称为无向完全图，N个顶点的无向完全图有N*(N-1)/2条边。

5. 有向完全图：任意两个顶点都有两个连接关系，方向相反，N个顶点的有向完全图有N*(N-1)条边。

6. 稀疏图和稠密图：是模糊的概念，用于描述图结构的边关系是否复杂繁多，顶点数是N，指标是NlogN（不绝对）。

7. 网（带权图）：链接关系是带权值的图称为网。

8. 邻接点（Adjacent）：两个顶点的边是属于该图结构的边，那么称两个顶点互为邻接点。

9. 顶点的度（Degree）：在无向图中，和顶点关联的边数就是度（记为TD）。在无向图中，以该顶点为弧头的边数称为入度（ID），以该顶点为弧尾的称为出度（OD），二者之和为度（TD）。

10. 简单路径：所有顶点只经过一次的路径称为简单路径。

11. 连通图：在无向图中，任意两个顶点都是可达的称为连通图。如果需要N个顶点，需要保证它为连通图那么至少需要N-1条边；如果需要保证它为非连通图，最多只能有条边。

12. 强连通图：在有向图中，如果两个顶点例如从A到B、从B到A都是有路径的（不一定是邻接点），那么称两个顶点是强连通的。如果任意两个顶点都是强连通的，那么称这个有向图是强连通图。N个结点具有的强连通图最少边数是N条（刚好形成一个环）

13. 子图和生成子图：在图中保留部分顶点和边，称为原来图的子图；注意边点的关系要对应，不能只保留边而去除顶点（这样根本不符合图结构的要求，也称不上子图。）如果保留了原来的图的所有顶点，但去除了某些边的关系，则称该新图为原来图的生成子图。

14. 连通分量：无向图中的极大联通子图称为连通分量。

15. 强连通分量：有向图中极大连通子图称为强连通分量。

16. 生成树：首先保留图的全部顶点，然后开始保留边，要求是保留尽量少的边使得图是连通的（也就是极小连通子图），顶点数为N，生成树的边数就是N-1，生成树去掉任一条边都是非连通的，加上任一条边都是形成回路，生成树可以不唯一，如：

2. 图的存储结构

1. 邻接矩阵

使用到了两个数组，一维顶点数组用于存放顶点元素的信息，二维边关系数组用于存放边的信息，如果边关系存在（是链接的），那么记为1，否则记为0。

不难理解，简单图的对角元素必然都是0，无向图的邻接矩阵是对称矩阵（这也意味着有一半空间是重复无意义的）。而有向图则一般是非对称矩阵。

此外，邻接矩阵还可以用于描述一个网结构，二维数组填入具体权值，以无穷代表不连接关系。

邻接矩阵的计算还可以蕴藏某些意义，例如邻接矩阵自身相乘，得到，i行j列某个元素=3代表i元素到j元素长度为2（因为二次方）的路径有3条。

邻接矩阵的特点：空间复杂度高（N^2，N代表顶点数），如果是稀疏图的存储将造成大量资源的浪费。

2. 邻接表

我们已经使用数组+链表的方式（双亲孩子表示法）表达过树状的结构，图中也是类似的，这种表达方式称为邻接表。使用顺序表存放每个元素的数据和下一个元素指针，使用链表来存储顶点链接的所有元素下标。如果需要网的结构，则需要在链表结点中定义新的数据空间用于存放权值。

对邻接表而言，无向图中同一个连接关系会在两个链表中重复出现，因此提高了不必要的复杂度。在有向图中，出度的计算是相对简单的，只需要遍历一个顶点的链表，而入度的计算相对困难，因为需要遍历所有顶点的链表才能找到相关顶点的入度（或者不同的设计下入度容易计算而出度难计算），而无向图则不存在这个问题。

邻接矩阵和邻接表比较

3. 十字链表

十字链表是专门为有向图的存储设计的方案，其目的是使得无需遍历整个图而获得某个顶点的出度以及入度。 十字链表的存储可以看成将普通的邻接表的弧结点、顶点结点的顶点下标、顶点指针进行了一分为二的区分:

1. 顶点结点原来的first指针指向出去的边，现在变成firstin指向入来的边以及firstout指向出去的边。

2. 弧结点Vertex原来是记录当前顶点编号，现在分为tailvex和headvex分别记录弧尾（该弧发出的位置）和弧头（当前弧指向的顶点）结点下标信息，原来的next指向的出去边的下一个的结点，现在分为hlink和tlink分别指向产生入边的结点和出边指向的结点。也即顺着hlink找能找到指向该顶点所有顶点信息，顺着tlink找能找到该顶点指向的所有顶点信息。

4. 邻接多重表

邻接多重表是专门为无向图存储设计的方案，无向图的问题在于同一段关系却出现在不同的链表连接中，当删除顶点、删除边时要进行双重的操作，产生复杂度，邻接多重表就是需要解决这个问题。

邻接多重表的结构和十字链表是类似的：

1. 顶点结点的定义和邻接表是一致的。

2. 边结点的Vertex一分为二，原来是用于当前顶点的编号，现在分为i、j记录边的两个顶点信息，原来的next指向的是下一个结点，现在分为iLink和Jlink分别指向i顶点的下一个编号和j顶点的下一个顶点编号，可以看成这个边结点被一点两用了，一个为i顶点服务，一个为j顶点服务，删除顶点时就能够只删除这个点，通过ilink和jlink改变指向即可。

3. 图的相关操作（基于无向图）

代码图示例

1. 邻接矩阵的结构以及初始化

邻接矩阵结构由两个矩阵构成，其一是一个一维数组vex用于存放顶点字符数据；另一个是二维的边关系数组用于描述两个点是否链接或者存放权值（没有使用）。顶点数目是便于进行循环的操作。

typedef char data_t; //顶点元素数据类型
typedef enum{true=1,false=0} bool; //定义C语言的bool

typedef struct {
    data_t vex[MAXSIZE]; //记录顶点元素
    int arc[MAXSIZE][MAXSIZE];//二维数组记录边的连接，1为连接，0为不连接
    int vexnum;  //顶点数目
    int arcnum; //边数

}AdjMatrix,*MGraph;

邻接矩阵的初始化很简单，只需要创建为数组填写初值即可。此外填入了如上图所示的图结构，使用了两个函数，一个是cin函数用于给用户输入来填写，提高创建的灵活性。一个是按照上图进行矩阵初始化，方便测试。

MGraph graph_create(){
    MGraph m=(MGraph)malloc(sizeof(AdjMatrix));
    if(m==NULL){
        printf("mailed failed");
        return NULL;
    }
    memset(m,0,sizeof(AdjMatrix));
    Mytest_graph(m);
    //cin_graph(m);
    return m;
}


//自行输入图
void cin_graph(MGraph m){
    int vex_num,arc_num;
    printf("Please input Vertex and Arch Num:");
    scanf("%d %d",&vex_num,&arc_num);
    m->vexnum=vex_num;
    m->arcnum=arc_num;
    printf("%d %d",vex_num,arc_num);
    data_t ch;
    for(int i=1;i<=vex_num;i++){
        printf("Please input No.%d VexElem:",i);
        scanf(" %c",&ch);
        m->vex[i-1]=ch;//顶点
    }
    printf("Input the arc if they are connect:(-1 to stop)");
    int temp1,temp2=0;
    for(int i=0;i<arc_num;i++){
        scanf("%d %d",&temp1,&temp2);
        if(temp1==-1||temp2==-1||temp1>=vex_num||temp2>=vex_num)
            break;
        m->arc[temp1][temp2]=1;
        m->arc[temp2][temp1]=1;	
    }
    puts("");
    printf("Create OK!");
}
//用于测试的图,图结构参考Eden博客
void Mytest_graph(MGraph m){
    if(m==NULL){
        printf("test create  NULL!\n");
        return;
    }
    m->vexnum=8;
    m->arcnum=10;
    data_t input[8]={'A','B','C','D','E','F','G','H'};
    for(int i=0;i<8;i++){
        m->vex[i]=input[i];	
    }
    m->arc[0][4]=1;
    m->arc[0][1]=1;
    m->arc[1][5]=1;
    m->arc[2][5]=1;
    m->arc[2][6]=1;
    m->arc[2][3]=1;
    m->arc[3][6]=1;
    m->arc[3][7]=1;
    m->arc[6][7]=1;
    m->arc[5][6]=1;
    for(int i=0;i<m->vexnum;i++){
        for(int j=0;j<m->vexnum;j++){
            m->arc[j][i]=m->arc[i][j];
        }	
    }
}              	

2. 邻接矩阵的深度优先遍历（DFS）

图的深度优先遍历类似于树结构的先序遍历：在先序遍历中，需要遍历到左子树的最左结点，再开始遍历。在上图中，假设我们从结点B开始进行DFS，原则是下标小的先遍历（因为循环是从小下标开始的），一条路走到黑，那么开始的顺序是BAE，E无路可走时，会逐级回退（检查但不输出）到B，进入FCDGH，因此顺序是BAEFCDGH。代码解读：深度优先首先对传入的参数顶点进行遍历，寻找该顶点相连的其他顶点（下标小的开始），然后递归到下一个顶点，继续寻找该点下标小的连接点进行遍历，等到走到最后一个结点，回头再走上一个顶点下标第二小的，以此类推。

void graph_DFS(MGraph m,int start_vex){
    if(m==NULL){
        printf("DFS NULL\n");
        return;
    }
    bool DFS_visited[MAXSIZE]={false}; //用于记录走过的顶点，初始化为false，走过为true
    printf("%c",m->vex[start_vex]);//                                          
    DFS_visited[start_vex]=true;
    for(int i=0;i<m->vexnum;i++){ //每到一个顶点就从0开始检查
        if(DFS_visited[i]==false&&m->arc[start_vex][i]==1) //某一列有连接关系，顶点还没有被遍历的
            graph_DFS(m,i);     //递归到该顶点
    }
}

3. 邻接矩阵的广度优先遍历（BFS）

广度优先遍历是类似树结构的层序遍历，以起点开始，遍历完当前点的所有邻接点，再进行下一个点的遍历。队列结构适合用于存储这些遍历过，但没有直接处理的顶点，例如B开始遍历，AF会相继入队，那么下一步就是走向A（A出队），在A点时E入队，因为队列是FIFO，F先入队会先考虑F，因此又走到F（F出队），CG入队、E出队、C出队，D入队、G出队，D出队，H入队出队，因此顺序是BAFECGDH。

void graph_BFS(MGraph m,int start_vex){
    if(m==NULL){
        return;
    }   
    bool BFS_visited[MAXSIZE]={false};
    printf("%c",m->vex[start_vex]);//打印第一个遍历顶点
    datatype r;
    linkqueue *q=queue_create();//初始化一个链式队列
    En_Queue(q,start_vex);  //入队
    BFS_visited[start_vex]=true;//标记遍历的第一个顶点
    while(q->front!=q->rear){ //队列不为空
        r=De_Queue(q);  //出队结点（开始处理）
        for(int i=0;i<m->vexnum;i++){ //遍历该顶点附近哪个顶点是有路径的
            if(m->arc[r][i]==1&&BFS_visited[i]==false){ //有路径、没走过
                printf("%c",m->vex[i]); //打印附近结点
                BFS_visited[i]=true; //标记                             
                En_Queue(q,i); //附近结点一一入队，（小下标先入先处理）
            }   
        }
    }
}

4. 图应用之一：最小生成树（最小代价树）

对于带权连通无向图而言，最小生成树（Minimum-Spanning-Tree，MST）就是从图结构尽可能去除权值大的边，最终留下的边使得边权值之和最小、而图结构是连通的树结构。如果图原本就是不连通的，只有生成森林。常用于描述最小生成树的问题是村庄修路问题，修一条路连通若干个村庄、而最大节省成本的路就是最小生成树的路径。最小生成树也不是唯一的，计算最小生成树一般有两个常见算法。

1. Prim算法（普里姆算法）

原理概述：这是一种点优先算法，不停地把权值小的边连接的点加入到树结构中。首先从任意某个顶点（P城）开始，挑选连接的权值最小的边（P城、学校），选择权值最小的边接入该树，即（P城矿场），下一个边（矿场、渔村），最后是P城、农场和农场、电站。

这就是一颗最小生成树，权值为15。

算法实现概述： 使用了两个数组记录顶点的连通情况、各顶点连通到生成树最小边权值（最小代价），上图是一开始的情况，每加入一个顶点，更新一次最小代价数组，根据最小代价数组最终把所有的顶点都纳入到生成树中。

2. Kruskal算法(克鲁斯卡尔算法)

原理概述：仍以上图为例，这是边优先的算法，挑选出边权值最小的边进行连通（前提是该两点是未连通的）。首先从图中挑选出权值最小的边（P城、学校），连通；继续挑选权值最小的边（矿场渔村），连通；继续挑选，（农场、电站），连通，继续挑选，（P城矿场、P城渔村二选一），连通；继续挑选，P城、渔村符合，但已经有连通了，不选；选P城、农场，结果同算法1一致。

算法实现概述： 开始时将边按权值大小进行排序，开始遍历第一条边，检查V0和V3是否同属一个集合（并查集的方法），不是则连通，以此类推V2和V5、V1和V4都可以连通，此时有三个集合，下一步V3和V2将连通，三个集合并成两个集合，因此V3和V5同属一个集合不再连通。最后连通V1和V3，并成一个集合，算法结束。

4. 图应用之二：最短路径规划

最短路径规划分为两个问题：单源最短路径和各顶点间最短路径。单源最短路径只考虑当前某个顶点到各个顶点间的最短路径，常用的有广度优先遍历（BFS）算法（仅无权图）、迪杰斯特拉（Dijkstra）算法（无权、带权图）；各顶点间最短路径考虑了每对顶点之间的最短路径，典型的是弗洛伊德（无权、带权图）算法。

本文至此基本更新完毕，以上各种介绍过、没介绍完的算法理论和具体问题可以继续参考数据结构算法题目（二）。