一）基本算法 : 1.枚举 2.搜索: 深度优先搜索 广度优先搜索 启发式搜索 遗传算法 （二）数据结构的算法 （三）数论与代数算法 （四）计算几何的算法：求凸包 （五）图论 算法： 1.哈夫曼编码 2.树的遍历 3.最短路径 算法 4.最小生成树 算法 5.最小树形图 6.网络流 算法 7.匹配算法 （六）动态规划 （七）其他： 1.数值分析 2.加密算法 3.排序 算法 4.检索算法 5.随机化算法
② 图遍历算法之DFS/BFS
在计算机科学， 图遍历（Tree Traversal，也称图搜索）是一系列图搜索的算法， 是单次访问树结构类型数据（tree data structure)中每个节点以便检查或更新的一系列机制。图遍历算法可以按照节点访问顺序进行分类，根据访问目的或使用场景的不同，算法大致可分为28种：
图遍历即以特定方式访问图中所有节点，给定节点下有多种可能的搜索路径。假定以顺序方式进行（非并行），还未访问的节点就需通过堆栈（LIFO）或队列（FIFO）规则来确定访问先后。由于树结构是一种递归的数据结构，在清晰的定义下，未访问节点可存储在调用堆栈中。本文介绍了图遍历领域最流行的广度优先搜索算法BFS和深度优先搜索算法DFS，对其原理、应用及实现进行了阐述。通常意义上而言，深度优先搜索（DFS）通过递归调用堆栈比较容易实现，广义优先搜索通过队列实现。
深度优先搜索（DFS）是用于遍历或搜索图数据结构的算法，该算法从根节点开始（图搜索时可选择任意节点作为根节点）沿着每个分支进行搜索，分支搜索结束后在进行回溯。在进入下一节点之前，树的搜索尽可能的加深。
DFS的搜索算法如下（以二叉树为例）：假定根节点（图的任意节点可作为根节点）标记为 ,
(L) : 递归遍历左子树，并在节点 结束。
(R): 递归遍历右子树，并在节点 结束。
(N): 访问节点 。
这些步骤可以以任意次序排列。如果（L）在（R）之前，则该过程称为从左到右的遍历；反之，则称为从右到左的遍历。根据访问次序的不同，深度优先搜索可分为 pre-order、in-order、out-order以及post-order遍历方式。
（a）检查当前节点是否为空；
（b）展示根节点或当前节点数据；
（c）递归调用pre-order函数遍历左子树；
（d）递归调用pre-order函数遍历右子树。
pre-order遍历属于拓扑排序后的遍历，父节点总是在任何子节点之前被访问。该遍历方式的图示如下：
遍历次序依次为：F -B -A-D- C-E-G- I-H.
（a）检查当前节点是否为空；
（b）递归调用in-order函数遍历左子树；
（c）展示根节点或当前节点数据；
（d）递归调用in-order函数遍历右子树。
在二叉树搜索中，in-order遍历以排序顺序访问节点数据。该遍历方式的图示如下：
遍历次序依次为：A -B - C - D - E - F - G -H-I
（a）检查当前节点是否为空；
（b）递归调用out-order函数遍历右子树；
（c）展示根节点或当前节点数据；
（d）递归调用out-order函数遍历左子树。
该遍历方式与LNR类似，但先遍历右子树后遍历左子树。仍然以图2为例，遍历次序依次为：H- I-G- F- B- E- D- C- A.
（a）检查当前节点是否为空；
（b）递归调用post-order函数遍历左子树；
（c）递归调用post-order函数遍历右子树；
（d）展示根节点或当前节点数据。
post-order遍历图示如下：
遍历次序依次为：A-C-E-D-B-H-I-G-F.
pre-order遍历方式使用场景：用于创建树或图的副本；
in-order遍历使用场景：二叉树遍历；
post-order遍历使用场景：删除树
遍历追踪也称树的序列化，是所访问根节点列表。无论是pre-order，in-order或是post-order都无法完整的描述树特性。给定含有不同元素的树结构，pre-order或post-order与in-order遍历方式结合起来使用才可以描述树的独特性。
树或图形的访问也可以按照节点所处的级别进行遍历。在每次访问下一层级节点之前，遍历所在高层级的所有节点。BFS从根节点（图的任意节点可作为根节点）出发，在移动到下一节点之前访问所有相同深度水平的相邻节点。
BFS的遍历方法图示如下：
遍历次序依次为： F-B-G-A-D-I-C-E-H.
图算法相关的R包为igraph，主要包括图的生成、图计算等一系列算法的实现。
使用方法：
参数说明：
示例：
结果展示：
DFS R输出节点排序：
使用方法：
参数含义同dfs
示例：
结果展示：
BFS R输出节点排序：
以寻找两点之间的路径为例，分别展示BFS及DFS的实现。图示例如下：
示例：
输出结果：
示例：
输出结果：
[1] 维基网络： https://en.wikipedia.org/wiki/Tree_traversal
[2] GeeksforGeeks: https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/
[3] http://webdocs.cs.ualberta.ca/~holte/T26/tree-traversal.html
[4]Martin Broadhurst, Graph Algorithm: http://www.martinbroadhurst.com/Graph-algorithms.html#section_1_1
[5]igraph: https://igraph.org/r/doc/dfs.html
[6]igraph: https://igraph.org/r/doc/bfs.html
[7] Depth-First Search and Breadth-First Search in python: https://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/
③ 求用C语言实现二叉树层次遍历的递归算法，谢谢！！！
算法思想：层次遍历目前最普遍用的就是队列的那种方式，不是递归，但是用到while循环，既然题目要求用递归，可以用递归实现该while循环功能。算法如下：
void TransLevele(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r->ch);
if (r->left != NULL)
{
InsertQueue(r->left);
}
if (r->right != NULL)
{
InsertQueue(r->right);
}
Tree *t = DeleteQueue();
TransLevele(t);
}
//测试程序，创建树输入例如ABD##E##C##,根左右创建的方式。
如下代码是测试通过的。
#include "stdlib.h"
#define MAX 100
typedef int Element;
typedef struct tree
{
Element ch;
struct tree *left;
struct tree *right;
}Tree;
typedef struct queue
{
Tree *a[MAX];
int front;
int rear;
}Queue;
Queue Qu;
void Init();
int InsertQueue(Element ch);
Tree *DeleteQueue();
void CreateTree(Tree **r);
void TransLevele(Tree *r);
void PrintTree(Tree *r);
int main()
{
Tree *r=NULL;
CreateTree(&r);
PrintTree(r);
printf("\n");
TransLevele(r);
return 0;
}
void Init()
{
int i=0;
for (i=0; i<MAX; i++)
{
Qu.a[i] = NULL;
}
Qu.front = 0;
Qu.rear = 0;
}
int InsertQueue(Tree *r)
{
if ( (Qu.rear+1)%MAX == Qu.front)
{
printf("Queue full!");
return 0;
}
Qu.a[Qu.rear] = r;
Qu.rear = (Qu.rear+1)%MAX;
return 1;
}
Tree *DeleteQueue()
{
if (Qu.front == Qu.rear)
{
printf("Queue empty");
return NULL;
}
Tree *t=NULL;
t = Qu.a[Qu.front];
Qu.front = (Qu.front+1)%MAX;
return t;
}
void CreateTree(Tree **r)
{
Element ch;
ch=getchar();
if (ch=='#')
{
(*r)=NULL;
return ;
}
*r = (Tree *)malloc(sizeof(Tree));
(*r)->ch = ch;
CreateTree(&((*r)->left));
CreateTree(&((*r)->right));
}
void PrintTree(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r->ch);
PrintTree(r->left);
PrintTree(r->right);
}
void TransLevele(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r->ch);
if (r->left != NULL)
{
InsertQueue(r->left);
}
if (r->right != NULL)
{
InsertQueue(r->right);
}
Tree *t = DeleteQueue();
TransLevele(t);
}