题目描述
输入一系列整数，建立二叉排序数，并进行前序，中序，后序遍历。
输入
输入第一行包括一个整数n(1<=n<=100)。接下来的一行包括n个整数。
输出
可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。每种遍历结果输出一行。每行最后一个数据之后有一个空格。
样例输入
1
2
2
8 15
4
21 10 5 39
样例输出
2
2
2
8 15
8 15
15 8
21 10 5 39
5 10 21 39
5 10 39 21 分析：按照题意建立二叉排序树即可，注意二叉排序树中没有相等的元素。
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <queue>
#include <stack>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#include<unordered_map>
#define INF 0x3f3f3f3f
#define db1(x) cout<<#x<<"="<<(x)<<endl
#define db2(x,y) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<endl
#define db3(x,y,z) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<endl
#define db4(x,y,z,a) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#a<<"="<<(a)<<endl
#define db5(x,y,z,a,r) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#a<<"="<<(a)<<", "<<#r<<"="<<(r)<<endl
using namespace std;typedef struct node
{int val;struct node *left,*right;
}node;void Free(node *p)
{if(p==NULL)return;Free(p->left);Free(p->right);free(p);return;
}void pre_order(node *p)
{if(p==NULL)return;printf("%d ",p->val);pre_order(p->left);pre_order(p->right);
}void in_order(node *p)
{if(p==NULL)return;in_order(p->left);printf("%d ",p->val);in_order(p->right);
}void post_order(node *p)
{if(p==NULL)return;post_order(p->left);post_order(p->right);printf("%d ",p->val);
}int main(void)
{#ifdef testfreopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);clock_t start=clock();#endif //testint n;while(~scanf("%d",&n)){node *root=NULL;for(int i=0;i<n;++i){int a;scanf("%d",&a);node *p=(node*)malloc(sizeof(node));p->val=a;p->left=p->right=NULL;if(!i)root=p;else{node *temp=root;while(1){if(a>temp->val){if(temp->right==NULL){temp->right=p;break;}else temp=temp->right;}else if(a<temp->val){if(temp->left==NULL){temp->left=p;break;}else temp=temp->left;}else break;}}}pre_order(root);printf("\n");in_order(root);printf("\n");post_order(root);printf("\n");Free(root);}#ifdef testclockid_t end=clock();double endtime=(double)(end-start)/CLOCKS_PER_SEC;printf("\n\n\n\n\n");cout<<"Total time:"<<endtime<<"s"<<endl; //s为单位cout<<"Total time:"<<endtime*1000<<"ms"<<endl; //ms为单位#endif //testreturn 0;
}
