输入样例：712345674132657输出样例：4617532
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct btree{
int data;
struct btree *left;
struct btree *right;
}btree,*tree;
tree creat(int pre[],int inorder[],int n);
void preSearch(tree root);
void level(tree root);
int main(){
int n;
scanf("%d",&n);
int inorder[30];
int pre[30];
for(int i=0;i<n;i++){
scanf("%d",&inorder[i]);
}
for(int i=0;i<n;i++){
scanf("%d",&pre[i]);
}
tree root = (tree)malloc(sizeof(btree));
root=creat(pre,inorder,n);
level(root);
}
tree creat(int pre[],int inorder[],int n){
if(n==0){
return NULL;
}
tree root = (tree)malloc(sizeof(btree));
root->data=pre[0];
//printf("%d
",pre[0]);
int index;
for(int i=0;i<n;i++){
if(pre[0]==inorder[i]){
index=i;
break;
}
}
//因为镜像，要反转一下
root->left=creat(pre+index+1,inorder+index+1,n-index-1);
root->right=creat(pre+1,inorder,index) ;
return root;
}
void preSearch(tree root){
printf("
");
if(root==NULL){
return;
}
printf("%d
",root->data);
level(root->left);
level(root->right);
}
void level(tree root){
tree queue[30];//队列尾巴进入，脑壳出去
int head=0;
int rear=0;
queue[rear++]=root;
int c=0;
while(head<rear){//队列不为空
int start=head;//start记录遍历开始的位置
head=rear;//此时 的head是该层的尾巴，也是下层的头
for(int i=start;i<head;i++){//输出队列中的元素 ，注意i<head
if(c==0){
printf("%d",queue[i]->data);
c++;
}else{
printf(" %d",queue[i]->data);
}
//子树进入队列
if(queue[i]->left!=NULL){
queue[rear++]=queue[i]->left;
}
if(queue[i]->right!=NULL){
queue[rear++]=queue[i]->right;
}
}
}
}
输入格式：输入第一行给出一个正整数N，是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。
文章为作者独立观点，不代表股票配资公司观点
相关文章
股民评论