7.1 特性

7.1.1 什么是树

树(Tree)是(n>=0)个节点的有限集合T，它满足两个条件：

(1) 有且仅有一个特定的称为根（Root）的节点。

1. 其余的节点可以分为m（m≥0）个互不相交的有限集合T1、T2、……、Tm，其中每一个集合又是一棵树，并称为其根的子树（Subtree）。

树的特性：层次关系，一对多，每个节点最多有一个前驱，但是可以有多个后继(根节点无前驱，叶节点无后继)。

关于树的节点：和链表类似，树存储结构中也将存储的各个元素称为 "结点"。

7.1.2 关于树的一些术语

1. 度数：一个节点的子树的个数 （一个节点有几个孩子为该节点度数）     
2. 树度数：树中节点的最大度数
3. 叶节点或终端节点: 度数为零的节点       
4. 分支节点：度数不为零的节点 （A B C D E H）
5. 内部节点：除根节点以外的分支节点 （去掉根和叶子）
6. 节点层次:  根节点的层次为1，根节点子树的根为第2层，以此类推
7. 树的深度或高度: 树中所有节点层次的最大值

7.2 二叉树

最多只有俩孩子的树，并且分为左孩子和右孩子。

7.2.1 什么是二叉树

二叉树（Binary Tree）是n（n≥0）个节点的有限集合，它或者是空集（n＝0）， 或者是由一个根节点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。

二叉树与普通有序树不同，二叉树严格区分左孩子和右孩子，即使只有一个子节点也要区分左右。

7.2.2 二叉树性质（重点）

1. 二叉树第k（k>=1）层上的节点最多为2的k-1次幂 // 2^(k-1)
2. 深度为k（k>=1）的二叉树最多有2的k次幂-1个节点。//满二叉树的时候

 做多的节点数 2^k-1

1. 在任意一棵二叉树中，树叶的数目比度数为2的节点的数目多一。

设度数为0的节点数为n0，度数为1的节点数为n1以及度数为2的节点数为n2，则：

总节点数为各类节点之和: n = n0 + n1+ n2

总节点数为所有子节点数加一：n = n0*0 + n1*1 + n2*2 + 1

下面式子减上面式子得： 0 = -n0 + n2 +1 ==> n0 = n2 + 1

7.2.3 满二叉树和完全二叉树

满二叉树: 深度为k（k>=1）时节点数为2^k - 1(2的k次幂-1)

完全二叉树: 只有最下面两层有度数小于2的节点，且最下面一层的叶节点集中在最左边的若干位置上。(先挂树的左边向右, 从上向下挂)

7.2.4 二叉树的存储结构

     1.  二叉树的顺序存储结构

顺序存储结构 ：完全二叉树节点的编号方法是从上到下，从左到右，根节点为1号节点。设完全二叉树的节点数为n，某节点编号为i：

• 当i>1（不是根节点）时，有父节点，其父节点编号为i/2;
• 当2*i<=n时，有左孩子，其编号为2*i ,否则没有左孩子，本身是叶节点;
• 当2*i+1<=n时，有右孩子，其编号为2*i+1 ,否则没有右孩子；

有n个节点的完全二叉树可以用有n+1 个元素的数组进行顺序存储，节点号和数组下标一一对应，下标为零的元素不用。

利用以上特性，可以从下标获得节点的逻辑关系。不完全二叉树通过添加虚节点构成完全二叉树，然后用数组存储，

      2. 二叉树的遍历（重点）

前序： 根 ----> 左 -----> 右

中序:  左 ----> 根 -----> 右

后序:  左 ----> 右 -----> 根

例如：

前序: A B C D E F G H K

中序：B D C A E H G K F

后序：D C B H K G F E A

练习：

已知遍历结果如下，试画出对应的二叉树。

前序: A B C E H F I J D G K

中序：A H E C I F J B D K G

提示：用前序确定根节点，然后用中序找到根节点然后再找左右子。

7.4 层次遍历

层次遍历（队列思想）一定要懂

补充（面试可能会遇到）：

哈夫曼树 Huffman

哈夫曼树又称为最优树.

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

先明确以下概念：

1、路径和路径长度

在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

2、结点的权及带权路径长度

若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。

3、树的带权路径长度

树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。（

Weighted Path Length of Tree）

WPL=2*2+5*2+7*1=21

哈夫曼树的构造：

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：

(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；

(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

(3)从森林中删除选取的两棵树，并将新树加入森林；

(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

例如：对 2，3，4，8 这四个数进行构造：

第一步：

第二步：

第三步：

图

1.什么是图

     图结构常用来存储逻辑关系为“多对多”的数据。比如说，一个学生可以同时选择多门课程，而一门课程可以同时被多名学生选择，学生和课程之间的逻辑关系就是“多对多“。或者说之前学习的田径比赛的例子，一个人进行好几种比赛，而每个比赛也会被好几个人进行，那么田径比赛和人的关系就是多对多。

再举个例子，{V1, V2, V3, V4} 中各个元素之间具有的逻辑关系如下图所示：

2.图的基本概念

    1. 弧头和弧尾

      有向图中，无箭头一端的顶点通常被称为"初始点"或"弧尾"，箭头一端的顶点被称为"终端点"或"弧头"。

    2. 入度和出度

      对于有向图中的一个顶点 V 来说，箭头指向 V 的弧的数量为 V 的入度（InDegree，记为 ID(V)）；箭头远离 V 的弧的数量为 V 的出度（OutDegree，记为OD(V)）。拿图 2 中的顶点 V1来说，该顶点的入度为 1，出度为 2，该顶点的度为 3。

    3. (V1,V2) 和 <V1,V2> 的区别

      无向图中描述两顶点 V1 和 V2 之间的关系可以用 (V1, V2) 来表示；有向图中描述从 V1 到 V2 的"单向"关系可以用 <V1,V2> 来表示。

由于图存储结构中顶点之间的关系是用线来表示的，因此 (V1,V2) 还可以用来表示无向图中连接 V1 和 V2 的线，又称为边；同样，<V1,V2> 也可用来表示有向图中从 V1 到 V2 带方向的线，又称为弧。

    4.集合 VR

      并且，图中习惯用 VR 表示图中所有顶点之间关系的集合。例如，图 1 中无向图的集合 VR={(v1,v2),(v1,v4),(v1,v3),(v3,v4)}，图 2 中有向图的集合 VR={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}。

    5.路径和回路

      无论是无向图还是有向图，从一个顶点到另一顶点途经的所有顶点组成的序列（包含这两个顶点），称为一条路径。如果路径中第一个顶点和最后一个顶点相同，则此路径称为"回路"（或"环"）。

    在此基础上，若路径中各顶点都不重复，此路径被称为"简单路径"；若回路中的顶点互不重复，此回路被称为"简单回路"（或简单环）。拿上图来说，从 V1 存在一条路径还可以回到 V1，此路径为 {V1,V3,V4,V1}，这是一个回路（环），而且还是一个简单回路（简单环）。在有向图中，每条路径或回路都是有方向的。

6.权和网

    有些场景中，可能会为图中的每条边赋予一个实数表示一定的含义，这种与边（或弧）相匹配的实数被称为"权"，而带权的图通常称为网。例如，下图就是一个带权的网结构：

    7. 子图

      指的是由图中一部分顶点和边构成的图，称为原图的子图。

3.图的分类

    根据不同的特征，图又可细分为完全图，连通图、稀疏图和稠密图：

      完全图：若图中各个顶点都与除自身外的其他顶点有直接关系，这样的无向图称为完全图（如图 5a)）。同时，满足此条件的有向图则称为有向完全图（图 5b)）。

      上图完全图具有 n 个顶点的完全图，图中边的数量为 n(n-1)/2；而对于具有 n 个顶点的有向完全图，图中弧的数量为 n(n-1)。

      稀疏图和稠密图：这两种图是相对存在的，即如果图中具有很少的边（或弧），此图就称为"稀疏图"；反之，则称此图为"稠密图"。稀疏和稠密的判断条件是：e<nlogn，其中 e 表示图中边（或弧）的数量，n 表示图中顶点的数量。如果式子成立，则为稀疏图；反之为稠密图。

3.1 连通图

3.1.1 什么是连通图

      前面讲过，图中从一个顶点到达另一顶点，若存在至少一条路径，则称这两个顶点是连通着的。例如下图中，虽然 V1 和 V3 没有直接关联，但从 V1 到 V3 存在两条路径，分别是 V1-V2-V3 和 V1-V4-V3，因此称 V1 和 V3 之间是连通的。

    上图是顶点之间的连通状态示意图

      在无向图中，如果任意两个顶点之间都能够连通，则称此无向图为连通图。例如下图中的无向图就是一个连通图，因为此图中任意两顶点之间都是连通的。

    连通图示意图

    若无向图不是连通图，但图中存储某个子图符合连通图的性质，则称该子图为连通分量。

前面讲过，由图中部分顶点和边构成的图为该图的一个子图，但这里的子图指的是图中"最大"的连通子图（也称"极大连通子图"）。

    如下图所示，虽然图 a) 中的无向图不是连通图，但可以将其分解为 3 个"最大子图"，图b)，它们都满足连通图的性质，因此都是连通分量。

3.1.2 强连通图

//有向图和无向图
#include <stdio.h>
#include <string.h>#define N 5typedef struct
{int V[N];int R[N][N];
}adjmatrix_t;int main(int argc, const char *argv[])
{adjmatrix_t graph;int i,j;//1.初始顶点集合for(i = 0; i < N; i++)graph.V[i] = i;//2.将关系集合清空置0，然后输入顶点之间的关系bzero(graph.R,sizeof(graph.R));printf("请您输入顶点关系:\n");while(scanf("(V%d,V%d) ",&i,&j) == 2)//scanf函数，如果输入i j两个值成功，返回值为 2代表输入成功有两个，如果不成功为EOF{graph.R[i][j] = 1;//vi --> vjgraph.R[j][i] = 1;//vj --> vi 如何将此行代码注销，可用表示有向图}//3.打印图for(i = 0; i < N; i++){printf("V%d:",graph.V[i]);for(j = 0; j < N; j++){if(graph.R[i][j] == 1)// == 1说明vi ---> vj{printf("V%d ",graph.V[j]);//将Vi 所有能到达的顶点Vj打印}}printf("\n");}return 0;
}//scanf输入 (V0,V1) (V0,V2) (V1,V4) (V2,V1) (V2,V3) (V3,V0) (V4,V3) -1

//有向图和无向图	
#include <stdio.h>
#include <stdlib.h>#define N 5 //5代表5个顶点typedef struct node_t
{int vertex;//保存顶点struct node_t *next;//指向下一个节点的指针
}adjlist_node_t;//画边函数，也就是将顶点vj插入到对应的链表vi中 draw 画 edge边
void drawEdge(adjlist_node_t *vi, int vj)//vi代表的是对应链表的头结点的指针
{//在插入的时候对其进行排序同霍夫曼树插入根据权值排序思想一样adjlist_node_t *pnew = NULL;while(vi->next != NULL && vj > vi->next->vertex)vi = vi->next;//创建新的节点保存vjpnew = (adjlist_node_t *)malloc(sizeof(adjlist_node_t));if(NULL == pnew){perror("pnew malloc failed");return;}//创建pnew后装东西pnew->vertex = vj;pnew->next = NULL;//将节点链接到链表中，先连后面再连前面pnew->next = vi->next;vi->next = pnew;return;
}int main(int argc, const char *argv[])
{int i,j;adjlist_node_t *h = NULL;//用来保存每条链表的头指针(无头)//1.创建一个结构体数组adjlist_node_t g[N] = { 0 };for(i = 0; i < N; i++)g[i].vertex = i;printf("请您输入顶点的关系:\n");//2.输入顶点之间的关系while(scanf("(V%d,V%d) ",&i,&j) == 2){//将vj这个顶点插入到vi顶点的链表中drawEdge(g+i,j);//此行等价于 &g[i]//	drawEdge(g+j,i);//如果输入的想代表无向图，将此行代码解除注释}//3.将各个顶点所有到达的顶点进行打印for(i = 0; i < N; i++){printf("V%d:",g[i].vertex);//g[i].vertex 代表的是Vi这个顶点 h = g[i].next;//相当于遍历无头链表，需要对每一条链表进行遍历while(h != NULL){printf("V%d ",h->vertex);h = h->next;}printf("\n");//遍历完一条链表后打印一个换行}printf("\n---------------\n");return 0;
}//scanf输入 //(V0,V1) (V0,V2) (V1,V4) (V2,V1) (V2,V3) (V3,V0) (V4,V3) -1

#include "graph.h"
#include "linkqueue.h"
#include <stdio.h>
#include <stdlib.h>
#include <strings.h>//1.创建一个图
adjmatrix_t *createGraph()
{int i,j;adjmatrix_t *g = (adjmatrix_t *)malloc(sizeof(adjmatrix_t));if(NULL == g){perror("createGraph malloc failed");return NULL;}//2.初始化顶点集合for(i = 0; i < N; i++)g->V[i] = i;//清空下关系结合bzero(g->R,sizeof(g->R));printf("请您输入顶点的关系(V0,V1):\n");while(scanf("(V%d,V%d) ",&i,&j) == 2){g->R[i][j] = 1;g->R[j][i] = 1;}return g;
}
//2.获取第一个邻接点 v是被搜索的顶点
int firstAdj(adjmatrix_t *g,int v)//v == 0,找v0第一个邻接点
{int j;for(j = 0; j < N; j++){if(g->R[v][j] == 1)return j;}return -1;//代表没有邻接点
}//int u;//保存v的第一个邻接点
//u = fristAdj(g,0);//得到第一个
//u =====> 1
// u = nextAdj(g,0,u);//下一个
// u = nextAdj(g,0,u);//再下一个
//3.获取下一个邻接点 v被搜索的顶点 u 前一个邻接点
int nextAdj(adjmatrix_t *g, int v, int u)
{//获取下一个邻接点函数的使用，需要fristAdj函数的配合int j;for(j = u+1; j < N; j++)//j = u+1 是因为第一个邻节点是u，那么继续找下一个从u+1位置开始遍历{if(g->R[v][j] == 1)return j;}return -1;
}
//4.深度搜索 visited 拜访，访问 v代表的是从那个顶点开始深度搜索
//visited是一个指向整型数组的指针，用来标记这个节点是否被访问
void DFS(adjmatrix_t *g, int v, int *visited)
{//visited[v] == 0代表没被访问， 1代表被访问int u;//用来保存邻接点if(visited[v] == 0)//说明该顶点没有被访问{printf("V%d ",g->V[v]);//相当于已经被访问了visited[v] = 1;//将标志位置1，变为已经被访问,已经被打印输出}//获取v的第一个邻接点u = firstAdj(g,v);while(u != -1)//如果u == -1代表,没有邻接点{if(visited[u] == 0)//没有被访问{DFS(g,u,visited);}u = nextAdj(g,v,u);//获取下一个邻接点}
}
//5.广度搜索
void BFS(adjmatrix_t *g, int v, int *visited)
{int u;//创建一个队列linkqueue_t *p = createEmptyLinkQueue();inLinkQueue(p,v);while(!isEmptyLinkQueue(p)){v = outLinkQueue(p);if(visited[v] == 0)//说明v未被访问{printf("V%d ",g->V[v]);visited[v] = 1;//打印之后标记为已经访问}//开始遍历v所有能达到的顶点u = firstAdj(g,v);while(u != -1){if(visited[u] == 0)//v到达的顶点没有被访问{inLinkQueue(p,u);}u = nextAdj(g,v,u);//在上面入列的u基础上，在找到下一个邻接点返回}}
}