PTA-1020——Tree Traversals
题目:Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences,you are supposed to output the level order traversal sequence of the corresponding binary tree. Input Specification:Each input file contains one test case. For each case,the first line gives a positive integer?N?(≤),the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space. Output Specification:For each test case,print in one line the level order traversal sequence of the corresponding binary tree. All the numbers in a line must be separated by exactly one space,and there must be no extra space at the end of the line. Sample Input:7 2 3 1 5 7 6 4 1 2 3 4 5 6 7 Sample Output:4 1 6 3 5 7 2 分析:二叉树(根据后序、中序遍历还原二叉树)、BFS 参考博客:点击前往 代码:1 #include<iostream> 2 #include<queue> 3 using namespace std; 4 struct Node{ 5 int data; 6 Node* lchild; 7 Node* rchild; 8 }; 9 10 int post[31]; 11 int in[31]; 12 int n; 13 14 //根据后序和中序遍历创建二叉树 15 Node* create(int postL,int postR,int inL,int inR){ 16 if(postL>postR){ 17 return NULL; 18 } 19 Node* root=new Node; 20 root->data=post[postR]; //后序的末尾是根 21 int k; 22 for(k=inL;k<=inR;k++){ //中序中寻找和后序末尾值相同的结点 23 if(in[k]==post[postR]){ 24 break; 25 } 26 } 27 int numLeft=k-inL; 28 root->lchild=create(postL,postL+numLeft-1,inL,k-1); 29 root->rchild=create(postL+numLeft,postR-1,k+1,inR); 30 return root; 31 } 32 33 int num=0; 34 //宽搜读取二叉树 35 void BFS(Node* root){ 36 queue<Node*> q; 37 q.push(root); 38 while(!q.empty()){ 39 num++; 40 Node* now=q.front(); 41 cout<<now->data; 42 if(num<n){ 43 cout<<" "; 44 } 45 q.pop(); 46 if(now->lchild!=NULL){ 47 q.push(now->lchild); 48 } 49 if(now->rchild!=NULL){ 50 q.push(now->rchild); 51 } 52 } 53 } 54 55 int main(){ 56 cin>>n; 57 for(int i=0;i<n;i++){ 58 cin>>post[i]; 59 } 60 for(int i=0;i<n;i++){ 61 cin>>in[i]; 62 } 63 Node* root=create(0,n-1,0,n-1); 64 BFS(root); 65 return 0; 66 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |