/*
功能，数据结构C语言版V2cn，P227，二叉排序树
可以进一步学习《算法导论V2cn》第12章 二叉查找树。
日期，2012年10月30日
博客，http://blog.csdn.net/shunqiziranhao007/article/details/7816771
环境，win7-32-vs2010
*/
#include <stdio.h>
#include <malloc.h>
// 数据元素个数
#define N 10
typedef int KeyType;
typedef struct
{
KeyType key;
int others;
} ElemType;
// 树的元素类型
typedef ElemType TElemType;
// 二叉树的二叉链表存储表示
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
// 构造一个空的动态查找表DT
int InitDSTable(BiTree *DT)
{
*DT = NULL;
return 1;
}
// 销毁动态查找表DT
void DestroyDSTable(BiTree *DT)
{
if(*DT)
{
if((*DT)->lchild)
// 递归销毁
DestroyDSTable(&(*DT)->lchild);
if((*DT)->rchild)
DestroyDSTable(&(*DT)->rchild);
free(*DT);
*DT = NULL;
}
}
// 算法9.5(a) P228
// 在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素，
// 若查找成功，则返回指向该数据元素结点的指针,否则返回空指针。
BiTree SearchBST(BiTree T, KeyType key)
{
if ( (!T) || (key == T->data.key) )
{
return T;
}
else if ( key < T->data.key )
{
// 在左子树中继续查找
return SearchBST(T->lchild,key);
}
else
{
return SearchBST(T->rchild,key);
}
}
// 算法9.5(b) P228
// 在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素，若查找
// 成功，则指针p指向该数据元素结点，并返回1，否则指针p指向查找路径上
// 访问的最后一个结点并返回0,指针f指向T的双亲，其初始调用值为NULL
void SearchBST1(BiTree *T, KeyType key, BiTree f, BiTree *p, int *flag)
{
if(!*T) // 查找不成功
{
*p = f;
*flag = 0;
}
else if(key == (*T)->data.key) // 查找成功
{
*p = *T; //指针p指向该数据元素结点
*flag = 1;
}
else if(key < (*T)->data.key)
SearchBST1(&(*T)->lchild,key,*T,p,flag); // 在左子树中继续查找
else
SearchBST1(&(*T)->rchild,key,*T,p,flag); // 在右子树中继续查找
}
// 算法9.6 P228
// 当二叉排序树T中不存在关键字等于e.key的数据元素时，插入e并返回1，否则返回0。
int InsertBST(BiTree *T, ElemType e)
{
BiTree p,s;
int flag;
SearchBST1(T, e.key, NULL, &p, &flag);
if(!flag) // 查找不成功
{
s = (BiTree)malloc(sizeof(BiTNode));
s->data = e;
s->lchild = s->rchild = NULL;
if( !p )
{
// 被插结点*s为新的根结点
*T = s;
}
else if(e.key < p->data.key)
{
// 被插结点*s为左孩子,值小的在左边
p->lchild = s;
}
else
{
// 被插结点*s为右孩子,值大的在右边
p->rchild = s;
}
return 1;
}
else
{
// 树中已有关键字相同的结点，不再插入
return 0;
}
}
// 算法9.8 P231
// 从二叉排序树中删除结点p，并重接它的左或右子树。
void Delete(BiTree *p)
{
// 中介，辅助删除结点
BiTree q, 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;
}
// s指向被删结点的＂前驱＂（将被删结点前驱的值取代被删结点的值）
(*p)->data = s->data;
if(q != *p)
q->rchild = s->lchild; // 重接*q的右子树
else
q->lchild = s->lchild; // 重接*q的左子树
free(s);
}
}
// 算法9.7 P230
// 若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点，
// 并返回1；否则返回0。
int DeleteBST(BiTree *T, KeyType key)
{
if(!*T) // 不存在关键字等于key的数据元素
return 0;
else
{
if(key == (*T)->data.key) // 找到关键字等于key的数据元素
Delete(T);
else if(key < (*T)->data.key)
DeleteBST(&(*T)->lchild,key);
else
DeleteBST(&(*T)->rchild,key);
return 1;
}
}
// 按关键字的顺序对DT的每个结点调用函数Visit()一次
void TraverseDSTable(BiTree DT, void(*Visit)(ElemType))
{
if(DT)
{
// 像这样遍历，最后结果是个非递减顺序
TraverseDSTable(DT->lchild,Visit); // 先中序遍历左子树
Visit(DT->data); // 再访问根结点
TraverseDSTable(DT->rchild,Visit); // 最后中序遍历右子树
}
}
void print(ElemType c)
{
printf("(%d,%d) ", c.key, c.others);
}
int main()
{
BiTree dt,p;
int i;
KeyType j;
// 以教科书P227图9.7(a)为例
ElemType r[N] =
{
{45,1}, {12,2}, {53,3}, {3,4}, {37,5},
{24,6}, {100,7}, {61,8}, {90,9}, {78,10}
};
// 构造空表
InitDSTable(&dt);
// 依次插入数据元素
for(i = 0; i < N; i++)
InsertBST(&dt, r[i]);
TraverseDSTable(dt,print);
printf("\n请输入待查找的值: ");
scanf("%d", &j);
p = SearchBST(dt,j);
if(p)
{
printf("表中存在此值。");
DeleteBST(&dt,j);
printf("删除此值后:\n");
TraverseDSTable(dt,print);
printf("\n");
}
else
{
printf("表中不存在此值\n");
}
DestroyDSTable(&dt);
return 0;
}
/*
输出效果：
(3,4) (12,2) (24,6) (37,5) (45,1) (53,3) (61,8) (78,10) (90,9) (100,7)
请输入待查找的值: 45
表中存在此值。删除此值后:
(3,4) (12,2) (24,6) (37,5) (53,3) (61,8) (78,10) (90,9) (100,7)
*/