首页 > 代码库 > 1020. Tree Traversals (25) PAT甲级真题
1020. Tree Traversals (25) PAT甲级真题
之前我看了这道题，实在是看不懂网上的解题答案，他们的具体思路基本上就是通过后续遍历和中序遍历，直接推出层次遍历。
我苦思冥想了半天，是在没看懂这种思路，于是想了一个笨点的但是也比较好理解的思路，通过后续和中序，先推出整个二叉树，再考虑
对二叉树层次遍历。
本题还有一点要注意的时在输出结果的末尾，如果使用了类似
pirntf("%d ",data);
这样的格式是不对的，一定要对末尾进行判断消除最尾端的空格。
首先最核心的部分是通过两次遍历反推回二叉树：这里的思路是，后续遍历的最末尾，一定是二叉树的根节点，后续遍历决定父子，中序遍历决定左右，从后序遍历找到了根节点后，到中序遍历中去找，找到后，中序遍历的根节点将整个二叉树一分为二，左边的为左节点，右边的为右节点，然后开始往下递归。
PTREE BuildTree(int * post, int *in,int size){ PTREE tree; int i=0; if(!size){ return(NULL); } tree=(PTREE)malloc(sizeof(TREE)); tree->data=http://www.mamicode.com/post[size-1]; for(i=0;i<size;i++){ if(post[size-1]==in[i]) break; } tree->Left=BuildTree(post,in,i); tree->Right=BuildTree(post+i,in+i+1,size-i-1); return(tree);}
在构建完了二叉树后，后续工作就不难了，要注意输出格式，最后一位不能有空格。附上完整代码：
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<iostream> 4 #include<queue> 5 using namespace std; 6 typedef struct tree{ 7 int data; 8 struct tree *Left; 9 struct tree *Right;10 }TREE,*PTREE;11 12 int TraversalTree(PTREE tree);13 PTREE BuildTree(int *,int *,int);14 int * TraversalTree_By_Level(PTREE,int);15 16 int main(){17 PTREE tree;18 int count,count1,Temp,i=0,count2;19 scanf("%d",&count);20 int pre[count],in[count];21 count1=count;22 count2=count;23 int size=count;24 while(count1!=0){25 scanf("%d",&Temp);26 pre[i]=Temp;27 i++;28 count1--;29 }30 i=0;31 while(count!=0){32 scanf("%d",&Temp);33 in[i]=Temp;34 i++;35 count--;36 }37 tree=BuildTree(pre,in,size);38 TraversalTree_By_Level(tree,count2);39 40 }41 42 43 int TraversalTree(PTREE tree){44 if(tree==NULL)45 return(0);46 printf("%d ",tree->data);47 TraversalTree(tree->Left);48 TraversalTree(tree->Right);49 }50 51 PTREE BuildTree(int * post, int *in,int size){52 PTREE tree;53 int i=0;54 if(!size){55 return(NULL);56 }57 58 tree=(PTREE)malloc(sizeof(TREE));59 tree->data=http://www.mamicode.com/post[size-1];60 for(i=0;i<size;i++){61 if(post[size-1]==in[i])62 break;63 }64 //2 3 1 5 7 6 465 //1 2 3 4 5 6 766 tree->Left=BuildTree(post,in,i);67 tree->Right=BuildTree(post+i,in+i+1,size-i-1);68 return(tree);69 }70 int * TraversalTree_By_Level(PTREE tree,int count2){71 int a[100];int i=0;int k=0;72 queue<PTREE>q1;73 PTREE Temp;74 q1.push(tree);75 while(!q1.empty()){76 Temp=q1.front();77 q1.pop();78 a[k]=Temp->data;79 k++;80 if(Temp->Left!=NULL)81 q1.push(Temp->Left);82 if(Temp->Right!=NULL)83 q1.push(Temp->Right);84 }85 while(i<count2-1){86 printf("%d ",a[i]);87 i++;88 }89 printf("%d",a[i]);90 return(NULL);91 }
1020. Tree Traversals (25) PAT甲级真题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。