二叉排序树的定义以及相关操作

二叉排序树：又称二叉查找树（BST，Binary Search Tree）

二叉排序树的性质：左子树节点值 < 根节点值 < 右子树节点值

所以  对一棵二叉排序树进行中序遍历，会得到一个递增的序列

定义二叉排序树的结点

//二叉排序树的结点
typedef struct BSTNode{
    int key;
    struct BSTNode *lchild ,*rchild;
}BSTNode,*BSTree;

二叉排序树的非递归查找值为Key的结点   最坏空间复杂度为 O（1）

//在二叉树中查找值为Key的结点
BSTNode *BST_Search(BSTree T,int key){
     while(T!=NULL&&key!=T->key){      //如果树空或者等于根节点值，就结束循环
         if(key<T->key) T=T->lchild;    //小于，则在左子树上查找
         else T=T->rchild;              //大于，则在右子树上进行查找
     }
     return T;
}

二叉排序树的递归实现查找值为Key的结点     最坏空间复杂度为O（H）H 取决与二叉排序树的高度

//在二叉排序树中查找值为Key的结点，（递归实现）
BSTNode *BSTSearch(BSTree T,int key){
    if(T==NULL)
      return NULL;     //查找失败
    if(key==T->key)
      return T;        //查找成功
    else if(key<T->key)
      return BSTSearch(T->lchild,key);   //在左子树中找
    else 
      return BSTSearch(T->rchild,key);   //在右子树中找
}

 二叉排序树的插入（递归方式实现）

 注意：传入的参数需要使用 引用    而且每次插入的结点都是叶子结点

//在二叉排序树中插入关键字为K的结点（递归实现）

int BST_Insert(BSTree &T,int k){    //注意：传入的参数需要使用引用类型，因为需要返回改变之后的根节点的值
 
    if(T==NULL){              //原树为空，新插入的节点为根节点
       T=(BSTree)malloc(sizeof(BSTNode));
       T->key=k;
       T->lchild=T->rchild=NULL;
       return 1;            //返回1，插入成功
    }
   else if(k==T->key)      //树中存在相同关键字的结点，不进行插入，插入失败，因为二叉排序树中不允许有相同元素的存在
       return 0;
   else if(k<T->key)       //插入到T的左子树
       return BST_Insert(T->lchild,k);
   else                   //插入到T的右子树
       return BST_Insert(T->rchild,k);
}

 二叉树的插入操作（使用非递归实现）

二叉树的构造（就是一个不断插入新节点的过程）

//按照 str[] 中的关键字序列建立二叉排序树
void Creat_BST(BSTree &T,int str[],int n){
   T=NULL;     //初始时T为空树
   int i=0;
   while(i<n){    //依次将每个关键字插入到二叉排序树中
    BST_Insert(T,str[i]);
    i++;
   }
}

 不同的关键字序列可能得到同款二叉树，也可能得到不同款的二叉排序树

二叉排序树的删除

1  要删除的结点是叶节点的情况，则直接进行删除，并不会破坏二叉排序树的性质

2  要删除的结点只有左子树或者只有右子树时，直接让子树替代被删除结点的位置

3  要删除的结点既有左子树，也有右子树的情况时，让被删除结点的 中序 遍历的后继结点替换被删除结点的位置。其中序遍历的后续节点的右子树中最左下结点（该节点一定没有左子树，让被替换结点的右子树直接替代它原来的位置就行）

具体过程可以见下图

 或者使用被删除结点的直接前驱替代被删除的结点（即左子树中最右下的结点）

 二叉排序树的查找效率的分析（一般使用平均查找长度进行评估）

查找效率取决与树的高度