L2-011玩二叉树分数25作者陈悦单位浙江大学给出了二叉树的序列和序列,请先做一个镜面反转,然后输出层序列反转后的序列。所谓的镜面反转是指所有非叶结点的儿童。假设键值是不相等的正整数。
输入格式:输入第一行给出正整数N,这是二叉树中的结点数。第二行给出序列遍历序列。第三行给出序列遍历序列。数字之间用空间分隔。
输出格式:在一行中输出树反转后的层序遍历序列。数字间隔一个空间,行的开头和结尾不得有多余的空间。
输入样例:71234674132657输出样例:461732
#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;
}
}
}
}
文章为作者独立观点,不代表股票交易接口观点