4933: 二叉排序树
Time Limit: 1 Sec Memory Limit: 32 MB
Submit: 6 Solved: 5
[Submit][Status][Web Board]
Description
输入一系列整数，建立二叉排序数，并进行前序，中序，后序遍历。
Input
输入第一行包括一个整数n(1<=n<=100)。接下来的一行包括n个整数。
Output
可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。每种遍历结果输出一行。每行最后一个数据之后有一个空格。
Sample Input
1
2
2
8 15
4
21 10 5 39
Sample Output
2
2
2
8 15
8 15
15 8
21 10 5 39
5 10 21 39
5 10 39 21
HINT
Source
数据结构高分笔记
【分析】按输入的点建树，然后各个顺序遍历输出就好。模板题。
#include<bits/stdc++.h>
using namespace std;
typedef struct node{int val;struct node *lchild,*rchild;
}Btreenode,*Btree;
Btree insert(Btree &T,int x)
{if(T==NULL){T=new Btreenode;T->lchild=T->rchild=NULL;T->val=x;return T;}else if(x<T->val)T->lchild=insert(T->lchild,x);else if(x>T->val)T->rchild=insert(T->rchild,x);return T;
}
void pre(Btree T)
{if(T){cout<<T->val<<" ";pre(T->lchild);pre(T->rchild);}
}
void in(Btree T)
{if(T){in(T->lchild); cout<<T->val<<" ";in(T->rchild);}
}
void post(Btree T)
{if(T){post(T->lchild);post(T->rchild); cout<<T->val<<" ";}
}
int main()
{int n;while(~scanf("%d",&n)){int x;Btree T=NULL;for(int i=0;i<n;i++){scanf("%d",&x);T=insert(T,x);}//cout<<"pre:\n";pre(T);cout<<endl;//cout<<"in\n";in(T);cout<<endl;//cout<<"post\n";post(T);cout<<endl;}return 0;
}