在编程生活中，我们总会遇见树性结构，这几天刚好需要对树形结构操作，就记录下自己的操作方式以及过程。现在假设有一颗这样树，（是不是二叉树都没关系，原理都是一样的）
1.广度优先遍历
英文缩写为BFS即Breadth FirstSearch。其过程检验来说是对每一层节点依次访问，访问完一层进入下一层，而且每个节点只能访问一次。对于上面的例子来说，广度优先遍历的 结果是：A,B,C,D,E,F,G,H,I(假设每层节点从左到右访问)。
先往队列中插入左节点，再插右节点，这样出队就是先左节点后右节点了。
广度优先遍历树，需要用到队列（Queue）来存储节点对象,队列的特点就是先进先出。例如，上面这颗树的访问如下：
首先将A节点插入队列中，队列中有元素（A）;
将A节点弹出，同时将A节点的左、右节点依次插入队列，B在队首，C在队尾，（B，C），此时得到A节点；
继续弹出队首元素，即弹出B，并将B的左、右节点插入队列，C在队首，E在队尾（C,D，E），此时得到B节点；
继续弹出，即弹出C，并将C节点的左、中、右节点依次插入队列，（D,E,F,G,H），此时得到C节点；
将D弹出，此时D没有子节点，队列中元素为（E,F,G,H），得到D节点；
以此类推。
//广度优先搜索伪代码
bool visited[MaxVertexNum]; //访问标记数组
void BFSTraverse(Graph G){
//对图进行广度优先搜索遍历，设访问函数为visit()
for(i=0；i<G.vexnum;i++){
visited[i] = FALSE; //访问标记数组初始化
InitQueue(Q); //初始化辅助队列Q
for(i=0;i<G.vexnum;++i) //从0号顶点开始遍历
if(!visited[i]) //对每个连通分量调用一次BFS
BFS(G,i); //Vi未访问过，从Vi开始BFS
}
}
void BFS(Graph G，int v){
//从顶点v出发，广度优先遍历图G，算法借助一个辅助队列Q
visit(v); //访问初始顶点v
visited[v]=TRUE; //对v作已访问标记
Enqueue(Q,v); //顶点v入队列
while(!isEmpty(Q)){
DeQueue(Q,v); //顶点v出队列
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
//检测v的所有临接点
if(!visited[w]){ //w为v的尚未访问的邻接点
visit(w); //访问w
visited[w]=TRUE; //对w做已访问标记
EnQueue(Q,w); //w入队
}
}
}
}
2、深度优先遍历
英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。对于上面的例子来说深度优先遍历的结果就是：A,B,D,E,I,C,F,G,H.(假设先走子节点的的左侧)。
深度优先遍历各个节点，需要使用到栈（Stack）这种数据结构。stack的特点是是先进后出。整个遍历过程如下：
先往栈中压入右节点，再压左节点，这样出栈就是先左节点后右节点了。
首先将A节点压入栈中，stack（A）;
将A节点弹出，同时将A的子节点C，B压入栈中，此时B在栈的顶部，stack(B,C)；
将B节点弹出，同时将B的子节点E，D压入栈中，此时D在栈的顶部，stack（D,E,C）；
将D节点弹出，没有子节点压入,此时E在栈的顶部，stack（E，C）；
将E节点弹出，同时将E的子节点I压入，stack（I,C）；
依次往下，最终遍历完成。
//深度优先搜索递归实现
bool visited[Max_Vertex_Num]; //访问标记数组
void DFSTraverse(Graph G){
//对图G进行深度优先遍历，访问函数为visit()
for(v=0;v<G.vexnum;++v)
visited[v] = FALSE; //初始化已访问标记数据
for(v=0;v<G.vexnum;++v) //从v=0开始遍历
if(!visited[v])
DFS(G,V);
}
void DFS(Graph G,int v){
//从顶点v出发，采用递归，深度优先遍历图G
visit(v); //访问顶点v
visited[v]=TRUE; //设置访问标记
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v))
if(!visited[w]){ //w为尚未访问的邻接顶点
DFS(G,w);
}
}