[数据结构与算法]1102 Invert a Binary Tree (25 分)

1102 Invert a Binary Tree (25 分)

题意

给出二叉树各个节点的左右子树（不存在的用 - 表示），反转该树的左右节点，要求输出该树反转后的层序遍历序列和中序遍历序列。（树节点编号从0 - n-1)

思路

先通过给出的各个节点建立树。由于给的是节点的左右子节点，这里采用静态写法建立二叉树会更简单一些。
建立btree结构体数组，下标表示节点编号。通过给出的每个节点的左右子节点建树。根节点没有出现在给出的数据中（根节点不可能作为某个节点的子节点），所以在处理数据时标记一下就可以找到根节点。

节点反转：可以通过后序遍历，在遍历的过程中调换左右节点即可。
层序遍历：1020 Tree Traversals (25 分)
中序遍历：左根右遍历，结尾不能有空格，可以存在队列中，之后再按条件输出即可。

代码

#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
typedef struct node{
	int lchild,rchild,data;
}node;
queue<int>q;
node btree[20];
int vis[20],n;
void invert(int root)
{
	if(root!=-1){
		invert(btree[root].lchild);
		invert(btree[root].rchild);
		int temp;
		temp=btree[root].lchild;
		btree[root].lchild=btree[root].rchild;
		btree[root].rchild=temp;
	}
}
void prin(int root)
{
	if(root==-1){
		return ;
	}
	printf("%d ",root);
	prin(btree[root].lchild);
	prin(btree[root].rchild);
}
void order(int root)
{
	if(root!=-1){
		printf("%d",root);
		q.push(root);
		while(!q.empty()){
			root=q.front();
			q.pop();
			if(btree[root].lchild!=-1){
				printf(" %d",btree[root].lchild);
				q.push(btree[root].lchild);
			}
			if(btree[root].rchild!=-1){
				printf(" %d",btree[root].rchild);
				q.push(btree[root].rchild);
			}
		}
	}
}
void in(int root)
{
	if(root!=-1){
		in(btree[root].lchild);
		q.push(root);
		in(btree[root].rchild);
	}
}
int main()
{
	int root;
	char ch;
	scanf("%d",&n);
	memset(vis,0,sizeof(vis));
	for(int i=0;i<n;i++){
		getchar();
		scanf("%c",&ch);
		if(ch>='0'&&ch<='9'){
			btree[i].lchild=ch-'0';
			vis[ch-'0']=1;
		}else{
			btree[i].lchild=-1;
		}
		getchar();
		scanf("%c",&ch);
		if(ch>='0'&&ch<='9'){
			btree[i].rchild=ch-'0';
			vis[ch-'0']=1;
		}else{
			btree[i].rchild=-1;
		}	
	}
//		scanf("%c %c",&ch1,&ch2);
//		if(ch1>='0'&&ch1<='9'){
//			btree[i].lchild=ch1-'0';
//			vis[ch1-'0']=1;
//		}else{
//			btree[i].lchild=-1;
//		}
//		if(ch2>='0'&&ch2<='9'){
//			btree[i].rchild=ch2-'0';
//			vis[ch2-'0']=1;
//		}else{
//			btree[i].rchild=-1;
//		}
	for(int i=0;i<n;i++){
		if(vis[i]==0){
			root=i;
			break;
		}
	}
//	for(int i=0;i<n;i++){
//		printf("%d %d\n",btree[i].lchild,btree[i].rchild);
//	}
	invert(root);
//	prin(root);
	order(root);
	printf("\n");
//	printf("#####################\n");
	in(root);
	if(!q.empty()){
		printf("%d",q.front());
		q.pop();
		while(!q.empty()){
			printf(" %d",q.front());
			q.pop();
		}
	}
	return 0;
}