---

本文包含王道考研讲课中所涉及的数据结构中的所有代码，当PPT代码和书上代码有所区别时以咸鱼的PPT为主，个人认为PPT上的代码比王道书上的代码要便于理解，此外，本博客也许会补充一些额外的代码进来（不仅受限于王道考研），408中冷门考点频出，应该会囊括所有涉及到的代码，这也是我的DS的第二轮复习，希望与大家共勉之。

DS的后四章只有最后一章（排序）涉及大量的代码，而树，图，查找这三章，对于概念的考察比较深入，故本文对于前三章也会进行概念上的整理，代码的话也同样会全部给出。

相关文章：
王道考研数据结构代码总结（前四章）

---

树

基本概念与属性

空树：节点数为0的树

非空树的特性:
1.有且仅有一个根节点
2.没有后继的结点称为“叶子结点”(或终端结点)
3.有后继的结点称为“分支结点”(或非终端结点)
4.除了根节点外，任何一个结点都 有且仅有一个前驱
5.每个结点可以有0个或多个后继。

树的属性：
1.结点的层次(深度)：从上往下数(默认从1开始)
2.结点的高度：从下往上数
3.树的高度(深度)：总共有多少层
4.结点的度：有几个孩子(分支)；【所以非叶子结点的度 $>0$；叶子结点的度 $=0$】
5.树的度：各节点的度的最大值

有序树与无序树：
有序树：逻辑上看，树中结点的各子树从左至右是有次序的，不能互换
无序树：逻辑上看，树中结点的各子树从左至右是无次序的，可以互换
【具体看你用树存什么，是否需要用 结点的左右位置关系 反映某些逻辑关系】

森林：森林是 $m(m\ge 0)$ 棵 互不相交 的树的集合； $m=0$ 代表空森林，森林和树是可以互相转换的。

树的基本性质

注意这是树的基本性质，即只要是个树，就有以下性质：

1. 结点数 = 总度数 $+1$

   证明：结点的度数 = 它的孩子数，只有根节点没父节点，即度数求和之后加上根节点后就是总度数

2. 树的度：各结点的度的最大值

3. $m$叉树：每个结点最多只能有 $m$ 个孩子的树

4. 度为$m$的树、$m$叉树的区别
   

图

拓扑排序

逆拓扑排序：

// 逆拓扑排序的实现（DFS算法） void DFSTraverse(Graph G){            // 对图G进行深度优先遍历 for (v = 0; v < G.vexnum; ++ v)visited[v] = false;           // 初始化已访问标记数据 for (v = 0; v < G.vexnum; ++ v)   // 本代码中是从v=0开始遍历 if (!visted[v])DFS(G, v);
/* 
注意这里也是没被访问过直接DFS
这是因为第一个节点的DFS就会输出完一个连通分量
全部打印出去后，剩下的点和边也会是一个或多个连通分量，即会出现出度为0的 "线"
此时再次DFS即可 
*/
}void DFS(Graph G, int v){visit(v);                 // 从顶点v出发，深度优先遍历图G visited[v] = true;           // 设已访问标记 
/* 
为什么不pop?
逆拓扑排序是先输出出度为0的点
所以只要有能往出走，就继续DFS即   if (!visited[w]) DFS(G, w);
故当不能往出走的时候，那么就是找见了出度为0的点
故我们需要打印输出，然后回溯 
*/for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighor(G, v, w))if (!visited[w]){        // w为u的尚未访问的邻接顶点 DFS(G, w);}print(v);           // 打印顶点 
/*
DFS实现逆拓扑排序：在顶点推栈前输出
此时的栈顶元素就是出度为0的点，符合我们的逆拓扑排序打印点的条件 
逆拓扑排序打印点的条件：
1.找一个出度为0的点输出
2.删除该顶点和所有以它为终点的有向边
无法继续DFS就是找到了出度为0的点
打印顶点其实就相当于出栈，即删除这个结点和以它为重点的有向边 
*/
}