输入格式：输入第一行给出正整数N，这是二叉树中结点的数量。第二行给出后续序列遍历序列。第三行给出序列遍历序列。数字间由空间分隔。
输入样例：72315741234567输出样例：416372代码长度限制
#include<stdio.h>
#include<stdlib.h>
typedef struct tree{
int data;
struct tree* left;
struct tree* right;
}tree,*link;
link creat(int back[],int inorder[],int n);
void ceng(link root);
int main(){
int n;
int back[55];
int inorder[55];
scanf("%d",&n);
for(int i=0;i<n;i ){
scanf("%d",&back[i]);
}
for(int i=0;i<n;i ){
scanf("%d",&inorder[i]);
}
link root =( link)malloc(sizeof(tree));
root=creat(back,inorder,n);
ceng(root);
}
link creat(int back[],int inorder[],int n){
if(n==0){
return NULL;
}
link root= (link)malloc(sizeof(tree));
int index;///根节点在中序遍历中的位置
for(int i=0;i<n;i ){
if(back[n-1]==inorder[i]){
index=i;
break;
}
}
root->data=back[n-1];
// printf("%d index:%d
",root->data,index);
root->left=creat(back,inorder,index);
root->right=creat(back index,inorder index 1,n-index-1); //注意下标的变化
// 左 根 右
//左 右 根
//左节点是一样的，数量是index，所以当右边的树，
//后续遍历序列 中刨除 左树节点，剩下的是右边的树
return root;
}
void ceng(link root){
link queue[55];//数组模拟队列，其中元素是指针结点。
int head =0;//队头 ，出去
int rear=0; //队尾,进入
queue[rear ]=root;///输入根节点
int c=0;///确保输入格式
while(rear>head){//队列不是空的
int start=head;//记录遍历开始的位置，也就是本层的头
head=rear;///本层的尾巴rear即将成为下层的头。因为所有元素都弹出队列
///在这里，下层的头head同时作为遍历结束的位置，因为rear会在遍历中不断变化，成为下层的尾巴
for(int i=start;i<head;i ){///弹出start到未改变的rear(即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;
}
}
}
}
文章为作者独立观点，不代表股票交易接口观点
股民评论