03 樹1：樹的同構 Description: 給定兩棵樹T1和T2。如果T1可以通過若幹次左右孩子互換就變成T2，則我們稱兩棵樹是“同構”的。例如圖1給出的兩棵樹就是同構的，因為我們把其中一棵樹的結點A、B、G的左右孩子互換後，就得到另外一棵樹。而圖2就不是同構的。現給定兩棵樹，請你判斷它們是否是 ...
03-樹1：樹的同構
Description:
給定兩棵樹T1和T2。如果T1可以通過若幹次左右孩子互換就變成T2，則我們稱兩棵樹是“同構”的。例如圖1給出的兩棵樹就是同構的，因為我們把其中一棵樹的結點A、B、G的左右孩子互換後，就得到另外一棵樹。而圖2就不是同構的。現給定兩棵樹，請你判斷它們是否是同構的。
Input:
輸入給出2棵二叉樹樹的信息。對於每棵樹，首先在一行中給出一個非負整數N(≤10)，即該樹的結點數（此時假設結點從0到N-1編號）；隨後N行，第i行對應編號第i個結點，給出該結點中存儲的1個英文大寫字母、其左孩子結點的編號、右孩子結點的編號。如果孩子結點為空，則在相應位置上給出“-”。給出的數據間用一個空格分隔。註意：題目保證每個結點中存儲的字母是不同的。
Output:
如果兩棵樹是同構的，輸出“Yes”，否則輸出“No”。
SampleInput1:
8
A 1 2
B 3 4
C 5 -
D - -
E 6 -
G 7 -
F - -
H - -
8
G - 4
B 7 6
F - -
A 5 1
H - -
C 0 -
D - -
E 2 -
SampleOutput1:
Yes
SampleInput2:
8
B 5 7
F - -
A 0 3
C 6 -
H - -
D - -
G 4 -
E 1 -
8
D 6 -
B 5 -
E - -
H - -
C 0 2
G - 3
F - -
A 1 4
SampleOutput2:
No
Codes:
//#define LOCAL
#include <cstdio>
#define M 15
struct Tree { int l, r; char p; };
Tree T1[M], T2[M];
int bT(Tree T[]) {
int i, n, A[M]; char a, b;
scanf("%d", &n);
if(n) {
for(i=0; i<n; ++i) A[i] = 0;
for(i=0; i<n; ++i) {
scanf(" %c %c %c", &T[i].p, &a, &b);
if(a != '-') { T[i].l = a-'0'; A[T[i].l] = 1; } else T[i].l = -1;
if(b != '-') { T[i].r = b-'0'; A[T[i].r] = 1; } else T[i].r = -1;
}
} else return -1;
for(i=0; i<n; ++i)
if(!A[i]) return i;
}
int same(int r1, int r2) {
if(r1==-1 && r2==-1) return 1;
if((r1==-1&&r2!=-1) || (r1!=-1&&r2==-1) || (T1[r1].p!=T2[r2].p)) return 0;
if(T1[r1].l==-1 && T2[r2].l==-1) return same(T1[r1].r, T2[r2].r);
if(T1[r1].l!=-1 && T2[r2].l!=-1 && T1[T1[r1].l].p==T2[T2[r2].l].p)
return same(T1[r1].l, T2[r2].l)&&same(T1[r1].r, T2[r2].r);
else return same(T1[r1].l, T2[r2].r)&&same(T1[r1].r, T2[r2].l);
}
int main()
{
#ifdef LOCAL
freopen("E:\\Temp\\input.txt", "r", stdin);
freopen("E:\\Temp\\output.txt", "w", stdout);
#endif
int r1, r2;
r1 = bT(T1), r2 = bT(T2);
if(same(r1, r2)) printf("Yes\n");
else printf("No\n");
return 0;
}03-樹2：List Leaves.
Description:
Given a tree, you are supposed to list all the leaves in the order of top down, and left to right.
Input:
Each input file contains one test case. For each case, the first line gives a positive integer N(≤10) 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, and gives the indices of the left and right children of the node. If the child does not exist, a "-" will be put at the position. Any pair of children are separated by a space.
Output:
For each test case, print in one line all the leaves' indices in the order of top down, and left to right. There must be exactly one space between any adjacent numbers, and no extra space at the end of the line.
SampleInput:
8
1
0
2 7
5
4 6
SampleOutput:
4 1 5
Codes:
//#define LOCAL
#include <cstdio>
#include <queue>
struct N { int d, l, r; };
N s[15]; bool f[15];
void bfs(int r) {
int cnt = 1; std::queue<N> q;
q.push(s[r]);
while(!q.empty()) {
N t = q.front();
if(t.l==-1 && t.r==-1) {
if(cnt == 1) { printf("%d", t.d); ++cnt; }
else printf(" %d", t.d);
}
if(t.l != -1) q.push(s[t.l]);
if(t.r != -1) q.push(s[t.r]); q.pop();
}
printf("\n");
}
int main()
{
#ifdef LOCAL
freopen("E:\\Temp\\input.txt", "r", stdin);
freopen("E:\\Temp\\output.txt", "w", stdout);
#endif
int i, n; char a, b;
scanf("%d", &n);
for(i=0; i<n; ++i) {
s[i].l = s[i].r = -1;
scanf(" %c %c", &a, &b); s[i].d = i;
if(a != '-') { s[i].l = a-'0'; f[a-'0'] = 1; }
if(b != '-') { s[i].r = b-'0'; f[b-'0'] = 1; }
}
int r = -1;
for(i=0; i<n; ++i)
if(!f[i]) { r = i; break; }
bfs(r);
return 0;
}PAT-1086:Tree Traversals Again.
Description:
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.
Input:
Each input file contains one test case. For each case, the first line contains a positive integer N (<=30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N 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:
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.
SampleInput:
6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop
SampleOutput:
3 4 2 6 5 1
Codes:
//#define LOCAL
#include <cstdio>
#include <stack>
#define M 50
int A[M], B[M], C[M];
void traversal(int a, int b, int c, int n) {
if(!n) return;
if(n == 1) { C[c] = A[a]; return; }
int i, l, r, R;
R = A[a], C[c+n-1] = R;
for(i=0; i<n; ++i)
if(B[b+i] == R) break;
l = i, r = n-l-1;
traversal(a+1, b, c, l);
traversal(a+l+1, b+l+1, c+l, r);
}
int main()
{
#ifdef LOCAL
freopen("E:\\Temp\\input.txt", "r", stdin);
freopen("E:\\Temp\\output.txt", "w", stdout);
#endif
int a, b, c, d, i, n;
a = b = c = i = 0;
char s[10]; std::stack<int> S;
scanf("%d", &n);
for(; i<2*n; ++i) {
scanf("%s", s);
if(s[1] == 'u') {
scanf("%d", &d);
A[a++] = d; S.push(d);
} else if(s[1] == 'o') {
B[b++] = S.top(); S.pop();
}
}
traversal(0, 0, 0, n);
for(i=0; i<n; ++i) {
if(i) printf(" ");
printf("%d", C[i]);
}
printf("\n");
return 0;
}
