主要内容 #

1. 二叉排序树知识点回顾
2. 二叉排序树习题练习

1. 二叉排序树知识点回顾 #

二叉排序树本质是一棵二叉树，它的特别之处在于：

1. 对于树中的每个结点，如果它有左子树，那么左子树上所有结点的值都比该结点小；
2. 对于树中的每个结点，如果它有右子树，那么右子树上所有结点的值都比该结点大。

举个简单的例子，下图就是一棵二叉排序树：

以根节点为例，左子树上所有结点的值都比 45小，右子树上所有结点的值都比 45大。不仅是根结点，整棵二叉树上的非叶子结点都是如此，这样的二叉树就是一棵二叉排序树。

2. 二叉排序树习题练习 #

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

2.2 输入：
输入第一行包括一个整数 n(1<=n<=100)。接下来的一行包括 n 个整数。 2.3 输出： 可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树， 并对二叉排序树进行前序、中序和后序遍历。每种遍历结果输出一行。每行最后 一个数据之后有一个空格。

2.4 样例输入：

5

1 6 5 9 8

2.5 样例输出：

1 6 5 9 8

1 5 6 8 9

5 8 9 6 1

2.6 提示：

输入中可能有重复元素，但是输出的二叉树遍历序列中重复元素不用输出。

2.7 示例程序：

#include<stdio.h>
#include<string.h>
struct Node{        //二叉树结构体
    Node *lchild;   //左儿子指针
    Node *rchild;   //右儿子指针
    int c;          //保存数字
}Tree[110];         //静态数组
 
int loc;            //静态数组中被使用元素个数
Node *creat()       //申请未使用的结点
{
    Tree[loc].lchild=Tree[loc].rchild=NULL;//初始化左右儿子为空
    return &Tree[loc++];//返回指针，且loc累加
}
void postOrder(Node *T)  //后序遍历
{
    if(T->lchild!=NULL)
    {
        postOrder(T->lchild);
    }
    if(T->rchild!=NULL)
    {
        postOrder(T->rchild);
    }
    printf("%d ",T->c);
}
void inOrder(Node *T)  //中序遍历
{
    if(T->lchild!=NULL)
    {
        inOrder(T->lchild);
    }
    printf("%d ",T->c);
    if(T->rchild!=NULL)
    {
        inOrder(T->rchild);
    }
}
void preOrder(Node *T)  //前序遍历
{
    printf("%d ",T->c);
    if(T->lchild!=NULL)
    {
        preOrder(T->lchild);
    }
    if(T->rchild!=NULL)
    {
        preOrder(T->rchild);
    }
}
Node *Insert(Node *T,int x)//插入数字
{
    if(T==NULL)     //若当前树为空
    {
        T=creat();  //建立结点
        T->c=x;     //数字直接插入其根结点
        return T;   //返回根结点指针
    }
    else if(x<T->c) //若x小于根结点数值
    {
        T->lchild=Insert(T->lchild,x);//插入到左子树上
    }
    else if(x>T->c) //若x大于根结点数值
    {
        T->rchild=Insert(T->rchild,x);//插入到右子树上，若根结点数值与x一样，根据题目要求直接忽略
    }
    return T;       //返回根结点指针
 
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        loc=0;
        Node *T=NULL;   //二叉排序树树根结点为空
        for(int i=0;i<n;i++)//依次输入n个数字
        {
            int x;
            scanf("%d",&x);
            T=Insert(T,x);//插入到排序树中
        }
        preOrder(T);    //前序遍历
        printf("\n");   //输出空行
        inOrder(T);     //中序遍历
        printf("\n");
        postOrder(T);   //后序遍历
        printf("\n");
    }
    return 0;
}