1002. 二叉查找树的遍历

Total:

111

Accepted:

73

	Time Limit: 1sec    Memory Limit:256MB Description 给定一组无序整数，以第一个元素为根节点，生成一棵二叉搜索树，对其进行中序遍历和先序遍历。 Input 输入包括多组测试数据，每组测试数据包含两行：第一行为整数m(1<=m<=3000)，表示该组数据中整数的数目，第二行给出m个整数，相邻整数间用一个空格间隔。最后一组测试数据后紧跟着包含0的一行输入，标识输入的结束。 Output 每组测试数据产生两行输出，第一行是中序遍历结果，第二行是先序遍历结果，每个整数后面带一个空格（包括最后一个整数），每行中第一个整数前无空格。 Sample Input  Copy sample input to clipboard 910 4 16 9 8 15 21 3 12620 19 16 15 45 480 Sample Output 3 4 8 9 10 12 15 16 2110 4 3 9 8 16 15 12 2115 16 19 20 45 4820 19 16 15 45 48

#include
      
       using namespace std;struct BitNode{	int data;	BitNode* lchild;	BitNode* rchild;};//重建二叉查找树void build(BitNode* T, int num){	//if bigger than the root	if(T->data>num)	{		if(!T->lchild)  //if no have left son		{			BitNode* lt=new BitNode();			lt->data=num;			lt->lchild=NULL;			lt->rchild=NULL;			T->lchild=lt;		}		else          // if have left son, recurise			build(T->lchild, num);	}	else   //if smaller than the root	{		if(!T->rchild)		{			BitNode* rt=new BitNode();			rt->data=num;			rt->lchild=NULL;			rt->rchild=NULL;			T->rchild=rt;		}		else			build(T->rchild, num);	}}//前序遍历void preorder(BitNode* T){	if(T)	{		cout<
       
        data<<" ";		preorder(T->lchild);		preorder(T->rchild);	}}//中序遍历void inorder(BitNode* T){    if(T)    {    	inorder(T->lchild);    	cout<
        
         data<<" ";        inorder(T->rchild);    }}int main(){    int n;    while(cin>>n&&n)    {    	int num;        BitNode* T=new BitNode();        cin>>num;        T->data=num;        T->lchild=NULL;        T->rchild=NULL;        while(--n>0)        {        	cin>>num;        	build(T, num);        }        inorder(T);        cout<