二叉排序树的建立、查找、插入、删除C语言实现
时间: 2023-09-30 10:06:51 浏览: 91
二叉排序树的建立、查找、插入、删除C语言实现
1. 二叉排序树的建立
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode* newNode(int val) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
struct TreeNode* insert(struct TreeNode* root, int val) {
if (root == NULL) {
return newNode(val);
}
if (val < root->val) {
root->left = insert(root->left, val);
} else {
root->right = insert(root->right, val);
}
return root;
}
2. 二叉排序树的查找
struct TreeNode* search(struct TreeNode* root, int val) {
if (root == NULL || root->val == val) {
return root;
}
if (val < root->val) {
return search(root->left, val);
} else {
return search(root->right, val);
}
}
3. 二叉排序树的插入
struct TreeNode* insert(struct TreeNode* root, int val) {
if (root == NULL) {
return newNode(val);
}
if (val < root->val) {
root->left = insert(root->left, val);
} else {
root->right = insert(root->right, val);
}
return root;
}
4. 二叉排序树的删除
struct TreeNode* minValueNode(struct TreeNode* node) {
struct TreeNode* current = node;
while (current && current->left != NULL) {
current = current->left;
}
return current;
}
struct TreeNode* deleteNode(struct TreeNode* root, int key) {
if (root == NULL) {
return root;
}
if (key < root->val) {
root->left = deleteNode(root->left, key);
} else if (key > root->val) {
root->right = deleteNode(root->right, key);
} else {
if (root->left == NULL) {
struct TreeNode* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
struct TreeNode* temp = root->left;
free(root);
return temp;
}
struct TreeNode* temp = minValueNode(root->right);
root->val = temp->val;
root->right = deleteNode(root->right, temp->val);
}
return root;
}
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)