C语言:设计算法,将n个数据组成二叉排序树结构,并可以删除其中的一个结点。 输入:数据个数n、n个数据、需要删除的数值value。 输出:原始数据、二叉排序树的中序输出及删除结点value后的结果。
时间: 2024-02-28 14:56:36 浏览: 59
c++实现在二叉检索树中删除一个结点的算法
5星 · 资源好评率100%
好的,下面是 C 语言的代码:
```
#include <stdio.h>
#include <stdlib.h>
// 二叉排序树节点结构体
typedef struct BSTNode {
int val;
struct BSTNode *left;
struct BSTNode *right;
} BSTNode;
// 插入节点函数
BSTNode* insertNode(BSTNode *root, int val) {
if (root == NULL) {
root = (BSTNode*) malloc(sizeof(BSTNode));
root->val = val;
root->left = NULL;
root->right = NULL;
} else if (val < root->val) {
root->left = insertNode(root->left, val);
} else {
root->right = insertNode(root->right, val);
}
return root;
}
// 中序遍历函数
void inorderTraversal(BSTNode *root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->val);
inorderTraversal(root->right);
}
}
// 查找节点函数
BSTNode* searchNode(BSTNode *root, int val) {
if (root == NULL || root->val == val) {
return root;
} else if (val < root->val) {
return searchNode(root->left, val);
} else {
return searchNode(root->right, val);
}
}
// 删除节点函数
BSTNode* deleteNode(BSTNode *root, int val) {
if (root == NULL) {
return root;
} else if (val < root->val) {
root->left = deleteNode(root->left, val);
} else if (val > root->val) {
root->right = deleteNode(root->right, val);
} 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;
} else {
// 既有左子树又有右子树
BSTNode *temp = root->right;
while (temp->left != NULL) {
temp = temp->left;
}
root->val = temp->val;
root->right = deleteNode(root->right, temp->val);
}
}
return root;
}
int main() {
int n, val;
printf("输入数据个数n:");
scanf("%d", &n);
printf("输入n个数据:");
BSTNode *root = NULL;
for (int i = 0; i < n; i++) {
int val;
scanf("%d", &val);
root = insertNode(root, val);
}
printf("原始数据为:");
inorderTraversal(root);
printf("\n输入要删除的数值value:");
scanf("%d", &val);
root = deleteNode(root, val);
printf("删除节点%d后的结果为:", val);
inorderTraversal(root);
return 0;
}
```
这段代码首先定义了二叉排序树节点结构体,包括节点值、左右子节点指针。然后定义了插入节点函数、中序遍历函数、查找节点函数和删除节点函数。
在主函数中,先读入数据,然后调用插入节点函数将数据插入到二叉排序树中,然后输出原始数据,并读入要删除的节点值。最后调用删除节点函数删除节点,并输出删除后的结果。
阅读全文