c++以二叉链表为存储结构编写算法在二叉树中删除以值x为根节点的子树
时间: 2023-06-24 17:05:09 浏览: 52
可以按照以下步骤来删除以值为x的节点为根节点的子树:
1. 找到值为x的节点及其父节点。
2. 判断x节点是父节点的左子节点还是右子节点。
3. 如果x节点是叶子节点,直接删除,并且将其父节点相应的子节点指针置为NULL。
4. 如果x节点只有一个子节点,将其子节点替换x节点,并且将其父节点相应的子节点指针指向其子节点。
5. 如果x节点有两个子节点,则找到x节点的右子树中的最小值节点y,将y节点的值赋给x节点,然后删除y节点。
下面是对应的C++代码:
```c++
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 查找值为x的节点及其父节点
void findNode(TreeNode* root, TreeNode*& parent, TreeNode*& node, int x) {
if (root == NULL) {
return;
}
if (root->val == x) {
node = root;
return;
}
parent = root;
if (x < root->val) {
findNode(root->left, parent, node, x);
} else {
findNode(root->right, parent, node, x);
}
}
// 删除以值为x的节点为根节点的子树
void deleteSubTree(TreeNode*& root, int x) {
TreeNode* parent = NULL;
TreeNode* node = NULL;
findNode(root, parent, node, x);
if (node == NULL) {
return;
}
if (parent == NULL) {
root = NULL;
delete node;
return;
}
if (node == parent->left) {
parent->left = NULL;
} else {
parent->right = NULL;
}
if (node->left == NULL && node->right == NULL) {
delete node;
} else if (node->left != NULL && node->right == NULL) {
parent->left = node->left;
delete node;
} else if (node->left == NULL && node->right != NULL) {
parent->right = node->right;
delete node;
} else {
TreeNode* p = node->right;
TreeNode* pp = node;
while (p->left != NULL) {
pp = p;
p = p->left;
}
node->val = p->val;
if (pp == node) {
pp->right = p->right;
} else {
pp->left = p->right;
}
delete p;
}
}
```
注意,在删除节点的时候,需要将其对应的指针置为NULL,否则可能会引起内存泄漏或其他问题。