二叉查找树

/* ******************************************************************************
/* <PRE>
/* 版权所有    : -
/* 模块名      : 查找
/* 文件名      : bitreeSearch.cpp
/* 功能描述    : 二叉排序树
/* 作者        : <xxx>
/* 版本        : 1.0
/* -----------------------------------------------------------------------------
/* 备注        : -
/* -----------------------------------------------------------------------------
/* 修改记录    :
/* 日 期        版本     修改人        修改内容
/* 2011/01/01   1.0      <xxx>         创建
/* </PRE>
****************************************************************************** */
#include  < stdio.h >
#include  < stdlib.h >

/* *****************************************************************************
/* 数据类型和常量定义
/***************************************************************************** */
#define  TRUE        1
#define  FALSE       0
#define  OK          1
#define  ERROR       0
#define  OVERFLOW   -2

typedef  int    Status;   /*  函数结果状态码  */
typedef  int    KeyType;  /*  整型关键字  */

/*  数值型关键字的比较  */
#define  EQ(a, b) ((a) == (b))
#define  LT(a, b) ((a) < (b))


/* *****************************************************************************
/* 数据结构定义
/***************************************************************************** */
/*  数据元素类型定义  */
typedef  struct  {
    KeyType key;    // 关键字域
}ElemType;

/*  二叉树的链式存储结构  */
typedef  struct  BiTNode {
    ElemType data;
     struct  BiTNode  * lchild,  * rchild;
} BiTNode,  * BiTree;


/* *****************************************************************************
/* 函数原型声明
/***************************************************************************** */
Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree  & p);
Status InsertBST(BiTree  & T, ElemType e);
Status DeleteBST(BiTree  & T, KeyType key);
Status Delete (BiTree  & p);

Status Visit(ElemType e);
Status InOrderTraverse(BiTree  & T, Status ( * Visit)(ElemType));



/* ******************************************************************************
/* <FUNC>
/* 函数名   : SearchBST
/* 功能     : 二叉排序树的查找方法
/* 参数     : -
/* 返回值   : -
/* 备注     : 在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素, 若查找
/*            成功, 则指针p指向该数据元素结点, 并返回TRUE, 否则指针p指向查找路径上
/*            访问的最后一个结点并返回FALSE, 指针f指向T的双亲, 其初始调用值为NULL
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree  & p)
{
     if  ( ! T) {p  =  f;  return  FALSE;}                                         // 查找不成功
     else   if  EQ(key, T -> data.key) {p  =  T;  return  TRUE;}                     // 查找成功
     else   if  LT(key, T -> data.key)  return  SearchBST(T -> lchild, key, T, p);   // 在左子树中查找
     else   return  SearchBST(T -> rchild, key, T, p);                           // 在右子树中查找
}

/* ******************************************************************************
/* <FUNC>
/* 函数名   : InsertBST
/* 功能     : 插入元素到二叉排序树中
/* 参数     : -
/* 返回值   : -
/* 备注     : 当二叉排序树T中不存在关键字等于e.key的数据元素时, 插入e并返回TRUE,
/*            否则返回FALSE
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
Status InsertBST(BiTree  & T, ElemType e)
{
    BiTree s; BiTree p;
     if  ( ! SearchBST(T, e.key, NULL, p)) {                   // 查找不成功
        s  =  (BiTree)malloc( sizeof (BiTNode));
        s -> data  =  e;  s -> lchild  =  s -> rchild  =  NULL;
         if  ( ! p) T  =  s;                      // 被插结点*s为新的根结点
         else   if  LT(e.key, p -> data.key) p -> lchild  =  s;   // 被插结点*s为左孩子
         else  p -> rchild  =  s;              // 被插结点*s为右孩子
         return  TRUE;
    }
     else   return  FALSE;     // 树中已有关键字相同的结点, 不再插入
}

/* ******************************************************************************
/* <FUNC>
/* 函数名   : DeleteBST
/* 功能     : 从二叉排序树中删除一个结点
/* 参数     : -
/* 返回值   : -
/* 备注     : 若二叉排序树T中存在关键字等于key的数据元素时, 则删除该数据元素结点,
/*            并返回TRUE; 否则返回FALSE
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
Status DeleteBST(BiTree  & T, KeyType key)
{
     if  ( ! T)  return  FALSE;                          // 不存在关键字等于key的数据元素
     else  {
         if  (EQ(key, T -> data.key)) { return  Delete(T); }  // 找到关键字等于key的数据元素
         else   if  (LT(key, T -> data.key))  return  DeleteBST(T -> lchild, key);
         else   return  DeleteBST(T -> rchild, key);
    }
}

/* ******************************************************************************
/* <FUNC>
/* 函数名   : Delete
/* 功能     : 删除一个结点的过程
/* 参数     : -
/* 返回值   : -
/* 备注     : 从二叉排序树中删除结点p, 并重接它的左或右子树
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
Status Delete (BiTree  & p) {
    BiTree q;  BiTree s;
     if  ( ! p -> rchild) {   // 右子树空则只需重接它的左子树
        q  =  p; p  =  p -> lchild; free(q);
    }
     else   if ( ! p -> lchild) {  // 只需重接它的右子树
        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 -> rchild  =  s -> lchild;            // 重接*q的右子树
         else  q -> lchild  =  s -> lchild;                   // 重接*q的左子树
        delete s;
    }
     return  TRUE;
}


/* ******************************************************************************
/* <FUNC>
/* 函数名   : Visit
/* 功能     : 打印节点数据
/* 参数     : -
/* 返回值   : -
/* 备注     : -
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
Status Visit(ElemType e)
{
    printf( " %d  " , e.key);
     return  OK;
}

/* ******************************************************************************
/* <FUNC>
/* 函数名   : InOrderTraverse
/* 功能     : 中序遍历二叉树
/* 参数     : -
/* 返回值   : -
/* 备注     : -
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
Status InOrderTraverse(BiTree  & T, Status ( * Visit)(ElemType))
{
     if (T){
         if (InOrderTraverse(T -> lchild, Visit))
             if (Visit(T -> data))
                 if (InOrderTraverse(T -> rchild, Visit))
                     return  OK;
                 return  ERROR;
    }
     else
         return  OK;
}


/* ******************************************************************************
/* <FUNC>
/* 函数名   : main
/* 功能     : 测试函数
/* 参数     : -
/* 返回值   : -
/* 备注     : -
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
void  main()
{
    BiTree T  =  NULL; ElemType e;

     int  i, j;
     // 插入元素
     for  (i  =   1 ; i  <=   5 ; i ++ )
    {
        e.key  =  i;
        InsertBST(T, e);
    }
     for  (i  =   - 5 ; i  <=   - 3 ; i ++ )
    {
        e.key  =  i;
        InsertBST(T, e);
    }
    printf( " elems inserted:  " );
    InOrderTraverse(T, Visit);

     // 删除元素
     for  (j  =   - 5 ; j  <=   4 ; j ++ )
    {
        DeleteBST(T, j);
    }
    printf( " \nremaining after delete:  " );
    InOrderTraverse(T, Visit);
}