Problem description 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. Pre-order traversal (Root-Left-Right) prints out the nodes 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 50 30 24 5 28 45 98 52 60 Sample Output 5 28 24 45 30 60 52 98 50 题意 给一个序列，让它以二叉树排序树的形式插入，即:遇到值比他小的往左子树插入，否则往右子树插入，输出他的后续遍历序列。 思路 建议大家能用数组的时候尽量开固定大小的数组，因为用指针去写的话申请内存耗时间，而且有的题目还可能内存超限，情况比较少就是了。这里先给出指针形式再给出数组形式代码。 图一是数组方法，图二是指针方法，比较两者时间，可想而知。 方法一
#include<iostream> #include<stdio.h> using namespace std; struct tree { int data; tree *l=NULL,*r=NULL; }; void _insert(tree *&T,int e) { if(!T) { tree *S=new tree; S->data=e; T=S; }else if(e<T->data){ _insert(T->l,e); }else{ _insert(T->r,e); } } void _print(tree *&T) { if(T){ _print(T->l); _print(T->r); printf("%d\n",T->data); } } int main() { int e; tree *T=NULL; while(~scanf("%d",&e)){ _insert(T,e); } _print(T); return 0; }方法二
#include<cstdio> #include<cstring> #include<algorithm> const int maxn = 1e6 + 10; using namespace std; int son[maxn][2]; int n, root = 0; void __insert(int val, int &x) { if(x==0){ x=val; return ; } if(val < x) __insert(val, son[x][0]); else __insert(val, son[x][1]); } void dfs(int o) { if(o==0) return ; dfs(son[o][0]); dfs(son[o][1]); printf("%d\n", o); } int main() { while(scanf("%d", &n) != EOF) __insert(n, root); dfs(root); return 0; }练习网址：https://cn.vjudge.net/problem/UVA-12347
