网友投稿 573 2022-10-31
【1127】ZigZagging on a Tree (30分)【中后序建树 层次】
#include#include#include#include#include#include #include#include#include #includeusing namespace std; vectorpostorder(31);vectorinorder(31);vector>levels(31);void buildTree(int postl,int postr,int inl,int inr,int level){ if(postl>postr || inl>inr) return; int root=postorder[postr];//root为根结点，在后序遍历最后一个位置上 int i=0; while(inorder[inl+i] !=root)//在中序遍历序列中查找根结点位置 i++;//跳出while时得到i，左子树结点个数为i levels[level].push_back(root);//把根结点存入对应层的vector中 buildTree(postl, postl+i-1, inl, inl+i-1, level+1);//建立左子树 buildTree(postl+i, postr-1, inl+i+1, inr, level+1);//建立右子树 //后序遍历： 左子树(postl ...postl+i-1) 右子树(post+i ... postr-1) root=postr-1 //中序遍历 ： 左子树(inl...inl+i-1) root=inl+i 右子树(inl+i+1...inr)}void zigzag(){//Z型的层序遍历 cout<=0;j--){ cout<<" "<>N){ for(int i=0;i>inorder[i];//存入中序遍历序列 } for(int i=0;i>postorder[i];//存入后序遍历序列 } buildTree(0,N-1,0,N-1,0); zigzag(); } system("pause"); return 0;}
和晴神差不多的版本
#include#include#include#include#include#include #include#include#include using namespace std; int n;int in[40],post[40];struct node{ int data; int level; node* left; node* right; node():left(NULL),right(NULL){}};node* create(int inL,int inR,int postL,int postR){ if(inL>inR) return NULL; node* root=new node; //新建一个新的结点，用来存放当前二叉树的根结点 root->data=post[postR]; //新结点的数据域为根结点的值 int k; for(k=inL;k<=inR;k++){ if(in[k]==post[postR]){//在中序序列中找到in[k]==post[postR]的结点 break; } } int num_Left=k-inL;//左子树的结点个数 //返回左子树的根结点地址，赋值给root的左指针 root->left=create(inL,k-1,postL,postL+num_Left-1); root->right=create(k+1,inR,postL+num_Left,postR-1); //返回右子树的根结点地址，赋值给root的右指针 return root;} int max_level=0; vector ve[40]; void BFS(node* root){ queueq; root->level=1;//一开始漏了这句，导致跳出读取位置 xxx时发生访问冲突 的报错 q.push(root); while(!q.empty()){ node* now=q.front(); q.pop(); ve[now->level].push_back(now->data); if(now->level>max_level) max_level=now->level; if(now->left!=NULL){ now->left->level=now->level+1; q.push(now->left); } if(now->right!=NULL){ now->right->level=now->level+1; q.push(now->right); } } }int main(){ int i,j,total=0; scanf("%d",&n); for(int i=0;i=0;j--){ printf("%d",ve[i][j]); total++; if(total 版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。
版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论，来抢沙发吧~
暂时没有评论，来抢沙发吧~