博客

7-2 玩转二叉树 (21分)

给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。

输入格式：

输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。

输出格式：

在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：

7

1 2 3 4 5 6 7

4 1 3 2 6 5 7

输出样例：

4 6 1 7 5 3 2

#include <stdio.h>
#include <stdlib.h>
typedef struct node* bintree;
typedef struct node{
	bintree left;
	bintree right;
	int data;
}tree;
bintree create(int n,int *pre,int *mid){//关键在于要通过前序中序的特点找到根节点，
										//利用递归依次层层划分下去 
	//a前序遍历 b中序遍历 
	bintree p;
	int i;
	if(n==0){
		return NULL;
	}else{
		p=(bintree)malloc(sizeof(tree));
		p->data=pre[0];
		for(i=0;i<n;i++){
			if(mid[i]==pre[0])//在中序中找到根节点 
				break;
		}
		p->left=create(i,pre+1,mid);//根节点下标为i左子树一定有 i个 
		p->right=create(n-1-i,pre+1+i,mid+i+1);//柚子树就一定有n-i-1个（因为还要除去根节点） 
	}
	return p;
}
void jx(bintree bt){//这里的镜像也是一个很简单的递归函数
	bintree p;
	if(bt!=NULL){
		if(bt->left!=NULL || bt->right!=NULL){//左右子树不同时为空就调换 
			p=bt->right;
			bt->right=bt->left;
			bt->left=p;
		}
	}else{
		return;
	}
	jx(bt->left);//依次递归下去 
	jx(bt->right);//依次递归下去 
}
void pp(bintree bt){
	int front=0,rear=1;//在这里联想到队列，我只能说是妙不可言 
	bintree t[60];
	t[0]=bt;
	while(front<rear){//条件一定是小于，小于等于都不行，一旦frout==rear,就退出，表示已经空了 
		if(t[front]!=NULL){
			if(t[front]==bt)
				printf("%d",t[front]->data);
			else
				printf(" %d",t[front]->data);
			t[rear++]=t[front]->left;
			t[rear++]=t[front]->right;
		}
		front++;//不管是否为空front都要++ 
	}
}
int main(){
	int n,pre[30],mid[30],i;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&mid[i]);
	}
	for(i=0;i<n;i++){
		scanf("%d",&pre[i]);
	}
	bintree bt;
	bt=create(n,pre,mid);
	jx(bt);
	pp(bt);
	return 0;
} 

其实代码还可以更加优化，我可以在一开始创建的时候就调换左右子树，就省去jx函数。代码如下

#include <stdio.h>
#include <stdlib.h>
typedef struct node* bintree;
typedef struct node{
	bintree left;
	bintree right;
	int data;
}tree;
bintree create(int n,int *pre,int *mid){//关键在于要通过前序中序的特点找到根节点，
										//利用递归依次层层划分下去 
	//a前序遍历 b中序遍历 
	bintree p;
	int i;
	if(n==0){
		return NULL;
	}else{
		p=(bintree)malloc(sizeof(tree));
		p->data=pre[0];
		for(i=0;i<n;i++){
			if(mid[i]==pre[0])//在中序中找到根节点 
				break;
		}
		p->right=create(i,pre+1,mid);//根节点下标为i左子树一定有 i个 
		p->left=create(n-1-i,pre+1+i,mid+i+1);//柚子树就一定有n-i-1个（因为还要除去根节点） 
	}
	return p;
}
void pp(bintree bt){
	int front=0,rear=1;//在这里联想到队列，我只能说是妙不可言 
	bintree t[60];
	t[0]=bt;
	while(front<rear){//条件一定是小于，小于等于都不行，一旦frout==rear,就退出，表示已经空了 
		if(t[front]!=NULL){
			if(t[front]==bt)
				printf("%d",t[front]->data);
			else
				printf(" %d",t[front]->data);
			t[rear++]=t[front]->left;
			t[rear++]=t[front]->right;
		}
		front++;//不管是否为空front都要++ 
	}
}
int main(){
	int n,pre[30],mid[30],i;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&mid[i]);
	}
	for(i=0;i<n;i++){
		scanf("%d",&pre[i]);
	}
	bintree bt;
	bt=create(n,pre,mid);
	pp(bt);
	return 0;
}