设计C语言程序,将n个数据组成二叉排序树结构,并可以删除其中的一个结点。 输入:数据个数n、n个数据、需要删除的数值value。 输出:原始数据、二叉排序树的中序输出及删除结点value后的结果。
时间: 2023-11-28 17:51:16 浏览: 74
结点类型定义如下-数据结构c语言版严蔚敏PPT
以下是基于C语言的代码实现:
```
#include <stdio.h>
#include <stdlib.h>
// 二叉排序树结构体定义
typedef struct BSTNode {
int data;
struct BSTNode* left;
struct BSTNode* right;
} BSTNode;
// 创建一个新节点
BSTNode* createNode(int data) {
BSTNode* newNode = (BSTNode*)malloc(sizeof(BSTNode));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 向二叉排序树中插入节点
BSTNode* insertNode(BSTNode* root, int data) {
if (root == NULL) {
return createNode(data);
}
if (data < root->data) {
root->left = insertNode(root->left, data);
} else if (data > root->data) {
root->right = insertNode(root->right, data);
}
return root;
}
// 中序遍历输出二叉排序树
void inorderTraversal(BSTNode* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}
// 查找最小值节点
BSTNode* findMinNode(BSTNode* root) {
while (root->left != NULL) {
root = root->left;
}
return root;
}
// 删除二叉排序树中的节点
BSTNode* deleteNode(BSTNode* root, int value) {
if (root == NULL) {
return root;
}
if (value < root->data) {
root->left = deleteNode(root->left, value);
} else if (value > root->data) {
root->right = deleteNode(root->right, value);
} else {
// 如果节点有一个或没有子节点
if (root->left == NULL) {
BSTNode* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
BSTNode* temp = root->left;
free(root);
return temp;
}
// 如果节点有两个子节点,找到右子树中的最小值节点
BSTNode* temp = findMinNode(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}
int main() {
int n, data, value;
printf("请输入数据个数:");
scanf("%d", &n);
BSTNode* root = NULL;
for (int i = 0; i < n; i++) {
printf("请输入第%d个数据:", i + 1);
scanf("%d", &data);
root = insertNode(root, data);
}
printf("原始数据为:");
inorderTraversal(root);
printf("\n请输入需要删除的数据:");
scanf("%d", &value);
root = deleteNode(root, value);
printf("删除节点%d后的结果为:", value);
inorderTraversal(root);
printf("\n");
return 0;
}
```
运行程序后,依次输入数据个数、n个数据和需要删除的数值value,即可输出原始数据、二叉排序树的中序输出及删除结点value后的结果。
阅读全文