用c语言写二叉树的删除操作
时间: 2023-08-18 17:06:05 浏览: 40
二叉树的删除操作比较复杂,需要考虑多种情况。以下是一种基于指针的实现方式,可以供参考:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树的节点结构体
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 创建新的二叉树节点
TreeNode* create_node(int val) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
// 在二叉排序树上查找值为val的节点
TreeNode* search(TreeNode* root, int val) {
if (root == NULL || root->val == val) {
return root;
} else if (root->val > val) {
return search(root->left, val);
} else {
return search(root->right, val);
}
}
// 找到右子树的最小节点
TreeNode* min_node(TreeNode* node) {
while (node->left != NULL) {
node = node->left;
}
return node;
}
// 删除值为val的节点,并返回根节点
TreeNode* delete_node(TreeNode* root, int val) {
if (root == NULL) {
return root;
} else if (root->val > val) {
root->left = delete_node(root->left, val);
} else if (root->val < val) {
root->right = delete_node(root->right, val);
} else { // 找到了值为val的节点
// 情况1:没有子节点或只有一个子节点
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;
}
// 情况2:有两个子节点
TreeNode* temp = min_node(root->right);
root->val = temp->val;
root->right = delete_node(root->right, temp->val);
}
return root;
}
// 中序遍历二叉排序树
void inorder(TreeNode* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->val);
inorder(root->right);
}
}
int main() {
TreeNode* root = create_node(5);
root->left = create_node(3);
root->right = create_node(7);
root->left->left = create_node(2);
root->left->right = create_node(4);
root->right->left = create_node(6);
root->right->right = create_node(8);
printf("原始树:");
inorder(root);
int val = 7;
root = delete_node(root, val);
printf("\n删除节点%d后的树:", val);
inorder(root);
return 0;
}
```
运行结果:
```
原始树:2 3 4 5 6 7 8
删除节点7后的树:2 3 4 5 6 8
```