图的遍历以及二叉树的遍历

1.二叉树的遍历方式有深度优先搜索与广度优先搜索，其中深搜又包括前序、中序与后序，而宽搜也叫层次遍历。

2.各种方式的顺序：
（1）前序遍历：根结点 -> 左子树 -> 右子树
（2）中序遍历：左子树-> 根结点 -> 右子树
（3）后序遍历：左子树 -> 右子树 -> 根结点
（4）层次遍历：宽搜，逐层遍历

前序遍历：1 2 4 5 7 8 3 6
中序遍历：4 2 7 5 8 1 3 6
后序遍历：4 7 8 5 2 6 3 1
层次遍历：1 2 3 4 5 6 7 8

3.下面介绍一种以邻接矩阵为基础的遍历思想。
（1）基础知识：
图 G 是由两个集合顶点集 V(G) 和边集 E(G) 组成的，记作G=( V(G)，E(G) )，简称G=(V，E)。
V(vertex)是顶点的有穷非空集合 ，E(edge)是两个顶点之间的关系，即边的有穷集合。

（2）图分为三类：
有向图：边有方向的图
无向图：边没有方向的图
带权图

（3）图主要有3种常用的存储表示方式：邻接矩阵，邻接表，邻接多重表。
邻接矩阵：


（4）从图中某一顶点出发访遍图中所有的顶点，且使每个顶点仅被访问一次，这一过程就叫做图的遍历 。
（5）两种图的遍历方法:
深度优先搜索 DFS
广度优先搜索 BFS
（6）具体代码及注释
深度优先搜索：

void DFS()   //为了防止遗漏有多个开始点的情况
    {
        for(int i=0;i<VertexNum;i++)
            if(visit[i]==0)      //如果这个点没被走过
                dfs(i);
    }

void dfs(int i)  //深搜（前序）
    {
        cout<<" ->"<<i+1;     //打印
        visit[i]=1;    //标记为已经走过
        for(int j=0;j<VertexNum;j++)
            if(matrix[i][j]&& !visit[j] &&matrix[i][j]!=MAX )    　//两点直接相连，该点没有被走过，两点距离不为无穷大
                dfs(j);
    }

广度优先搜索（运用队列）：／／其实是在强行运用队列，主要思想还是邻接矩阵

 void BFS()  //为了防止遗漏有多个开始点的情况
    {
        for(int i=0;i<VertexNum;i++)
            if(visit[i]==0)    //如果这个点没被走过
                bfs(i);
    }

 void bfs(int i)
    {
        int j;
        queue<int> q;
        visit[i]=1;     // 标记为已经走过
        cout<<" ->"<<i<<endl;   //打印
        q.push(i);     //入队列
        while(!q.empty())
        {
            q.pop();   //出队列
            for(j=0;j<VertexNum;j++)
                if( matrix[i][j]&&!visit[j] && matrix[i][j]!=MAX )     //两点直接相连，该点没有被走过，两点距离不为无穷大
                {
                    cout<<" ->"<<j;  //打印
                    visit[j]=1;     // 标记为已经走过
                    q.push(j);     //入队列
                }
        }
    }

4.一个介绍二叉树遍历的非常非常优秀博客（链接附在引用上）（本文的主要精华）

引用
http://m.blog.csdn.net/article/details?id=8645991