实验题目: 二叉排序树。任意给定一组数据，设计一个算法，建立一棵二叉排序树，对它进行查找、插入、删除等操作。
实验说明：二叉排序树存储结构如下：
typedef struct BiTNode { // 结点结构
struct BiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode, *BiTree;
二叉排序树插入算法伪代码如下：
1. 若root是空树，则将结点s作为根结点插入；否则
2. 若s->data＜root->data，则把结点s插入到root的左子树中；否则
3. 把结点s插入到root的右子树中。
二叉排序树中删除一个结点f的左孩子结点p算法伪代码如下：
1. 若结点p是叶子，则直接删除结点p；
2. 若结点p只有左子树，则只需重接p的左子树；
若结点p只有右子树，则只需重接p的右子树；
3. 若结点p的左右子树均不空，则
3.1 查找结点p的右子树上的最左下结点s以及结点s的双亲结点par；
3.2 将结点s数据域替换到被删结点p的数据域；
3.3 若结点p的右孩子无左子树，则将s的右子树接到par的右子树上；
否则，将s的右子树接到结点par的左子树上；
3.4 删除结点s；
对于二叉树这样的一个特殊的树类结构，每个结点都可以看作根结点，因此我们可以采用递归的思想设计算法，首先我们需要建立一棵二叉排序树，二叉排序树的特点是，根结点的左子树均小于根结点，根结点的右子树均大于根结点，因此我们可以每次只对二叉树作插入操作，共循环n次（n是所给定的关键字的数量），每次插入如果待插入的结点小于根结点，就递归处理左子树，反之处理右子树，如果与根结点相等，则返回false（二叉排序树中不存在关键字一样的结点）。二叉排序树构造完毕后，对其实行插入操作，我们也同样使用递归来实现，当找到时，返回true。对于删除操作，根据不同的情况，我们可以采取不同的删除办法，上面的伪代码已经给出了大致思想，用代码实现即可。
下面给出两种代码，一种c语言写法，一种c++写法
c语言写法：
//二叉排序树。任意给定一组数据，设计一个算法，建立一棵二叉排序树，对它进行查找、插入、删除等操作。
#include<stdio.h>
#include<stdlib.h>
typedef struct node//元素类型
{
int key;//关键字
struct node *lchild;//左右孩子指针
struct node *rchild;
}BSTNode;
///*
bool InsertBST(BSTNode *&bt,int k)
{//在二叉排序树中插入一个关键字为k的结点，若插入成功返回真，否则返回假
if(bt==NULL)//若原树为空，新插入的结点为根节点
{
bt=(BSTNode*)malloc(sizeof(BSTNode));
bt->key=k;
bt->lchild=bt->rchild=NULL;
return true;
}
else if(k==bt->key)//数中存在相同关键字则无需插入，返回假
{
return false;
}
else if(k<bt->key)//若关键字小于根节点
{
return InsertBST(bt->lchild,k);//插入到左子树中
}
else//否则
return InsertBST(bt->rchild,k);//插入到右子树中
}
//*/
///*
BSTNode* CreateBST(int a[],int n)//创建二叉排序树算法，数组参数传递关键字序列，n传递关键字数量
//返回结点指针，这里要注意调用形式
{
BSTNode* bt=NULL;//初始时bt树为空，这里bt作为临时结点，调用插入函数插入到原先的节点上
int i=0;
while(i<n)
{
InsertBST(bt,a[i]);
i++;
}
return bt;//返回建立的二叉树
}
//*/
///*
BSTNode *SearchBST(BSTNode*bt,int k)//二叉排序树的查找，这里也要注意返回一个结点指针
//第一个参数是二叉排序树，第二个参数是要查找的关键字
{
if(bt==NULL||bt->key==k)//递归结束条件
{
return bt;
}
if(k<bt->key)
{
return SearchBST(bt->lchild,k);//在左子树中递归查找
}
else
return SearchBST(bt->rchild,k);//在右子树中递归查找
}
//*/
///*
void Deletel(BSTNode* p,BSTNode*&r)//结点p既有左子树也有右子树
//r指向左孩子
{
BSTNode *q;//临时结点q
if(r->rchild!=NULL)//递归找出结点r的最右下结点
{
Deletel(p,r->rchild);//
}
else //找到了最右下结点
{
p->key=r->key;//将r的值（左孩子值）存放到结点p（根节点）中
q=r; //原教材上下面两行代码为：
r->key=r->lchild->key;//r=r->lchild;
q->lchild=q->rchild=NULL;//free(q);但若按照这个代码，结点不会被消除，只是生成随机数，到时不好输出
}
}
void Delete(BSTNode *&p)//从二叉排序树删除结点p
{
BSTNode *q;
if(p->rchild==NULL)//若结点没有右子树
{
q=p;
//下面两行教材上的代码：
p->key=p->lchild->key; // p=p->rchild;//用结点p的左孩子代替
q->lchild=q->rchild=NULL;//free（q）;但若按照这个代码，结点不会被消除，只是生成随机数，到时不好输出
//q被p取代，其孩子为空，相当于释放q，下面同理
}
else if(p->lchild==NULL)//结点p没有左孩子
{
q=p;
//下面两行教材上的代码：
p->key=p->rchild->key; //p=p->rchild;
q->rchild=q->lchild=NULL ; // free(q);但若按照这个代码，结点不会被消除，只是生成随机数，到时不好输出
}
else Deletel(p,p->lchild);
}
void DipBT(BSTNode *b)//输出二叉树
{
if(b!=NULL)
{
printf("%d",b->key);
if(b->lchild!=NULL || b->rchild!=NULL)
{
printf("(");
DipBT(b->lchild);
if(b->rchild!=NULL) printf(",");
DipBT(b->rchild);
printf(")");
}
}
}
int main()
{
BSTNode *p,*tp;
int a[9]={5,2,1,6,7,4,8,3,9};
p=CreateBST(a,9);
printf("创建二叉排序树:\n");
DipBT(p);
printf("\n\n\n");
printf("插入关键字为10的结点:\n");
InsertBST(p,10);
DipBT(p);
printf("\n\n\n");
printf("查找关键字为4的结点:\n");
tp=SearchBST(p,4);
printf("结点为%d\n\n\n",tp->key);
printf("删除关键字是4的结点：\n");
Delete(tp);
DipBT(p);
}
c++实现，本例与c语言思路是一样的，只是把结构体换成了类，不给出注释了
#include<iostream>
using namespace std;
class BSTNode {
public:
int key;
BSTNode* lchild, * rchild;
};
bool InsertNode(BSTNode*& b, int k) {
if (b == NULL) {
b = new BSTNode;
b->key = k;
b->lchild = NULL;b->rchild = NULL;
return true;
}
else if (k == b->key)return false;
else if (k < b->key)
return InsertNode(b->lchild, k);
else if (k > b->key)
return InsertNode(b->rchild, k);
}
void Display(BSTNode* b) {
if (b != NULL) {
cout << b->key;
if (b->lchild != NULL || b->rchild != NULL) {
cout << "(";
Display(b->lchild);
if (b->rchild != NULL)cout << ",";
Display(b->rchild);
cout << ")";
}
}
}
void Delete1(BSTNode* b, BSTNode*& r) {
BSTNode* p;
if (r->rchild != NULL)
Delete1(b, r->rchild);
else {
b->key = r->key;
p = r;
r = r->lchild;
delete p;
}
}
void Delete(BSTNode*& b) {
BSTNode* p;
if (b->lchild == NULL && b->rchild == NULL) {
b = NULL;
delete b;
}
else if (b->lchild != NULL && b->rchild == NULL) {
p = b;
b = b->lchild;
delete p;
}
else if (b->lchild == NULL && b->rchild != NULL) {
p = b;
b = b->rchild;
delete p;
}
else
Delete1(b, b->lchild);
}
bool Seek(BSTNode*& b, int k) {
if (b == NULL)
return false;
else {
if (k < b->key)
return Seek(b->lchild, k);
else if (k > b->key)
return Seek(b->rchild, k);
else {
Delete(b);
return true;
}
}
}//查找算法
void CreatBST(BSTNode*& b, int a[9]) {
int i;
b = NULL;
for (i = 0; i < 9; i++)
InsertNode(b, a[i]);
}
void Destroy(BSTNode*& b) {
if (b != NULL) {
Destroy(b->lchild);
Destroy(b->rchild);
delete b;
}
}
int main() {
BSTNode* b;
int k;
int a[9] = { 5,2,6,1,4,7,3,8,9 };
CreatBST(b, a);
Display(b);
cout << endl;
cout << "请输入要删除的结点：";
cin >> k;
Seek(b, k);
Display(b);
cout << endl;
cout << "———————————————" << endl;
Destroy(b);
}
0 条评论