SDUTOJ 2173 数据结构实验之求二叉树后序遍历和层次遍历

2/10/2017来源:ASP.NET技巧人气:244

[cpp] view plain copy #include<iostream>  #include<stdio.h>  #include<queue>  #include<string.h>  #include<stdlib.h>  using namespace std;  char s1[100],s2[100],ans[100];  typedef struct BiTNode  {      char data;      struct BiTNode *lchild,*rchild;  }BiTNode,*BiTree;  void build(BiTree &T,char *s1,char *s2,int n)//利用前序遍历和中序遍历恢复二叉树  {      if(n<=0) T=NULL;      else      {          int p=strchr(s2,s1[0])-s2;          T=new BiTNode;          T->data=s1[0];          build(T->lchild,s1+1,s2,p);//递归创建左子树          build(T->rchild,s1+p+1,s2+p+1,n-p-1);//递归创建右子树      }  }  void build1(int n,char *s1,char *s2,char *s)//根据前序遍历和中序遍历求后序遍历  {       if(n<=0) return ;       else       {           int p=strchr(s2,s1[0])-s2;           build1(p,s1+1,s2,s);           build1(n-p-1,s1+p+1,s2+p+1,s+p);           s[n-1]=s1[0];       }  }  void levelOrder(BiTree T)//bfs算法完成层次遍历,使用队列存储数据。  {      BiTree p=T;      queue<BiTree>queue;      queue.push(p);      while(!queue.empty())      {          p=queue.front();          cout<<p->data;          queue.pop();          if(p->lchild!=NULL)          {              queue.push(p->lchild);          }          if(p->rchild!=NULL)          {              queue.push(p->rchild);          }      }  }  int main()  {      BiTree T;      int n,len;      cin>>n;      while(n--)      {          cin>>s1>>s2;          len=strlen(s1);          build(T,s1,s2,len);          build1(len,s1,s2,ans);          ans[len]='\0';          cout<<ans<<endl;          levelOrder(T);          cout<<endl;      }      return 0;  }  转载地址http://blog.csdn.net/r_misaya/article/details/40396607