L2-011玩转二叉树分数25作者陈越单位浙江大学给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。
输入格式：输入第一行给出一个正整数N，是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。
输出格式：在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。
输入样例：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;
}
}
}
}
文章为作者独立观点，不代表股票配资公司观点
相关文章
股民评论