java二叉树的增删查改
时间: 2023-10-26 22:56:15 浏览: 34
二叉树的增删查改是二叉树操作中常见的操作,下面我分别介绍一下。
1. 增加节点:
在二叉树中增加一个节点,需要遵循以下规则:
- 如果树为空,新节点成为根节点。
- 如果树不为空,从根节点开始,比较新节点的值和当前节点的值。
- 如果新节点的值小于当前节点的值,将新节点插入当前节点的左子树。
- 如果新节点的值大于当前节点的值,将新节点插入当前节点的右子树。
2. 删除节点:
删除节点需要考虑以下几种情况:
- 如果要删除的节点是叶子节点(没有子节点),直接删除即可。
- 如果要删除的节点只有一个子节点,将子节点替代要删除的节点。
- 如果要删除的节点有两个子节点,则找到该节点右子树中的最小值(或左子树中的最大值),用该最小(最大)值替代要删除的节点,并在右子树中删除该最小(最大)值所在的节点。
3. 查找节点:
查找节点需要遵循以下规则:
- 从根节点开始,比较要查找的值与当前节点的值。
- 如果要查找的值等于当前节点的值,则找到了目标节点。
- 如果要查找的值小于当前节点的值,则在左子树中继续查找。
- 如果要查找的值大于当前节点的值,则在右子树中继续查找。
- 如果遍历到叶子节点仍未找到目标节点,则说明目标节点不存在。
4. 修改节点:
修改节点需要先查找到目标节点,然后修改该节点的值即可。
希望以上介绍对你有帮助!如果还有其他问题,请继续提问。
相关问题
C语言实现根据key值进行二叉树的增删查改
1. 增加节点:
```c
struct TreeNode* insert(struct TreeNode* root, int key) {
if (root == NULL) {
return createNode(key);
}
if (key < root->key) {
root->left = insert(root->left, key);
} else if (key > root->key) {
root->right = insert(root->right, key);
}
return root;
}
```
2. 删除节点:
```c
struct TreeNode* delete(struct TreeNode* root, int key) {
if (root == NULL) {
return root;
}
if (key < root->key) {
root->left = delete(root->left, key);
} else if (key > root->key) {
root->right = delete(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->key = temp->key;
root->right = delete(root->right, temp->key);
}
return root;
}
```
3. 查找节点:
```c
struct TreeNode* search(struct TreeNode* root, int key) {
if (root == NULL || root->key == key) {
return root;
}
if (key < root->key) {
return search(root->left, key);
}
return search(root->right, key);
}
```
4. 修改节点:
```c
struct TreeNode* modify(struct TreeNode* root, int oldKey, int newKey) {
root = delete(root, oldKey);
root = insert(root, newKey);
return root;
}
```
二叉树的增删改查 c语言
好的,下面是二叉树的增删改查的C语言代码示例。
首先,我们需要定义二叉树的结构体:
```c
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
```
接下来,我们分别实现二叉树的增、删、改、查操作:
1. 增加节点
```c
struct TreeNode* insertNode(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 = insertNode(root->left, val);
} else if (val > root->val) {
root->right = insertNode(root->right, val);
}
return root;
}
```
2. 删除节点
```c
struct TreeNode* deleteNode(struct TreeNode* root, int key) {
if (!root) {
return NULL;
}
if (root->val == key) {
if (!root->left) {
struct TreeNode* tmp = root->right;
free(root);
return tmp;
} else if (!root->right) {
struct TreeNode* tmp = root->left;
free(root);
return tmp;
} else {
struct TreeNode* p = root->right;
while (p->left) {
p = p->left;
}
root->val = p->val;
root->right = deleteNode(root->right, p->val);
}
} else if (root->val > key) {
root->left = deleteNode(root->left, key);
} else {
root->right = deleteNode(root->right, key);
}
return root;
}
```
3. 修改节点
```c
struct TreeNode* modifyNode(struct TreeNode* root, int oldVal, int newVal) {
root = deleteNode(root, oldVal);
root = insertNode(root, newVal);
return root;
}
```
4. 查找节点
```c
struct TreeNode* searchNode(struct TreeNode* root, int val) {
if (!root || root->val == val) {
return root;
}
if (root->val > val) {
return searchNode(root->left, val);
} else {
return searchNode(root->right, val);
}
}
```
以上就是二叉树的增删改查的C语言代码示例。