首页 > 代码库 > 数据结构:树的BFS,树的层次遍历! 按先序遍历创建一棵树,然后以层次遍历输出。
数据结构:树的BFS,树的层次遍历! 按先序遍历创建一棵树,然后以层次遍历输出。
按先序遍历创建一棵树,以层次遍历输出
样例输入
A B # D # # C E # # F # #
样例输出
LevelOrder: A B C D E F
代码:
#include <iostream>#include <queue>using namespace std;struct node { //表示一个树上的节点 char ch; node *left, *right;};node* creat() { //以递归的方式构造一棵二叉树 node *root = new node; char c; cin >> c; if(c == '#') root = NULL; else { root->ch = c; root->left = creat(); root->right = creat(); } return root; //返回这棵树的根节点}int main() { node *root = creat(); queue<node*> q; if(root) q.push(root); cout << "LevelOrder:"; while(!q.empty()) { //用BFS的方法,层次遍历输出该二叉树 cout << " " << q.front()->ch; if(q.front()->left) q.push(q.front()->left); //把当前节点左子树的根节点加入队列前,必须先检验当前节点是否具有左子树!!! if(q.front()->right) q.push(q.front()->right); //把当前节点右子树的根节点加入队列前,必须先检验当前节点是否具有右子树!!! q.pop(); //处理完当前节点以后,就可以把它从队列中剔除了! } cout << endl; return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。