首页 > 代码库 > 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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。