二叉排序树（二叉查找树）_二叉排序树查找成功和不成功最大比较次数

/**************************************************************/
/**                        二叉排序树                          **/
/**************************************************************/
 
#include <stdio.h>
#include <stdlib.h>
 
#define FALSE 0
#define TRUE 1
 
typedef int Boolean;
typedef int ElemType;
 
// 二叉树的二叉链表结点结构定义
typedef struct BiTNode
{
    ElemType data;
    struct BiTNode *lchild, *rchild;   // 左右孩子指针
}BiTNode, *BiTree;
 
/**
 * 递归查找二叉排序树tree中是否存在key
 * 指针front指向tree的双亲，其初始调用值为NULL
 * 若查找成功，则指针p指向该数据元素结点，并返回TRUE；否则指针p指向查找路径上访问的最后一个结点并返回FALSE
 */
Boolean SearchBinarySortTree(BiTree tree, ElemType key, BiTree front, BiTree *p)
{
    if (!tree)  // 查找失败
    {
        *p = front;
        return FALSE;
    }
    else if (tree->data == key)   // 查找成功
    {
        *p = tree;
        return TRUE;
    }
    else if (tree->data < key)
    {
        return SearchBinarySortTree(tree->rchild, key, tree, p);  // 在该结点的右子树继续查找
    }
    else
    {
        return SearchBinarySortTree(tree->lchild, key, tree, p);  // 在该结点的左子树继续查找
    }
}
 
/**
 * 当二叉树tree中不存在关键字等于key的数据元素时，插入key并返回TRUE，否则返回FALSE
 */
Boolean InsertBinarySortTree(BiTree *tree, ElemType key)
{
    BiTree p, s;
 
    if (!SearchBinarySortTree(*tree, key, NULL, &p)) // 不存在关键字为key的数据元素
    {
        s = (BiTree)malloc(sizeof(BiTNode));
        if (!s)
        {
            return FALSE;
        }
        s->data = key;
        s->lchild = s->rchild = NULL;
 
        if (!p)   // p为空则说明二叉查找树为空
        {
            *tree = s; // 作为二叉排序树的根结点
        }
        else if (p->data > key)
        {
            p->lchild = s;   // s结点作为左孩子
        }
        else
        {
            p->rchild = s;   // s结点作为右孩子
        }
        return TRUE;
    }
    return FALSE;            // 已经存在关键字为key的数据元素
}
 
/**
 * 从二叉排序树中删除结点p，并重接它的左或右子树
 */
 Boolean DoDelete(BiTree *p)
 {
     BiTree q, s;
 
     // 右子树为空，则只需要重接它的左子树
     if ((*p)->rchild == NULL)
     {
         q = *p;
         *p = (*p)->lchild;
         free(q);
     }
     else if ((*p)->lchild == NULL)     // 左子树为空，则只需要重接它的右子树
     {
         q = *p;
         *p = (*p)->rchild;
         free(q);
     }
     else     // 左右子树均不为空
     {
         q = *p;
         s = (*p)->lchild;
         while (s->rchild)   // 转左，然后向右到尽头(找到待删除结点的前驱)
         {
             q = s;
             s = s->rchild;
         }
         (*p)->data = s->data;   // s指向被删除结点的直接前驱
         if(q != *p)    // 重接q的右子树
         {
             q->rchild = s->lchild;  // 重接q的右子树
         }
         else
         {
             q->lchild = s->lchild;  // 重接q的左子树
         }
         free(s);
     }
     return TRUE;
 }
 
/**
 * 若二叉排序树tree中存在关键字等于key的数据元素时，则删除该元素结点，并返回TRUE，否则返回FALSE
 */
Boolean DeleteBinarySortTree(BiTree *tree, ElemType key)
{
    if (!tree)    // 不存在关键字等于key的数据元素
    {
        return FALSE;
    }
    else
    {
        if (key == (*tree)->data)    // 找到关键字等于key的数据元素
        {
            return DoDelete(tree);
        }
        else if (key < (*tree)->data)
        {
            return DeleteBinarySortTree(&(*tree)->lchild, key);
        }
        else
        {
            return DeleteBinarySortTree(&(*tree)->rchild, key);
        }
    }
}
 
int main()
{
    int i;
    Boolean bole;
    ElemType data[10] = {62, 88, 58, 47, 35, 73, 51, 99, 37, 93};
 
    BiTree tree = NULL, p;
 
    for (i = 0; i < 10; i++)
    {
        InsertBinarySortTree(&tree, data[i]);
    }
 
    bole = SearchBinarySortTree(tree, 99, NULL, &p);
    if (bole == TRUE)
    {
        printf("查找成功\n");
    }
    else
    {
        printf("查找失败\n");
    }
 
    bole = DeleteBinarySortTree(&tree, 99);
    if (bole == TRUE)
    {
        printf("删除成功\n");
    }
    else
    {
        printf("删除失败\n");
    }
 
    return 0;
}