定义：一颗二叉排序树（BST）是一棵二叉树，其中的每个节点都包含一个Comparable的键（以及相关联的值），并且每个键都大于其左子树中的任意键而小于右子数的任意结点的键。

复杂度：一个由N个随机键构造的二叉排序树，查找的平均所需比较次数为~2lgN（约1.39lgN）。

         接下来是完整的代码，包括二叉树的创建，插入，遍历，删除

1 #include
     
        2 #include
      
         3 #ifdef _DEBUG  4 #define new DEBUG_NEW  5 #undef THIS_FILE  6 static char THIS_FILE[] = __FILE__;  7 #endif  8 #define ARRAYLEN 10  9 int source[]={
   54,90,6,69,12,37,92,28,65,83}; 10     typedef struct bst 11     { 12         int data; 13         struct bst *left; 14         struct bst *right; 15     }BSTree; 16 void InsertBST(BSTree *t,int key)//在二叉树中插入查找关键字key； 17 { 18     BSTree *p,*parent,*head; 19     if(!(p=(BSTree*)malloc(sizeof(BSTree *))))//判断分配内存空间是否成功； 20     { 21         printf("申请内存出错！\n"); 22         exit(0); 23     } 24     p->data=key;//保存节点数据 25     p->left=p->right=NULL;//左右子树置空 26     head=t; 27     while(head)//查找需要添加的父节点 28     {  29         parent=head; 30         if(key
       
        data)//若关键字小于节点数据 31           head=head->left; 32         else 33             head=head->right; 34     } 35         //判断添加到左子树还是右子树 36         if(key
        
         data)//小于父节点 37             parent->left=p;//添加到左子树； 38         else 39             parent->right=p; 40 } 41 BSTree *SearchBST(BSTree *t,int key) 42 { 43     if(!t||t->data==key)//节点为空或者关键字相等 44        return t;//返回结点指针 45     else if (key>t->data)//关键字大于结点数据 46         return (SearchBST(t->right,key)); 47     else 48         return (SearchBST(t->left,key)); 49 } 50 void CreateBST(BSTree *t,int data[],int n)//n个数据在数组中，tree为二叉树根 51 { 52     int i; 53     t->data=data[0]; 54     t->left=NULL; 55     t->right=NULL; 56     for(i=1;i
         
          left);//中序遍历左子树 66         printf("%d  ",t->data);//输出结点数据 67         BST_LDR(t->right);//中序遍历右子树 68     } 69     return; 70 } 71 void BST_Delete(BSTree *t,int key) 72 { 73     BSTree *p,*parent,*l,*l1; 74     int child=0;//0表示左子树，1表示又子树 75     if(!t) return ;//二叉排序树为空，则退出 76     p=t; 77     parent=p; 78     while(p)//二叉排序树有效 79     { 80         if(p->data==key) 81         { 82             if(!p->left && !p->right)//叶节点（左右子树都为空） 83             { 84                 if(p==t)//被删除的是根结点 85                 { 86                     free(p); 87                 } 88                 else if (child==0)//父节点为左子树 89                 { 90                     parent->left=NULL;//设置父结点左子树为空； 91                     free(p); 92                 } 93                 else//父节点为右子树 94                 { 95                     parent->right=NULL;//设置父结点右子树为空； 96                     free(p); 97                 } 98             } 99                  if (!p->left)//左子树为空，右子数不为空100                 {101                     if(child==0)//是父结点的左子树102                         parent->left=p->right;103 104                    else  //是父结点的右子树105                         parent->left=p->left;106                    free(p);107                 }108                else if (!p->right)//右子树为空，左子数不为空109                 {110                     if(child==0)//是父结点的左子树111                         parent->right=p->right;112 113                    else  //是父结点的右子树114                         parent->right=p->left;115                    free(p);116                 }117                 else//左右子树都不为空118                 {119                     l1=p;//保存左子树的父节点120                     l=p->right;//当前节点的右子数开始查找121                    while(l->left)//左子树不为空122                    {123                        l1=l;124                        l=l->left;//查找左子树；125                    }126                    p->data=l->data;//将左子树的数据保存到被删除的节点127                    l1->left=NULL;//设置父结点的左子树指针为空128                    free(l1);//释放左子树占的内存空间129                 }130                 p=NULL;131             }132             else if(key
          
           data)//需删除记录的关键字小于节点的数据133 {134 child=0;//标记在当前结点左子树查找135 parent=p;//保存当前结点为父节点136 p=p->left;137 }138 else //需删除记录的关键字大于节点的数据139 {140 child=1;//标记在当前结点右子树查找141 parent=p;//保存当前结点为父节点142 p=p->right;143 }144 }145 }146 147 148 int main()149 {150 int i,key;151 BSTree bst,*pos;//保存二叉树的根结点152 printf("原始数据");153 for(i=0;i
          
         
        
       
      
     

注意点：在二叉排序树中，删除操作对应着多种不同情况（这几种情况在代码中均有体现）：

  （1） 删除元素是叶节点；

  （2） 删除元素有左子树，无右子数

  （3） 删除元素有右子树，无左子数

  （4） 删除元素有左子树，右子数