编写一个C/C++程序,实现随机产生一组关键字,利用二叉排序树的插入算法建立二叉排序树,然后删除某一指定关键字元素。
时间: 2024-03-12 12:45:49 浏览: 91
C++实现二叉排序树(插入、删除、遍历)
好的,以下是一个简单的C++程序,实现随机产生一组关键字,利用二叉排序树的插入算法建立二叉排序树,然后删除某一指定关键字元素。
```cpp
#include <iostream>
#include <cstdlib>
using namespace std;
// 二叉排序树的节点结构体
struct BSTNode {
int key;
BSTNode* left;
BSTNode* right;
};
// 插入节点到二叉排序树中
void BSTInsert(BSTNode*& root, int key) {
if (!root) {
root = new BSTNode{key, NULL, NULL};
return;
}
if (key < root->key) {
BSTInsert(root->left, key);
} else {
BSTInsert(root->right, key);
}
}
// 在二叉排序树中查找指定关键字的节点
BSTNode* BSTSearch(BSTNode* root, int key) {
if (!root) {
return NULL;
}
if (key == root->key) {
return root;
} else if (key < root->key) {
return BSTSearch(root->left, key);
} else {
return BSTSearch(root->right, key);
}
}
// 从二叉排序树中删除指定关键字的节点
void BSTDelete(BSTNode*& root, int key) {
if (!root) {
return;
}
if (key == root->key) {
if (!root->left && !root->right) {
// 删除叶子节点
delete root;
root = NULL;
} else if (root->left && !root->right) {
// 删除只有左子树的节点
BSTNode* temp = root;
root = root->left;
delete temp;
} else if (!root->left && root->right) {
// 删除只有右子树的节点
BSTNode* temp = root;
root = root->right;
delete temp;
} else {
// 删除有两个子树的节点
BSTNode* temp = root->right;
while (temp->left) {
temp = temp->left;
}
root->key = temp->key;
BSTDelete(root->right, temp->key);
}
} else if (key < root->key) {
BSTDelete(root->left, key);
} else {
BSTDelete(root->right, key);
}
}
int main() {
// 随机生成一组关键字
int keys[10];
for (int i = 0; i < 10; i++) {
keys[i] = rand() % 100;
}
// 建立二叉排序树
BSTNode* root = NULL;
for (int i = 0; i < 10; i++) {
BSTInsert(root, keys[i]);
}
// 输出原始的二叉排序树
cout << "Original BST: ";
for (int i = 0; i < 10; i++) {
cout << keys[i] << " ";
}
cout << endl;
// 删除指定关键字的节点
int key;
cout << "Enter the key to be deleted: ";
cin >> key;
BSTDelete(root, key);
// 输出删除指定关键字后的二叉排序树
cout << "BST after deleting " << key << ": ";
for (int i = 0; i < 10; i++) {
if (keys[i] != key) {
cout << keys[i] << " ";
}
}
cout << endl;
return 0;
}
```
注意,这个程序中的删除操作只能删除第一个匹配的关键字,如果有多个相同的关键字,只会删除第一个。如果需要删除所有匹配的关键字,需要修改删除函数。
阅读全文