数据结构_二叉排序树

概念

二叉排序树是一颗特殊的二叉树，它是一颗二叉树但同时满足如下条件：对于树上的任意一个结点，其上的数值必大于等于其左子树上任意结点数值，必小于等于其右子树上任意结点的数值。

由于各个数字插入的顺序不同，所得到的二叉排序树的形态也很可能不同，所以不同的插入顺序对二叉排序树的形态有重要的影响，但其都有一个共同点：若对二叉排序树进行中序遍历，那么其遍历结果必然是一个递增序列，所以通过建立二叉排序树就能对原无需序列进行排序，并实现动态维护。

例3.5 二叉排序树 （1201）

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

输入：输入第一行包括一个整数n(1<=n<=100)。接下来的一行包括n个整数。

输出：可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。每种遍历结果输出一行。每行最后一个数据之后有一个空格。

样例输入：
5
1 6 5 9 8
样例输出：
1 6 5 9 8 
1 5 6 8 9 
5 8 9 6 1

#include<stdio.h>
#include<string.h>
using namespace std;
struct Node{
    Node *lchild;
    Node *rchild;
    int x;
}Tree[];
int loc;
Node *create(){
    Tree[loc].lchild=Tree[loc].rchild=NULL;
    return &Tree[loc++];
}
void preOrder(Node *T){
    printf("%d ",T->x);
    if(T->lchild) preOrder(T->lchild);
    if(T->rchild) preOrder(T->rchild);
}
void postOrder(Node *T){
    if(T->lchild) postOrder(T->lchild);
    if(T->rchild) postOrder(T->rchild);
    printf("%d ",T->x);
}
void inOrder(Node *T){
    if(T->lchild) inOrder(T->lchild);
    printf("%d ",T->x);
    if(T->rchild) inOrder(T->rchild);
}
Node *insert(Node *T,int y){
    if(T==NULL){
        T=create();
        T->x=y;
        return T;
    }
    else if(y>T->x)
        T->rchild=insert(T->rchild,y);
    else 
        T->lchild=insert(T->lchild,y);
    return T;
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        Node *T=NULL;
        loc=;
        while(n--){
            int t;
            scanf("%d",&t);
            T=insert(T,t);
        }
        preOrder(T);
        printf("\n");
        inOrder(T);
        printf("\n");
        postOrder(T);
        printf("\n");
    }
    return ;
}