对一棵初始为空的二叉查找树(Binary Search Tree, BST)进行若干插入或删除操作,用中序遍历输出最后的二叉查找树,用c语言给出代码
时间: 2024-05-02 22:22:23 浏览: 111
二叉查找树的查找、删除、插入等基本操作(C语言)
5星 · 资源好评率100%
以下是用C语言实现二叉查找树的插入和删除操作,并用中序遍历输出最后的二叉查找树的代码:
```c
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
// 二叉查找树的插入操作
struct TreeNode* insert(struct TreeNode* root, int val) {
if (!root) {
// 如果根节点为空,直接新建一个节点
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
if (val < root->val) {
// 如果要插入的值小于根节点的值,递归插入到左子树中
root->left = insert(root->left, val);
} else if (val > root->val) {
// 如果要插入的值大于根节点的值,递归插入到右子树中
root->right = insert(root->right, val);
}
// 如果要插入的值等于根节点的值,什么也不做
return root;
}
// 二叉查找树的删除操作
struct TreeNode* delete(struct TreeNode* root, int val) {
if (!root) {
// 如果根节点为空,直接返回
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 && !root->right) {
// 如果要删除的节点没有左子树和右子树,直接删除
free(root);
return NULL;
} else if (root->left && !root->right) {
// 如果要删除的节点只有左子树,将左子树作为新的根节点
struct TreeNode* node = root->left;
free(root);
return node;
} else if (!root->left && root->right) {
// 如果要删除的节点只有右子树,将右子树作为新的根节点
struct TreeNode* node = root->right;
free(root);
return node;
} else {
// 如果要删除的节点既有左子树又有右子树,找到右子树的最小值节点,将该节点的值赋给要删除的节点,然后递归删除右子树中的这个最小值节点
struct TreeNode* node = root->right;
while (node->left) {
node = node->left;
}
root->val = node->val;
root->right = delete(root->right, root->val);
}
}
return root;
}
// 中序遍历输出二叉查找树
void inorder(struct TreeNode* root) {
if (!root) {
return;
}
inorder(root->left);
printf("%d ", root->val);
inorder(root->right);
}
int main() {
struct TreeNode* root = NULL;
int nums[] = {5, 2, 4, 6, 1, 3};
int n = sizeof(nums) / sizeof(int);
for (int i = 0; i < n; i++) {
root = insert(root, nums[i]);
}
inorder(root); // 中序遍历输出:1 2 3 4 5 6
root = delete(root, 2);
printf("\n");
inorder(root); // 中序遍历输出:1 3 4 5 6
return 0;
}
```
阅读全文