DFS和BFS(c++)

@TOC

深度优先遍历dfs

• Depth First Search, 简称 DFS
• 图解链接: link
• 对每一个分支路径深入到不能再深入为止
• 二叉树的深度优先遍历特殊，分为先序遍历、中序遍历、后序遍历
• 先序遍历，对任一子树，先访问根，然后左子树，最后右子树。
• 中序遍历，对任一子树，先遍历左子树，然后根，最后右子树。
• 后序遍历，对任一子树，先遍历其左子树，然后右子树，最后根。

广度优先遍历bfs

• Breath First Search，简称bfs
• 又叫层次遍历，从上往下对每一层依次访问

代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Tree{
int data;
vector<Tree*> child;
Tree(int x){
data=x;
}
~Tree(){
for(int i=0;i<child.size();i++)
delete child[i];
}
void add(Tree* t){
child.push_back(t);
}
};
//递归实现 
void dfs(Tree* p){
cout<<p->data<<" ";
for(int i=0;i<p->child.size();i++)
dfs(p->child[i]);
}
//用队列实现 
void bfs(Tree* p){
queue<Tree*> que;
que.push(p);
while(!que.empty()){
Tree* q=que.front();
que.pop();
cout<<q->data<<" ";
for(int i=0;i<q->child.size();++i){
que.push(q->child[i]);
}
}
}
int main(){
//create a tree
Tree a(1);
a.add(new Tree(2));
a.add(new Tree(3));
a.child[0]->add(new Tree(4));
a.child[0]->add(new Tree(5));
a.child[1]->add(new Tree(6));
a.child[0]->child[1]->add(new Tree(7));
dfs(&a);
cout<<endl;
bfs(&a);
cout<<endl;
return 0;
}

原文地址：https://blog.csdn.net/qq_37755459/article/details/140460845

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！