设计算法,将n个数据组成二叉排序树结构,并可以删除其中的一个结点。 输入:数据个数n、n个数据、需要删除的数值value。 输出:原始数据、二叉排序树的中序输出及删除结点value后的结果。
时间: 2024-03-26 13:35:16 浏览: 119
以下是算法的详细步骤:
1. 定义二叉排序树结点的结构体,包括结点值、左右子树指针。
2. 定义插入结点函数,将数据按照大小插入到二叉排序树中。
3. 定义中序遍历函数,按照左根右的顺序输出二叉排序树中的所有结点值。
4. 定义查找结点函数,查找二叉排序树中是否存在需要删除的数值value,如果存在,则返回该结点指针;否则返回NULL。
5. 定义删除结点函数,实现删除二叉排序树中指定结点的功能。如果被删除的结点是叶子结点,直接删除;如果被删除的结点只有一个子结点,将其子结点接到被删除结点的父结点上;如果被删除的结点有两个子结点,则将其右子树中最小的结点(即右子树中最左下角的结点)替换到被删除结点的位置上,然后删除该最小结点。
下面是具体的C++实现:
```c++
#include <iostream>
using namespace std;
// 二叉排序树结点结构体
struct BSTNode {
int val;
BSTNode *left, *right;
BSTNode(int v) : val(v), left(NULL), right(NULL) {}
};
// 插入结点
void insertNode(BSTNode *&root, int val) {
if (!root) {
root = new BSTNode(val);
return;
}
if (val < root->val)
insertNode(root->left, val);
else
insertNode(root->right, val);
}
// 中序遍历
void inorder(BSTNode *root) {
if (!root) return;
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}
// 查找结点
BSTNode* searchNode(BSTNode *root, int val) {
if (!root || root->val == val)
return root;
if (val < root->val)
return searchNode(root->left, val);
else
return searchNode(root->right, val);
}
// 删除结点
void deleteNode(BSTNode *&root, int val) {
if (!root) return;
if (val < root->val) {
deleteNode(root->left, val);
} else if (val > root->val) {
deleteNode(root->right, val);
} else {
if (!root->left && !root->right) {
delete root;
root = NULL;
} else if (!root->left || !root->right) {
BSTNode *tmp = root;
root = root->left ? root->left : root->right;
delete tmp;
} else {
BSTNode *tmp = root->right;
while (tmp->left) tmp = tmp->left;
root->val = tmp->val;
deleteNode(root->right, tmp->val);
}
}
}
int main() {
int n, val;
cin >> n;
BSTNode *root = NULL;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
insertNode(root, x);
}
cin >> val;
cout << "原始数据:";
inorder(root);
cout << endl;
cout << "删除结点" << val << "后:";
deleteNode(root, val);
inorder(root);
cout << endl;
return 0;
}
```
阅读全文