树（1）
|
二叉树基本操作 ?
1020?Tree Traversals?(25?分)
?
Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences,you are supposed to output the level order traversal sequence of the corresponding binary tree. Input Specification:Each input file contains one test case. For each case,the first line gives a positive integer?N?(≤),the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space. Output Specification:For each test case,print in one line the level order traversal sequence of the corresponding binary tree. All the numbers in a line must be separated by exactly one space,and there must be no extra space at the end of the line. Sample Input:7 2 3 1 5 7 6 4 1 2 3 4 5 6 7 Sample Output:
#include <cstdio> #include <queue> using namespace std; int post[50],in[50]; int n,s=0; //定义二叉树的基本操作 struct node//结点结构 { int value; node* left; node* right; }; node* rebuild(int pof,int pol,int inf,int inl) { if(pol<pof) return NULL; node* root=new node; root->value=post[pol]; int i=0; for(i=inf;i<=inl;i++) { if(in[i]==post[pol]) break; } int leftnum=i-inf; root->left=rebuild(pof,pof+leftnum-1,inf,inf+leftnum-1); root->right=rebuild(pof+leftnum,pol-1,inf+leftnum+1,inl); return root; } void level(node* root) { queue<node*> q; q.push(root); while(!q.empty()) { node* now=q.front(); q.pop(); printf("%d",now->value); s++; if(now->left!=NULL) q.push(now->left); if(now->right!=NULL) q.push(now->right); if(s<n) printf(" "); } } int main() { scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&post[i]); for(int i=0;i<n;i++) scanf("%d",&in[i]); node* root=rebuild(0,n-1,0,n-1); level(root); return 0; } 按书上的套路多练练，熟悉常规操作。 ?
1086?Tree Traversals Again?(25?分)
?
An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example,suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed,the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.
Figure 1 Input Specification:Each input file contains one test case. For each case,the first line contains a positive integer?N?(≤) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to?N). Then?2?lines follow,each describes a stack operation in the format: "Push X" where X is the index of the node being pushed onto the stack; or "Pop" meaning to pop one node from the stack. Output Specification:For each test case,print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space,and there must be no extra space at the end of the line. Sample Input:6 Push 1 Push 2 Push 3 Pop Pop Push 4 Pop Pop Push 5 Push 6 Pop Pop Sample Output:
#include <cstdio> #include <stack> using namespace std; int post[50],in[50],pre[50]; int n; stack<int> temp; void build(int prel,int prer,int inl,int inr,int postl,int postr) { if(prel>prer) return; post[postr]=pre[prel]; int i; for(i=inl;i<=inr;i++) { if(in[i]==pre[prel]) break; } int len=i-inl; build(prel+1,prel+len,inl,i,postl,postl+len-1); build(prel+len+1,prer,i+1,inr,postl+len,postr-1); return; } int main() { char str[10]; int x,j=0,k=0; scanf("%d",&n); for(int i=0;i<2*n;i++) { scanf("%s",&str); if(str[1]==‘u‘) { scanf("%d",&x); pre[j++]=x;temp.push(x); }else { in[k++]=temp.top(); temp.pop(); } } build(0,n-1); for(int i=0;i<n;i++) { printf("%d",post[i]); if(i<n-1) printf(" "); } return 0; } ?
1102?Invert a Binary Tree?(25?分)
?
The following is from Max Howell @twitter: Google: 90% of our engineers use the software you wrote (Homebrew),but you can‘t invert a binary tree on a whiteboard so fuck off. Now it‘s your turn to prove that YOU CAN invert a binary tree! Input Specification:Each input file contains one test case. For each case,the first line gives a positive integer?N?(≤) which is the total number of nodes in the tree -- and hence the nodes are numbered from 0 to?N?1. Then?N?lines follow,each corresponds to a node from 0 to?N?1,and gives the indices of the left and right children of the node. If the child does not exist,a? Output Specification:For each test case,print in the first line the level-order,and then in the second line the in-order traversal sequences of the inverted tree. There must be exactly one space between any adjacent numbers,and no extra space at the end of the line. Sample Input:8 1 - - - 0 - 2 7 - - - - 5 - 4 6 Sample Output:
#include <cstdio> #include <queue> using namespace std; int n; int k=0; int j=0; struct node { int left; int right; }nodes[15]; void invert(int root) { if(root==-1) return; invert(nodes[root].left); invert(nodes[root].right); swap(nodes[root].left,nodes[root].right); return; } void lev(int root) { queue<int> q; q.push(root); while(!q.empty()) { int now=q.front(); q.pop(); printf("%d",now); j++; if(j<n) printf(" "); if(nodes[now].left!=-1) q.push(nodes[now].left); if(nodes[now].right!=-1) q.push(nodes[now].right); } } void in(int root) { if(root==-1) return; in(nodes[root].left); printf("%d",root); k++; if(k<n) printf(" "); in(nodes[root].right); return; } int main() { char l,r; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%*c%c %c",&l,&r); if(l!=‘-‘) nodes[i].left=l-‘0‘;else nodes[i].left=-1; if(r!=‘-‘) nodes[i].right=r-‘0‘;else nodes[i].right=-1; } int judge[15]={0}; for(int i=0;i<n;i++) { if(nodes[i].left!=-1) judge[nodes[i].left]=1; if(nodes[i].right!=-1) judge[nodes[i].right]=1; } int root; for(root=0;root<n;root++) { if(judge[root]!=1) break; } invert(root); lev(root); printf("n"); in(root); return 0; } 这一题用静态二叉树实现，没看仔细题，还要先反转（大概是我不认识那个单词所以直接忽略了），即便如此看了书后发现还用了一些技巧我没有想到。 输入时没注意而段错误，还有用后序遍历实现反转。 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
