以下为配合PAT1086 修改为层次遍历的代码，可以参考我的上一篇文章；

原理就是BFS

int level_order(TreeNode * Tree){
	queue<TreeNode *> q;
	q.push(Tree);
	while(!q.empty()){
		cout<<q.front()->data<<" ";
		TreeNode *tmp = new TreeNode;
		tmp->data=q.front()->data;
		tmp->left=q.front()->left;
		tmp->right=q.front()->right;
		q.pop();
		if(tmp->left!=NULL) q.push(tmp->left);
		if(tmp->right!=NULL) q.push(tmp->right);
		
	}
	cout<<endl;
}

#include<iostream>
#include<algorithm>
#include<string>
#include<stack>
#include<queue>
using namespace std;

typedef struct TreeNode {
	int data;
	struct TreeNode *left,*right;
} TreeNode;

TreeNode *pTree = new TreeNode;

int n,b=0,b2=0,p,op=0;

stack<int> s;

int arr_pre[40],arr_mid[40],r[40],h=0;

void last_order(TreeNode * Tree){
	if(Tree!=NULL){
		last_order(Tree->left);
		last_order(Tree->right);
		r[h++]=Tree->data;
	}
	return;
}
int level_order(TreeNode * Tree){
	queue<TreeNode *> q;
	q.push(Tree);
	while(!q.empty()){
		cout<<q.front()->data<<" ";
		TreeNode *tmp = new TreeNode;
		tmp->data=q.front()->data;
		tmp->left=q.front()->left;
		tmp->right=q.front()->right;
		q.pop();
		if(tmp->left!=NULL) q.push(tmp->left);
		if(tmp->right!=NULL) q.push(tmp->right);
		
	}
	cout<<endl;
}
void Build_Tree(TreeNode* &Tree,int p1/* 中序遍历扫描起点 */,int p2 /* 中序遍历扫描终点 */){
	if(p1>p2) return;
	Tree = new TreeNode;
	Tree->left = Tree->right = NULL;
	int pos;
	for(int i=p1;i<=p2;i++){
		if(arr_mid[i]==arr_pre[op]) {
			pos=i;
			break;
		}
	}
	Tree->data=arr_pre[op++];
	Build_Tree(Tree->left,p1,pos-1);
	Build_Tree(Tree->right,pos+1,p2);
	//cout<<Tree->data<<"| "; 
	return;
}

int main(){
	string act;
	cin>>n;
	pTree->left=pTree->right=NULL;
	while(cin>>act){
		if(act=="Push"){
			cin>>p;
			s.push(p);
			arr_pre[b++]=p; 
		}
		if(act=="Pop"){
			arr_mid[b2++]=s.top();
			s.pop();
		}
	}

	Build_Tree(pTree,0,n-1);
	level_order(pTree);
	return 0;
}

693 total views, no views today