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

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


版权声明:本文为thj19980720原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。