请给出一个可以运行的C语言代码,可实现一棵二叉排序树,包括插入,删除,查找等功能
时间: 2023-07-29 18:09:00 浏览: 57
以下是一个可以运行的 C 语言代码,实现了二叉排序树的插入、删除、查找等功能。代码中使用了递归算法实现了这些功能,同时也包含了一些简单的测试代码。
```
#include <stdio.h>
#include <stdlib.h>
//定义二叉排序树节点
typedef struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
//插入节点
TreeNode* insert(TreeNode *root, int data) {
if (root == NULL) {
TreeNode *newNode = (TreeNode*)malloc(sizeof(TreeNode));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
} else if (data < root->data) {
root->left = insert(root->left, data);
} else if (data > root->data) {
root->right = insert(root->right, data);
}
return root;
}
//删除节点
TreeNode* delete(TreeNode *root, int data) {
if (root == NULL) {
return NULL;
} else if (data < root->data) {
root->left = delete(root->left, data);
} else if (data > root->data) {
root->right = delete(root->right, data);
} else {
//如果该节点有左右子树,则找到其右子树的最小值来替换
if (root->left != NULL && root->right != NULL) {
TreeNode *minNode = root->right;
while (minNode->left != NULL) {
minNode = minNode->left;
}
root->data = minNode->data;
root->right = delete(root->right, minNode->data);
} else {
TreeNode *tempNode = root;
if (root->left == NULL) {
root = root->right;
} else if (root->right == NULL) {
root = root->left;
}
free(tempNode);
}
}
return root;
}
//查找节点
TreeNode* search(TreeNode *root, int data) {
if (root == NULL) {
return NULL;
} else if (data < root->data) {
return search(root->left, data);
} else if (data > root->data) {
return search(root->right, data);
} else {
return root;
}
}
//中序遍历
void inorderTraversal(TreeNode *root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}
int main() {
TreeNode *root = NULL;
root = insert(root, 5);
root = insert(root, 3);
root = insert(root, 7);
root = insert(root, 1);
root = insert(root, 4);
root = insert(root, 6);
root = insert(root, 8);
inorderTraversal(root);
printf("\n");
root = delete(root, 5);
inorderTraversal(root);
printf("\n");
TreeNode *searchResult = search(root, 7);
if (searchResult != NULL) {
printf("Found %d\n", searchResult->data);
} else {
printf("Not Found\n");
}
return 0;
}
```
在代码中,我们首先定义了二叉排序树节点的结构体。然后实现了插入、删除、查找和中序遍历等功能。在主函数中,我们通过插入一些节点来构建了一棵二叉排序树,并且对其进行了中序遍历、删除和查找等操作。输出结果如下:
```
1 3 4 5 6 7 8
1 3 4 6 7 8
Found 7
```
阅读全文