首页 > 代码库 > PAT-1102(Invert a Binary Tree)

PAT-1102(Invert a Binary Tree)

  题目见这里

   和1099略微相似,考察二叉树和基本的遍历,算是简单的啦,下标还充当了数据域,主要是知道要标记访问到的下标,从而确定root

//1102:Invert a Binary Tree#include <cstdio>#include <iostream> using namespace std;const int N = 10;typedef struct node{	int lChild,rChild;}Node;void Input(int &root, bool *flag, Node *node, int &n){	int i;	char left,right;	scanf("%d",&n);	getchar();	for(i=0;i<n;i++){		scanf("%c %c",&left,&right);		getchar();		if(left==‘-‘) node[i].lChild = -1;		else{			node[i].lChild = left-‘0‘;			flag[left-‘0‘] = true;		}		if(right==‘-‘) node[i].rChild = -1;		else{			node[i].rChild = right-‘0‘;			flag[right-‘0‘] = true;		}	}	for(i=0;i<n;i++) 		if(!flag[i]){			root = i;			break;		}  }void Invert(int root, Node *node){	if(root!=-1){		Invert(node[root].lChild,node);		Invert(node[root].rChild,node);		swap(node[root].lChild,node[root].rChild);	}}void LevelOrderTraverse(int root, Node *node, int n){	int qNode[N],tmpNode;	int front,rear;	front = rear = 0;	if(root==-1) return;	qNode[rear] = root;	rear ++;	while(front<rear){ //无‘=‘ 		tmpNode = qNode[front];		front ++;		printf("%d",tmpNode);		if(front<n) printf(" ");		else printf("\n");		if(node[tmpNode].lChild!=-1){			qNode[rear]	= node[tmpNode].lChild;			rear ++;		}		if(node[tmpNode].rChild!=-1){			qNode[rear]	= node[tmpNode].rChild;			rear ++;		}	}}void InOrderTraverse(int root, Node *node, int n){	static int i = 1;	if(root!=-1){		InOrderTraverse(node[root].lChild,node,n);		printf("%d",root);		if(i==n) printf("\n");		else printf(" ");		i ++;		InOrderTraverse(node[root].rChild,node,n);	}}int main(){//	freopen("Data.txt","r",stdin);	Node node[N];	bool flag[N]={false};	int root,n;	Input(root,flag,node,n);	Invert(root,node);	LevelOrderTraverse(root,node,n);	InOrderTraverse(root,node,n);	return 0;}

 

     

PAT-1102(Invert a Binary Tree)