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.一个介绍二叉树遍历的非常非常优秀博客(链接附在引用上)(本文的主要精华)
版权声明:本文为thj19980720原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。