请使用C语言编写可实现二叉排序树相关基础操作的程序
时间: 2024-03-24 07:37:58 浏览: 70
好的,以下是使用C语言编写的可实现二叉排序树相关基础操作的程序:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int value;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
void insertNode(TreeNode **root, int value) {
if (*root == NULL) {
*root = (TreeNode*)malloc(sizeof(TreeNode));
(*root)->value = value;
(*root)->left = NULL;
(*root)->right = NULL;
} else {
if (value < (*root)->value) {
insertNode(&((*root)->left), value);
} else {
insertNode(&((*root)->right), value);
}
}
}
void inorderTraversal(TreeNode *root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->value);
inorderTraversal(root->right);
}
}
TreeNode *searchNode(TreeNode *root, int value) {
if (root == NULL || root->value == value) {
return root;
} else if (value < root->value) {
return searchNode(root->left, value);
} else {
return searchNode(root->right, value);
}
}
TreeNode *findMinNode(TreeNode *root) {
while (root->left != NULL) {
root = root->left;
}
return root;
}
void deleteNode(TreeNode **root, int value) {
if (*root == NULL) {
return;
}
if (value < (*root)->value) {
deleteNode(&((*root)->left), value);
} else if (value > (*root)->value) {
deleteNode(&((*root)->right), value);
} else {
if ((*root)->left == NULL) {
TreeNode *temp = *root;
*root = (*root)->right;
free(temp);
} else if ((*root)->right == NULL) {
TreeNode *temp = *root;
*root = (*root)->left;
free(temp);
} else {
TreeNode *temp = findMinNode((*root)->right);
(*root)->value = temp->value;
deleteNode(&((*root)->right), temp->value);
}
}
}
int main() {
TreeNode *root = NULL;
insertNode(&root, 5);
insertNode(&root, 2);
insertNode(&root, 7);
insertNode(&root, 1);
insertNode(&root, 3);
insertNode(&root, 6);
insertNode(&root, 8);
printf("中序遍历二叉排序树:");
inorderTraversal(root);
printf("\n");
int value = 3;
TreeNode *node = searchNode(root, value);
if (node != NULL) {
printf("找到节点 %d\n", node->value);
} else {
printf("未找到节点 %d\n", value);
}
value = 4;
node = searchNode(root, value);
if (node != NULL) {
printf("找到节点 %d\n", node->value);
} else {
printf("未找到节点 %d\n", value);
}
value = 5;
printf("删除节点 %d\n", value);
deleteNode(&root, value);
printf("中序遍历二叉排序树:");
inorderTraversal(root);
printf("\n");
return 0;
}
```
该程序定义了一个名为`TreeNode`的结构体,表示二叉排序树的节点,包含整型数值、左子节点和右子节点。程序还定义了`insertNode`、`inorderTraversal`、`searchNode`、`findMinNode`和`deleteNode`等函数,分别实现了插入节点、中序遍历、查找节点、查找最小节点和删除节点等操作。
主函数中首先创建一个空的二叉排序树,然后插入一些节点,输出中序遍历结果,查找一些节点并输出查找结果,删除一个节点后再次输出中序遍历结果。
二叉排序树是一种特殊的二叉树,它的每个节点的左子树中的所有节点的值都小于该节点的值,右子树中的所有节点的值都大于该节点的值。因此,二叉排序树的中序遍历结果是一个有序的序列。插入节点时,需要按照二叉排序树的要求将新节点插入到合适的位置。查找节点时,从根节点开始递归查找,直到找到要查找的节点或者找到了叶子节点(表示未找到)。删除节点时,需要考虑三种情况:被删除节点没有子节点、被删除节点只有一个子节点、被删除节点有两个子节点。
阅读全文