1020. Tree Traversals (25)

the problem is from pat,which website is http://pat.zju.edu.cn/contests/pat-a-practise/1020

and the source code is as followed.

#include<iostream>
#include<cstdlib>
#include<queue> using namespace std; const int maxx = ; typedef struct Tree
{
Tree *le;
Tree *ri;
int data;
}Tree; Tree *root; int pos[maxx],in[maxx]; void printLevelOrder(Tree *root)
{
queue<Tree*> que;
Tree *tr = NULL;
que.push(root);
bool flg = true;
while (!que.empty())
{
tr = (Tree *)que.front();
que.pop();
if (tr == NULL) continue;
if (flg)
{
printf("%d",tr->data);
flg = false;
}else
{
printf(" %d",tr->data);
}
que.push(tr->le);
que.push(tr->ri);
}
printf("\n");
} //构造树pl为后序序列的左边界pr为其右边界
//il为中续遍历的左边界ir为其右边界
Tree *buildTree(int pl,int pr,int il,int ir)
{
if (pl > pr)return NULL;
int p = il;
while (in[p] != pos[pr])
{
++p;
}
Tree *tree = (Tree *)malloc(sizeof(Tree));
tree->data = pos[pr];
tree->le = buildTree(pl,pr-ir+p-,il,p-);
tree->ri = buildTree(pr-ir+p,pr-,p+,ir); return tree;
} int main(){
int n,i;
Tree *root; scanf("%d",&n);
for(i=;i<n;++i){
scanf("%d",&pos[i]);
}
for(i=;i<n;++i){
scanf("%d",&in[i]);
}
root=buildTree(,n-,,n-);
printLevelOrder(root);
return ;
}

the main function is rebuild the tree,which is a recursive function;and it is important to find

the left side and the right side from both postOrder and InOrder!Therefore ,we can use these argument to build the tree recursively.

上一篇:漫长Appium之路(一)——从黑苹果到虚拟机


下一篇:Python数据处理PDF