按以下要求写出代码,1、定义二叉排序树的查找算法函数。2、二叉排序树的插入算法函数。3、建立二叉排序树的插入算法。4、二叉排序树删除一个结点的操作实现。5、打印二叉排序树。
时间: 2023-12-28 14:03:46 浏览: 83
以下是基于 C++ 的代码实现,包括所需的数据结构和算法函数:
```cpp
#include <iostream>
using namespace std;
// 定义二叉排序树的结点
struct BSTNode {
int data;
BSTNode* left;
BSTNode* right;
};
// 查找算法函数
BSTNode* BSTSearch(BSTNode* root, int key) {
if (root == nullptr || root->data == key) {
return root;
}
if (key < root->data) {
return BSTSearch(root->left, key);
}
return BSTSearch(root->right, key);
}
// 插入算法函数
BSTNode* BSTInsert(BSTNode* root, int key) {
if (root == nullptr) {
root = new BSTNode;
root->data = key;
root->left = root->right = nullptr;
} else if (key < root->data) {
root->left = BSTInsert(root->left, key);
} else {
root->right = BSTInsert(root->right, key);
}
return root;
}
// 建立二叉排序树的插入算法
BSTNode* BSTCreate() {
BSTNode* root = nullptr;
int n;
cout << "请输入结点个数: ";
cin >> n;
cout << "请输入" << n << "个结点的值: ";
for (int i = 0; i < n; i++) {
int key;
cin >> key;
root = BSTInsert(root, key);
}
return root;
}
// 二叉排序树删除一个结点的操作实现
BSTNode* BSTDelete(BSTNode* root, int key) {
if (root == nullptr) {
return root;
}
if (key < root->data) {
root->left = BSTDelete(root->left, key);
} else if (key > root->data) {
root->right = BSTDelete(root->right, key);
} else {
if (root->left == nullptr) {
BSTNode* temp = root->right;
delete root;
return temp;
} else if (root->right == nullptr) {
BSTNode* temp = root->left;
delete root;
return temp;
}
BSTNode* temp = root->right;
while (temp->left != nullptr) {
temp = temp->left;
}
root->data = temp->data;
root->right = BSTDelete(root->right, temp->data);
}
return root;
}
// 中序遍历打印二叉排序树
void BSTPrint(BSTNode* root) {
if (root == nullptr) {
return;
}
BSTPrint(root->left);
cout << root->data << " ";
BSTPrint(root->right);
}
int main() {
BSTNode* root = BSTCreate();
cout << "建立的二叉排序树为: ";
BSTPrint(root);
int key;
cout << "\n请输入要删除的结点的值: ";
cin >> key;
root = BSTDelete(root, key);
cout << "删除结点 " << key << " 后的二叉排序树为: ";
BSTPrint(root);
return 0;
}
```
这个程序允许用户输入要插入的结点值,然后建立一个二叉排序树。用户可以输入一个要删除的结点的值,如果该值存在于树中,则将其删除。最后,程序打印剩余的二叉排序树。
阅读全文