/********************************
运行环境：http://www.anycodes.cn/zh/
原文：http://blog.csdn.net/u014488381/article/details/41719765/
二叉排序树的查找算法的C代码实现
修改以直接测试
待C++类封装版本
*********************************/
#include
#include
typedef int Elemtype;
typedef struct BiTNode{
Elemtype data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
/*/在给定的BST中插入结点，其数据域(数值)为element/*/
void BSTInsert( BiTree *t, Elemtype element )
{/*/每次插入 开辟空间/*/
if( NULL == *t ) {
(*t) = (BiTree)malloc(sizeof(BiTNode));
(*t)->data = element;
(*t)->lchild = (*t)->rchild = NULL;
}
/*/依据二叉搜索树性质/*/
if( element == (*t)->data ) return ; /*/不允许有重复的数据，若遇到直接不处理/*/
else if( element < (*t)->data ) BSTInsert( &(*t)->lchild, element );
else BSTInsert( &(*t)->rchild, element );
}
/*/创建BST/*/
void CreateBST( BiTree *t, Elemtype *a, int n )
{
(*t) = NULL;
for( int i=0; idata )
printf("查找成功!\n");
else if( (key < p->data) && (NULL != p->lchild) )
SearchBST( p->lchild , key );
else if( (key > p->data) && (NULL != p->rchild) )
SearchBST( p->rchild , key );
else
printf("无此元素!\n");
}
}
/*/BST的迭代查找/*/
void _SearchBST( BiTree t, Elemtype key )
{
BiTree p; p = t;
while( NULL != p && key != p->data ) /*/结点存在而数值不等时/*/
{
if( key < p->data ) p = p->lchild ;
else p = p->rchild ;
}/*/ 走出循环后 p指针总是指向找到的元素 或者 叶子结点下的空结点/*/
if( NULL != p ) printf("查找成功!\n");
else printf("无此元素!\n");
}
/*/BST结点的删除 本二叉树内容重点/*/
void DelBSTNode( BiTree t, Elemtype key )
{
BiTree p, q;
p = t;
Elemtype temp;
/*/ 先遍历找这元素/*/
while( NULL != p && key != p->data ) {
q = p; /*/ q总是在结点p的上方（当p不是根结点时q总是父亲）
p就是我们要删的元素
/*/
if( key < p->data ) p = p->lchild ;
else p = p->rchild ;
}
if( NULL == p ) printf("无此元素!\n");
/*/找到元素 会有如下几个情况
1. 2. 3.
q q q
/\ / \ / \
p p p p p p
/ \ / \ / \
x x x x x x
/*/
else {
/*/情况1:结点p的双亲结点为q，且p为叶子结点，则直接将其删除。/*/
if( NULL == p->lchild && NULL == p->rchild ) {
if( p == q->lchild ) q->lchild = NULL;
if( p == q->rchild ) q->rchild = NULL;
free(p);
p = NULL;
}
/*/情况2:结点p的双亲结点为q，且p只有左子树或只有右子树，
则可将p的左子树或右子树直接改为其双亲结点q的左子树或右子树。/*/
else if( (NULL == p->rchild && NULL != p->lchild) ) { /*/p只有左子树/*/
if( p == q->lchild ) q->lchild = p->lchild ;
else if( p == q->rchild ) q->rchild = p->lchild ;
free(p);
p = NULL;
}
else if( NULL == p->lchild && NULL != p->rchild ) { /*/p只有右子树/*/
if( p == q->lchild ) q->lchild = p->rchild ;
if( p == q->rchild ) q->rchild = p->rchild ;
free(p);
p = NULL;
}
/*/情况3:结点p的双亲结点为q，且p既有左子树又有右子树。
本代码使用直接前驱（也可以直接后继）这里找的是左子树中最大的元素/*/
else if( NULL != p->lchild && NULL != p->rchild ) {
BiTree s, sParent;
sParent = p;
s = sParent->lchild ;
while( NULL != s->rchild ) {/*/找到p的直接前驱/*/
sParent = s;
s = s->rchild ; /*/左子树最大的总是在左子树中最右下角/*/
}
temp = s->data ; /*/此时 s指向的是最大的右下叶子结点 为一般情况1 直接删除/*/
DelBSTNode( t, temp );
p->data = temp; /*/最后将原来要删除的p的数据改为temp/*/
}
}
}
/*/
待递归版本的删除 传引用的妙处
中序遍历打印BST/*/
void PrintBST( BiTree t )
{
if( t ) {
PrintBST( t->lchild );
printf("%d ", t->data);
PrintBST( t->rchild );
}
}
void use()
{
int n;
int *a;
Elemtype key;
BiTree t;
printf("请输入二叉查找树的结点数:\n");
scanf("%d", &n);
a = (int *)malloc(sizeof(int)*n);
printf("请输入二叉找树的结点数据:\n");
for( int i=0; i
标题名称：小代码向原文学习BST简单的C语言版本
文章链接：http://cdxtjz.cn/article/pjsooe.html
