题目描述

输入一系列整数，建立二叉排序数，并进行前序，中序，后序遍历。

输入

输入第一行包括一个整数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 <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
struct Btree
{
    int x;
    Btree *left;
    Btree *right;
    Btree()
    {
        left=NULL;
        right=NULL;
    }
};
typedef struct Btree Btree;
Btree *root;
int n;
int vis[10000];
  
void Insert(int x,Btree *&r)
{
    if(r==NULL)
    {
        r=new Btree;
        r->x=x;
    }
    else
    {
        if(x<r->x)
        {
            Insert(x,r->left);
        }
        else
        {
            Insert(x,r->right);
        }
    }
}
  
void xian(Btree* r)
{
    if(r==NULL)
    {
        return ;
    }
    printf("%d ",r->x);
    xian(r->left);
    xian(r->right);
}
  
void zhong(Btree* r)
{
    if(r==NULL)
    {
        return ;
    }
    zhong(r->left);
    printf("%d ",r->x);
    zhong(r->right);
}
  
void hou(Btree* r)
{
    if(r==NULL)
    {
        return ;
    }
    hou(r->left);
    hou(r->right);
    printf("%d ",r->x);
  
}
  
int Find(int x,Btree *r)
{
    if(r==NULL)
    {
        return 0;
    }
    else
    {
        if(r->x==x)
        {
            return 1;
        }
        else
        {
            int left= Find(x,r->left);
            int right=Find(x,r->right);
            return left+right;
        }
    }
}
  
  
int main()
{
    while(scanf("%d",&n)==1)
    {
        root=NULL;
        for(int i=0;i<n;i++)
        {
            int x;
            scanf("%d",&x);
            if(Find(x,root)==0)
            {
                Insert(x,root);
            }
        }
        xian(root);
        printf("\n");
        zhong(root);
        printf("\n");
        hou(root);
        printf("\n");
  
    }
    return 0;
}