二叉排序树的实现

目录

• 1. 编写SearchBST(T, key)与InsertBST(T, key)的伪代码，并实现；
  • SearchBST(T，key)的伪代码及代码实现：
  • InsertBST(T, key)的伪代码及代码实现：
• 2. 编写CreateBST(T)的伪代码实现从控制台输入创建BST树。最后使用代码实现。使用“50 30 80 20 40 90 10 25 35 85 23 88”创建BST，并中序输出该BST
  • CreateBST(T)的伪代码:
  • CreateBST(T)的代码实现:
  • 使用“50 30 80 20 40 90 10 25 35 85 23 88”创建BST，并中序输出该BST
    • 运行结果演示：
    • 完整代码：
• 3. 编写DeleteBST(T, key)的伪代码实现从T中删除关键字key。如果无法编写出来，请写出在BST中删除关键字key所需注意的事项。
  • 注意事项：
  • 伪代码：
• 4.使用代码实现DeleteBST(T, key)
  • 代码实现：
  • 运行结果演示：
  • 完整代码：

1. 编写SearchBST(T, key)与InsertBST(T, key)的伪代码，并实现；

SearchBST(T，key)的伪代码及代码实现：

/*二叉排序树查找伪代码*/
SearchBST(T, key) {
	if (T为空 || T->data等于key) {//递归结束的条件
		return T;
	}
	if (key小于T->data) {
		return SearchBST(T->lchild, key);//在左子树中递归查找
	}
	else {
		return SearchBST(T->rchild, key);//在右子树中递归查找
	}
}

/*二叉排序树查找代码实现*/
BSTNode* SearchBST(BSTNode* T, int k) {
	if (T == NULL || T->key == k) {
		return T;
	}
	if (k < T->key) {
		return SearchBST(T->lchild, k);
	}
	else {
		return SearchBST(T->rchild, k);
	}
}

InsertBST(T, key)的伪代码及代码实现：

/*二叉排序树插入的伪代码*/
insertBST(T, key) {
	//在二叉排序树T中插入一个关键字为key的结点，若插入成功则返回真，否则返回假
	if (T为空) {//原树为空，新插入的结点为根节点
		初始化T;//申请空间创建新节点T，然后把T的左右孩子都设为NULL
		T->data = key;
		return true;
	}
	else if (key等于T->data) {//树种存在相同关键字的结点，返回假
		return false;
	}
	else if (key小于T->data) {
		return InsertBST(T->lchild, key);//插入到左子树中
	}
	else {
		return InsertBST(T->rchild, key);//插入到右子树中
	}
}

/*二叉排序树插入代码实现*/
bool InsertBST(BSTNode*& bt, int k) {
	if (bt == NULL) {
		bt = new 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);
	}
}

2. 编写CreateBST(T)的伪代码实现从控制台输入创建BST树。最后使用代码实现。使用“50 30 80 20 40 90 10 25 35 85 23 88”创建BST，并中序输出该BST

CreateBST(T)的伪代码:

/*创建二叉排序树的伪代码*/
CreateBST(T) {
	T = NULL;// 初始化T为空树
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];//从控制台获取n个结点数，存入数组a[]
	}
	初始化i = 0;
	while (i小于n) {
		InsertBST(T, a[i]);//将关键字a[i]插入二叉排序树T中
		i++;
	}
	return T;//返回建立的BST的根指针
}

CreateBST(T)的代码实现:

/*创建二叉排序树的代码实现*/
BSTNode* CreateBST(int a[], int n) {
	BSTNode* bt = NULL;
	int i = 0;
	while (i < n) {
		InsertBST(bt, a[i]);
		i++;
	}
	return bt;
}

使用“50 30 80 20 40 90 10 25 35 85 23 88”创建BST，并中序输出该BST

运行结果演示：

完整代码：

#include<iostream>
using namespace std;
typedef int KeyTyped;
typedef struct Node {
	int key;
	struct Node* lchild;
	struct Node* rchild;
}BSTNode;
BSTNode* SearchBST(BSTNode* T, int k);
bool InsertBST(BSTNode*& bt, int k);
BSTNode* CreateBST(int a[], int n);
void InOrder(BSTNode* bt);
int main(){
	int i, n, a[100];
	printf("请输入二叉排序树的结点个数：");
	cin >> n;
	printf("请输入二叉排序树结点值：
");
	for (i = 0; i < n; i++) {
		cin >> a[i];
	}
	BSTNode* root = CreateBST(a, n);
	printf("该二叉树中序遍历序列为：
");
	InOrder(root);
	return 0;
}
BSTNode* SearchBST(BSTNode* T, int k) {
	if (T == NULL || T->key == k) {
		return T;
	}
	if (k < T->key) {
		return SearchBST(T->lchild, k);
	}
	else {
		return SearchBST(T->rchild, k);
	}
}
bool InsertBST(BSTNode*& bt, int k) {
	if (bt == NULL) {
		bt = new 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) {
	BSTNode* bt = NULL;
	int i = 0;
	while (i < n) {
		InsertBST(bt, a[i]);
		i++;
	}
	return bt;
}
void InOrder(BSTNode* bt) {
	if (bt != NULL) {
		InOrder(bt->lchild);
		printf("%d ", bt->key);
		InOrder(bt->rchild);
	}
}

3. 编写DeleteBST(T, key)的伪代码实现从T中删除关键字key。如果无法编写出来，请写出在BST中删除关键字key所需注意的事项。

注意事项：

删除操作时必须先进行查找，假设查找结束时p指向要删除的结点，则删除分成以下几种情况：
（1）若p结点是叶子结点，直接删去该叶子结点。
（2）若p只有左（右）子树，直接将其左（右）孩子结点替代结点p。
（3）若p结点同时存在左右子树，可以从其左子树中选择关键字最大的结点r，用结点r的值替代结点p的值，并删除结点r，其原理是用中序前驱替代被删结点。
在实现代码的时候，其实情况（2）包含了情况（1），所以无需为情况（1）另开一个if分支。

伪代码：

DeleteBST(T, key) {//删除函数
	if (T不为空树) {
		if (key小于T->data) {//递归在左子树中删除为key的结点
			return DeleteBST(T->lchild, key);
		}
		else if (key大于T->data) {//递归在右子树中删除为key的结点
			return DeleteBST(T->rchild, key);
		}
		else {//找到了要删除的结点T
			if (T->lchild为空) {//T没有左子树的情况
				q = T;
				T = T->rchild;//用结点T的右孩子替代它
				free(q);
			}
			else if (T->rchild为空) {//T没有右子树的情况
				q = T;
				T = T->lchild;//用结点T的左孩子替代它
				free(q);
			}
			else {//T既有左子树又有右子树的情况
				Delete(T, T->lchild);//调用Delete函数删除结点T
			}
		}
	}
	else {//空树删除失败，返回假
		return false;
	}
}

Delete(p, r) {//被删结点p有左、右子树，r指向其左孩子
	if (r->rchild不为空) {//递归找结点人r的最右下结点
		Delete(p, r->rchild);
	}
	else {//找到了最右下结点r（r没有右子树）
		p->data = r->data;//将结点r的值存放到结点p中
		q = r;
		r = r->rchild;//用结点r的左孩子替代它
		free(q);//释放结点q的空间
	}
}

4.使用代码实现DeleteBST(T, key)

代码实现：

bool DeleteBST(BSTNode*& bt, int k) {
	if (bt == NULL) {
		return false;
	}
	else {
		if (k < bt->key) {
			return DeleteBST(bt->lchild, k);
		}
		else if (k > bt->key) {
			return DeleteBST(bt->rchild, k);
		}
		else {
			BSTNode* q;
			if (bt->lchild == NULL) {
				q = bt;
				bt = bt->rchild;
				free(q);
			}
			else if (bt->rchild == NULL) {
				q = bt;
				bt = bt->lchild;
				free(q);
			}
			else {
				Delete(bt, bt->lchild);
			}
		}
	}
}

void Delete(BSTNode* p, BSTNode* &r) {
	BSTNode* q;
	if (r->rchild != NULL) {
		Delete(p->rchild);
	}
	else {
		p->key = r->key;
		q = r;
		r = r->lchild;
		free(q);
	}
}

运行结果演示：

完整代码：

#include<iostream>
using namespace std;
typedef int KeyTyped;
typedef struct Node {
	int key;
	struct Node* lchild;
	struct Node* rchild;
}BSTNode;
BSTNode* SearchBST(BSTNode* T, int k);
bool InsertBST(BSTNode*& bt, int k);
BSTNode* CreateBST(int a[], int n);
void InOrder(BSTNode* bt);
bool DeleteBST(BSTNode*& bt, int k);
void Delete(BSTNode* p, BSTNode*& r);
int main(){
	int i, n, a[100], k;
	printf("请输入二叉排序树的结点个数：");
	cin >> n;
	printf("请输入二叉排序树结点值：
");
	for (i = 0; i < n; i++) {
		cin >> a[i];
	}
	BSTNode* root = CreateBST(a, n);
	printf("请输入要删除的结点：");
	cin>>k;
	printf("该二叉树删除前中序遍历序列为：
");
	InOrder(root);
	printf("
该二叉树删除后中序遍历序列为：
");
	DeleteBST(root, k);
	InOrder(root);

	return 0;
}
BSTNode* SearchBST(BSTNode* T, int k) {
	if (T == NULL || T->key == k) {
		return T;
	}
	if (k < T->key) {
		return SearchBST(T->lchild, k);
	}
	else {
		return SearchBST(T->rchild, k);
	}
}
bool InsertBST(BSTNode*& bt, int k) {
	if (bt == NULL) {
		bt = new 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) {
	BSTNode* bt = NULL;
	int i = 0;
	while (i < n) {
		InsertBST(bt, a[i]);
		i++;
	}
	return bt;
}
void InOrder(BSTNode* bt) {
	if (bt != NULL) {
		InOrder(bt->lchild);
		printf("%d ", bt->key);
		InOrder(bt->rchild);
	}
}
bool DeleteBST(BSTNode*& bt, int k) {
	if (bt == NULL) {
		return false;
	}
	else {
		if (k < bt->key) {
			return DeleteBST(bt->lchild, k);
		}
		else if (k > bt->key) {
			return DeleteBST(bt->rchild, k);
		}
		else {
			BSTNode* q;
			if (bt->lchild == NULL) {
				q = bt;
				bt = bt->rchild;
				free(q);
			}
			else if (bt->rchild == NULL) {
				q = bt;
				bt = bt->lchild;
				free(q);
			}
			else {
				Delete(bt, bt->lchild);
			}
		}
	}
}
void Delete(BSTNode* p, BSTNode* &r) {
	BSTNode* q;
	if (r->rchild != NULL) {
		Delete(p, r->rchild);
	}
	else {
		p->key = r->key;
		q = r;
		r = r->lchild;
		free(q);
	}
}