二叉排序树，简单的意思是这样的，先创建一个根节点，然后一次判断新增节点，比根节点大的放左边，比根节点小的放右边，以此类推。
二叉排序树的基本操作有：
1. 初始化。其实也就是创建一个根节点。（Init_BST)
2. 增加节点。 (insert_BST)
3. 删除节点。 (delete_BST)
4. 遍历节点。 (show_BST)
5. 显示最小节点。 (FindMin)
6. 显示最大节点。 (FindMax)
以上6个基本操作中，比较复杂的是删除节点操作，其他的则较为容易理解。下面给出类型声明，以及基本操作的代码。（在Linux下，通过gcc编译，请放心使用。)
============================================================================================
类型声明 && 函数声明：
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int data; //数据域
struct node *left; //左指针
struct node *right; //右指针
}sort_node,*sort_link;
sort_link Init_BST(void); //初始化二叉排序树
sort_link insert_BST(int,sort_link *); //增加节点操作
sort_link delete_BST(int,sort_link *); //删除节点操作
sort_link FindMin(sort_link); //显示最小节点
sort_link FindMax(sort_link); //显示最大节点
void show_BST(sort_link); //显示节点操作
==============================================================================================
Main 函数:
int main(void)
{
sort_link head = NULL; //设置一个头指针
head = Init_BST(); //先初始化二叉排序树
/*开始新增节点*/
printf(" Now you can input other numbers,enter -1 for quit:/n");
int num = 0;
scanf("%d",&num);
while(num != -1) //循环新增节点直到用户输入 -1 结束为止
{
insert_BST(num,&head); //这里用到了二级指针，这是因为head即是一个指针，同时自己本身也是一个变量。我们
这里是要修改指针的指向，所以所以要传一级指针的地址。
scanf("%d",&num);
}
printf("Insert Operation finished.../n");
/*显示所有节点*/
show_BST(head); //不需要修改，只需要一级指针
printf("/n");
/*显示最小节点*/
sort_link Min_BST = FindMin(head);
printf("The Min in BST = %d/n",Min_BST->data);
/*显示最大节点*/
sort_link Max_BST = FindMax(head);
printf("The Max in BST = %d/n",Max_BST->data);
/*删除节点操作*/
printf("please enter the num you want to delete:/n");
int del_num = 0;
scanf("%d",&num);
delete_BST(del_num,&head);
/*打印删除完指定节点后的所有节点*/
printf("Now elements in BST are:/n");
show_BST(head);
printf("/n");
return 0;
}
===============================================================================================
初始化操作
sort_link Init_BST(void)
{
printf("please enter a number for creating the root.../n");
int root = 0;
scanf("%d",&root);
sort_link s = (sort_link)malloc(sizeof(sort_node)); //新建一个节点
s->data = root; //将数据域设置为 root
s->left = NULL; //左右指针都设置为空
s->right = NULL;
return s; //返回指针s
}
================================================================================================
增加节点操作
sort_link insert_BST(int num, sort_link *s)
{
if((*s) == NULL) //如果没有节点，这里类似于初始化
{
(*s) = (sort_link)malloc(sizeof(sort_node));
if((*s) == NULL)
{
printf("malloc error .../n");
exit(0);
}
else
{
(*s)->data = num;
(*s)->left = NULL;
(*s)->right = NULL;
}
}
/*如果有节点*/
{
if(num < (*s)->data)
{
return insert_BST(num,(*s)->left); //如果插入的节点小于根节点，那么递归的向左子树插
}
else if(num > (*s)->data)
{
return insert_BST(num,(*s)->right); //如果插入的节点大于根节点，那么递归的向右子树插
}
}
}
==================================================================================================
遍历节点操作，其实就是二叉树的遍历，我们这里用的是中序遍历，对于二叉排序树而言，中序遍历就是从小到大排序
void show_BST(sort_link s)
{
if (s == NULL)
return;
show_BST(s->left);
printf("%d",s->data);
show_BST(s->right);
}
===================================================================================================
显示最小节点操作
sort_link FindMin(sort_link s)
{
/*由二叉排序树的特点所知，最小的节点肯定在整棵树的最左端*/
while((s->left) != NULL)
{
s = s->left;
}
return s;
}
====================================================================================================
显示最大节点操作
sort_link FindMax(sort_link s)
{
/*同上*/
while((s->right) != NULL)
{
s = s->right;
}
return s;
}
=====================================================================================================
删除节点操作
删除节点的操作较为复杂，主要考虑以下几种情况：
1. 该节点为叶子，这种比较简单，直接free掉就可以了。
2. 该节点有一个孩子。对于这种情况，如果只有左孩子，那么就把指针指向左孩子；只有右孩子，就把指针指向右孩子。
3. 如果该节点有2个孩子，对于这种情况，就从他的右子树中，找到一个最小的节点，来替换掉该节点，然后再把右子树中那个最小
节点删除掉，使该节点的右指针指向这棵新的右子树。
具体实现代码如下：
sort_link delete_BST(int num,sort_link *s)
{
/*先在树中找到要删除的节点*/
if(num <(*s)->data)
{
(*s)->left = delete_BST(num,&((*s)->left); //如果要删除的节点小于根节点，则递归的往左走。
}
if(num > (*s)->data)
{
(*s)->right = delete_BST(num,&((*s)->right); //如果要删除的节点小于根节点，则递归的往右走。
}
/*找到了要删除的节点。第一种情况：该节点有2个孩子*/
else if((*s)->left && (*s)->right)
{
/*在右子树中，找出一个最小的节点,让一个tmp记录下这个最小节点*/
sort_link tmp = FindMin((*s)->right);
/*用最小节点的值替换要删除的节点*/
(*s)->data = tmp->data;
/*在右子树中删除这个最小节点，考虑到这个最小节点下面还有子树，用递归的方法。最后将要删除节点
的右指针指向这棵新树*/
(*s)->right = delete_BST(tmp->data,&((*s)->right));
}
/*第二种情况：该节点有一个孩子*/
else
{
sort_link tmp = (*s);
/*如果该节点没有左孩子*/
if((*s)->left == NULL)
{
(*s) = (*s)->right;
free(tmp);
}
/*如果该节点没有右孩子*/
else if((*s)->right == NULL)
{
(*s) = (*s)->left;
free(tmp);
}
/*第三种情况：是叶子，没有孩子，直接free*/
free(tmp);
}
return *s; /*不要忘记返回*/
}
=====================================================================================================
(完)
