C语言:设计算法,将n个数据组成二叉排序树结构,并可以删除其中的一个结点。 输入:数据个数n、n个数据、需要删除的数值value。 输出:原始数据
时间: 2024-02-28 20:57:28 浏览: 108
构成的二叉排序树结构和删除指定结点后的二叉排序树结构。
算法设计如下:
1. 定义二叉排序树的结构体,包括结点值、左右子树指针;
2. 定义二叉排序树的创建函数,从输入数据中逐个插入结点;
3. 定义二叉排序树的删除函数,分三种情况进行处理:
1. 待删除结点为叶子结点,直接删除;
2. 待删除结点只有一个子结点,将子结点移动到待删除结点的位置;
3. 待删除结点有两个子结点,找到它的中序遍历前驱或后继结点替换它,并删除前驱或后继结点。
4. 定义二叉排序树的中序遍历函数,输出原始数据构成的二叉排序树结构和删除指定结点后的二叉排序树结构。
C语言实现代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉排序树结构体
typedef struct BSTNode {
int data;
struct BSTNode *left;
struct BSTNode *right;
} BSTNode;
// 创建二叉排序树
void createBST(BSTNode **root, int data) {
if (*root == NULL) {
// 创建新结点
BSTNode *newNode = (BSTNode *)malloc(sizeof(BSTNode));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
*root = newNode;
} else if (data < (*root)->data) {
// 插入左子树
createBST(&((*root)->left), data);
} else {
// 插入右子树
createBST(&((*root)->right), data);
}
}
// 删除二叉排序树中指定结点
void deleteBST(BSTNode **root, int value) {
if (*root == NULL) {
// 结点不存在
printf("Node not found!\n");
return;
}
if (value < (*root)->data) {
// 在左子树中删除结点
deleteBST(&((*root)->left), value);
} else if (value > (*root)->data) {
// 在右子树中删除结点
deleteBST(&((*root)->right), value);
} else {
// 找到待删除结点
BSTNode *p = *root;
if (p->left == NULL && p->right == NULL) {
// 待删除结点为叶子结点
*root = NULL;
free(p);
} else if (p->left == NULL) {
// 待删除结点只有右子树
*root = p->right;
free(p);
} else if (p->right == NULL) {
// 待删除结点只有左子树
*root = p->left;
free(p);
} else {
// 待删除结点有两个子树
BSTNode *q = p->left;
while (q->right != NULL) {
q = q->right;
}
p->data = q->data;
deleteBST(&(p->left), q->data);
}
}
}
// 中序遍历二叉排序树
void inorderBST(BSTNode *root) {
if (root == NULL) {
return;
}
inorderBST(root->left);
printf("%d ", root->data);
inorderBST(root->right);
}
int main() {
int n, i, data, value;
BSTNode *root = NULL;
// 输入数据个数和数据
printf("Enter the number of data: ");
scanf("%d", &n);
printf("Enter the data: ");
for (i = 0; i < n; i++) {
scanf("%d", &data);
createBST(&root, data);
}
// 输入需要删除的数值
printf("Enter the value to delete: ");
scanf("%d", &value);
// 删除指定结点
deleteBST(&root, value);
// 输出原始数据构成的二叉排序树结构和删除指定结点后的二叉排序树结构
printf("Original BST: ");
inorderBST(root);
printf("\n");
return 0;
}
```
注意:该算法删除二叉排序树中的结点时,只删除一个结点,如果有重复的值,只会删除其中的一个结点。
阅读全文