请用c语言实现任意给定一组数据,设计一个算法,建立一棵二叉排序树,对它进行查找、插入、删除等操作,并且给出全部代码
时间: 2024-02-28 21:57:01 浏览: 70
好的,以下是用C语言实现二叉排序树的代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 插入节点
TreeNode* insert(TreeNode* root, int val) {
if (root == NULL) {
root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = val;
root->left = NULL;
root->right = NULL;
return root;
}
if (val < root->val) {
root->left = insert(root->left, val);
} else if (val > root->val) {
root->right = insert(root->right, val);
}
return root;
}
// 查找节点
TreeNode* search(TreeNode* root, int val) {
if (root == NULL) {
return NULL;
}
if (root->val == val) {
return root;
} else if (val < root->val) {
return search(root->left, val);
} else {
return search(root->right, val);
}
}
// 删除节点
TreeNode* delete(TreeNode* root, int val) {
if (root == NULL) {
return NULL;
}
if (val < root->val) {
root->left = delete(root->left, val);
} else if (val > root->val) {
root->right = delete(root->right, val);
} else {
// 如果节点只有一个子节点或者没有子节点
if (root->left == NULL) {
TreeNode* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
TreeNode* temp = root->left;
free(root);
return temp;
}
// 如果节点有两个子节点
TreeNode* temp = root->right;
while (temp->left != NULL) {
temp = temp->left;
}
root->val = temp->val;
root->right = delete(root->right, temp->val);
}
return root;
}
// 中序遍历
void inorder(TreeNode* root) {
if (root == NULL) {
return;
}
inorder(root->left);
printf("%d ", root->val);
inorder(root->right);
}
int main() {
TreeNode* root = NULL;
// 插入节点
root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 70);
root = insert(root, 60);
root = insert(root, 80);
// 中序遍历
inorder(root);
printf("\n");
// 查找节点
TreeNode* node = search(root, 70);
if (node == NULL) {
printf("未找到节点\n");
} else {
printf("找到节点:%d\n", node->val);
}
// 删除节点
root = delete(root, 50);
// 中序遍历
inorder(root);
printf("\n");
return 0;
}
```
以上代码实现了二叉排序树的插入、查找、删除和中序遍历等操作。
阅读全文