来源：
/* ******************************************************************************/* <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);}