首页 > 代码库 > 数据结构:树的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;}