[UVA] 12347 - Binary Search Tree
A binary search tree is a binary tree that satisfies the following properties:
· The left subtree of a node contains only nodes with keys less than the node's key.
· The right subtree of a node contains only nodes with keys greater than the node's key.
· Both the left and right subtrees must also be binary search trees.
Figure 1. Example binary search tree
Pre-order traversal (Root-Left-Right) prints out the node’s key by visiting the root node then traversing the left subtree and then traversing the right subtree. Post-order traversal (Left –Right-Root) prints out the left subtree first and then right subtree and finally the root node. For example, the results of pre-order traversal and post-order traversal of the binary tree shown in Figure 1 are as follows:
Pre-order: 50 30 24 5 28 45 98 52 60
Post-order: 5 28 24 45 30 60 52 98 50
Given the pre-order traversal of a binary search tree, you task is to find the post-order traversal of this tree.
Input
The keys of all nodes of the input binary search tree are given according to pre-order traversal. Each node has a key value which is a positive integer less than 106. All values are given in separate lines (one integer per line). You can assume that a binary search tree does not contain more than 10,000 nodes and there are no duplicate nodes.
Output
The output contains the result of post-order traversal of the input binary tree. Print out one key per line.
|
Sample input |
Sample output |
|
50 30 24 5 28 45 98 52 60
|
5 28 24 45 30 60 52 98 50 |
作法 : 按照順序分成兩個區塊, 這就意味著我們需要找尋最鄰近且比根大的節點
例如 :
範例輸入
50 30 24 5 28 45 98 52 60 對於 50 來說, 98 是最鄰近且大於 50
則 50 [30 24 5 28 45][98 52 60] 最後輸出 50
30 [24 5 28][45] 對 30 來說 45 是最鄰近且大於 30, 最後輸出 30
...
採用了 Sparse Table 完成了 O(nlogn*logn),
避免了O(n*n)的最慘結果
#define L 10000
int SparseTable[L][15], A[L]; /*2^14 = 16384 >= L*/
int Max(int x, int y) {
return x > y ? x : y;
}
int Build(int *A, int n) {
int i, t, k;
for(i = 0; i < n; i++)
SparseTable[i][0] = A[i];
for(k = 1, t = 2; t <= n; k++, t <<= 1)
for(i = 0; i+t <= n; i++)
SparseTable[i][k] = Max(SparseTable[i][k-1], SparseTable[i+(t>>1)][k-1]);
}
void PostOrder(int i, int n) {
int k, t, st = i, cut;
if(i > n) return;
while(1) {
cut = -1;
for(k = 1, t = 2; st+t <= n; k++, t <<= 1)
if(SparseTable[st][k] > SparseTable[st][0]) {
cut = 1;
break;
}
if(SparseTable[st][0] > SparseTable[i][0])
{cut = 0;break;}
if(cut == -1 && st > n) break;
st = st + (t>>1);
}
if(cut != -1) {
PostOrder(i+1, st-1);
PostOrder(st, n);
} else {
PostOrder(i+1, n);
}
printf("%d\n", A[i]);
}
int main() {
int i = 0;
while(scanf("%d", &A[i]) == 1)
i++;
Build(A, i);
PostOrder(0, i-1);
return 0;
}