BST节点删除的情况可以细分为6种情况
- 根节点的删除
1.1 根节点没有左右孩子
1.2 根节点只有左孩子
1.3 根节点只有右孩子
1.4 根节点有左右孩子 - 子节点的删除
2.1 子节点没有左右孩子
2.2 子节点只有左孩子
2.3 子节点只有右孩子
2.4 子节点有左右孩子
现在配合图例来分别描述这六种情况.
创建后的BST结构如下:
BST.png
1 根节点的删除
1.1 根节点没有左右孩子
很好理解,只有一个根节点,删除就好了
1.2 根节点只有左孩子
这种情况就是把根节点删除,把左孩子节点当做新的根节点
001.png
1.3 根节点只有右孩子同1.2
1.4 根节点有左右孩子(这里只考虑操作左子树的情况,右子树同理)
根据BST的特性,
左子树的右叶子<根节点<右子树的左叶子,所以当删除根节点的时候,确保BST的特性,可以将左子树的右叶子或者右子树的左叶子的值来代替根节点,并将该节点删除.1.4.1 根节点的左孩子有左右子树
002.png
1.4.2 根节点的左孩子只有右子树(同1.4.1)
1.4.3 根节点的左孩子只有左子树
003.png
1.4.4 根节点的左右孩子都没有孩子(这里只考虑左子树的操作)
004.png
2 子节点的删除
2.1 子节点没有左右孩子
删除节点既可
2.2 子节点只有左孩子
这种情况与1.4.3的情况类似,只是不用交换节点值,将子节点指向子节点的左孩子既可
2.3 子节点只有右孩子
这种情况与2.3相同.只是操作右节点
2.4 子节点有左右孩子
2.4.1 要删除的子节点在根节点的左边
与1.4.1的请相同,例如我们如果要删除5节点
004.png
006.png
2.4.2 要删除的子节点在根节点的右边
与上面相同,只是操作右子树
2.4.3 要删除的子节点有左右两个孩子,但是左孩子没有右孩子
这种情况不满足2.4.1或者2.4.2的条件,需要特别考虑
007.png
008.png
#include<stdio.h>
#include<stdlib.h>
typedef struct node {
int data;
struct node *left;
struct node *right;
} Node;
Node *newNode(int data);
Node *insert(Node *node, int data);
Node *getParent(Node *node, Node *parent, int target);
void printPreorder(Node *node);
void printInorder(Node *node);
void printPostorder(Node *node);
Node *lookup(Node *node, int target);
Node *leftLeaf(Node *node);
Node *rightLeaf(Node *node);
Node *delNode(Node *root, int target);
int main(void) {
Node *root = newNode(10);
/* following is the tree after above statement
10
/ \
NULL NULL
*/
insert(root, 5);
insert(root, 15);
/* 2 and 3 become left and right children of 1
10
/ \
5 15
/ \ / \
NULL NULL NULL NULL
*/
insert(root, 3);
/* 4 becomes left child of 2
10
/ \
5 15
/ \ / \
3 NULL NULL NULL
/ \
NULL NULL
*/
insert(root, 7);
insert(root, 8);
insert(root, 6);
// insert(root, 4);
insert(root, 2);
insert(root, 20);
/* 4 insert some node
10
/ \
5 15
/ \ \
3 7 20
/ \ / \
2 4 6 8
*/
delNode(root, 5);
printf("\n");
printf("preorder:");
printPreorder(root);//前序遍历:10--5--3--2--4--7--6--8--20
free(root);
return 0;
}
//创建新节点
Node *newNode(int data) {
Node *node = (Node *)malloc(sizeof(Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
};
//插入节点
Node *insert(Node *node, int data) {
// 1. If the tree is empty, return a new, single node
if(node == NULL) {
return newNode(data);
}
// 2. Otherwise, recur down the tree
if(data < node->data) {
node->left = insert(node->left, data);
} else {
node->right = insert(node->right, data);
}
//return the (unchanged) node pointer
return node;
}
//获取指定值的父亲节点
Node *getParent(Node *node, Node *parent, int target) {
if(node == NULL) {
return NULL;
}
if(target == node->data) {
return parent;
}
parent = node;
if(target < node->data) {
return getParent(node->left, parent, target);
} else {
return getParent(node->right, parent, target);
}
}
//前序遍历
void printPreorder(Node *node) {
if(node == NULL) {
return;
}
printf("%d--", node->data);
printPreorder(node->left);
printPreorder(node->right);
}
//中序遍历
void printInorder(Node *node) {
if(node == NULL) {
return;
}
printInorder(node->left);
printf("%d--", node->data);
printInorder(node->right);
}
//后序遍历
void printPostorder(Node *node) {
if (node == NULL) return;
// first recur on both subtrees
printPostorder(node->left);
printPostorder(node->right);
// then deal with the node
printf("%d--", node->data);
}
//左叶子节点
Node *leftLeaf(Node *node) {
if(node->left == NULL) {
return node;
}
return leftLeaf(node->left);
}
//右叶子节点
Node *rightLeaf(Node *node) {
if(node->right == NULL) {
return node;
}
return rightLeaf(node->right);
}
//查找指定值的节点
Node *lookup(Node *node, int target) {
if(node == NULL) {
return NULL;
}
if(target == node->data) {
return node;
}
if(target < node->data) {
return lookup(node->left, target);
} else {
return lookup(node->right, target);
}
}
//删除指定值的节点
Node *delNode(Node *root, int target) {
Node *node = lookup(root, target);
Node *ret = NULL;
if(node == NULL) {
return ret;
}
Node *parent = getParent(root, NULL, target);
//根节点的情况
if(parent == NULL) {
//没有左右孩子
if(node->left == NULL && node->right == NULL) {
ret = NULL;
}
//只有左孩子
if(node->left && node->right == NULL) {
ret = node->left;
}
//只有右孩子
if(node->right && node->left == NULL) {
ret = node->right;
}
//有左右孩子
if(node->left && node->right) {
//左子树的最右边叶子节点
Node *leaf = rightLeaf(node->left);
//node->left没有右子树
if(leaf == node->left) {
node->data = leaf->data;
node->left = leaf->left;
} else {
//找到叶子节点的父亲
Node *leafParent = getParent(root, NULL, leaf->data);
//交换叶子节点的值
node->data = leaf->data;
//叶子节点父亲就是操作节点
if(leafParent == node) {
//删除左子树
leafParent->left = NULL;
} else {
//删除右子树
leafParent->right = NULL;
}
}
ret = node;
}
} else {
//非根节点的情况
//没有左右孩子
if(node->left == NULL && node->right == NULL) {
//节点值>操作节点值,说明是父节点的右孩子.反之是父节点的左孩子
if(node->data > parent->data) {
parent->right = NULL;
} else {
parent->left = NULL;
}
ret = parent;
}
//只有左子树
if(node->left && node->right == NULL) {
//节点值>操作节点值,说明是父节点的右孩子.反之是父节点的左孩子
if(node->data > parent->data) {
parent->right = node->left;
} else {
parent->left = node->left;
}
ret = parent;
}
//只有右子树
if(node->right && node->left == NULL) {
//节点值>操作节点值,说明是父节点的右孩子.反之是父节点的左孩子
if(node->data > parent->data) {
parent->right = node->right;
} else {
parent->left = node->right;
}
ret = parent;
}
//有左右子树
if(node->left && node->right) {
//节点值>操作节点值,说明是父节点的右孩子.反之是父节点的左孩子
if(node->data < parent->data) {
Node *leaf = rightLeaf(node->left);
Node *leafParent = getParent(root, NULL, leaf->data);
node->data = leaf->data;
//父亲节点就是操作节点
if(leafParent == node) {
leafParent->left = leaf->left;
} else {
leafParent->right = NULL;
}
} else {
Node *leaf = leftLeaf(node->right);
Node *leafParent = getParent(root, NULL, leaf->data);
node->data = leaf->data;
//父亲节点就是操作节点
if(leafParent == node) {
leafParent->right = leaf->right;
} else {
leafParent->left = NULL;
}
}
ret = node;
}
}
return ret;
}
上面细分了6种删除节点的情况,可以总结成3种情况
1.删除节点是叶子节点
2.删除节点有左/右子树
3.删除节点有左右子树(相当于找左子树的最大值或者右子树的最小值)
//找到左子树的最大值
Node* findMax(Node* node){
return node->right ? findMax(node->right) : node;
}
//找到右子树的最小值
Node* findMin(Node* node){
return node->left ? findMax(node->left) : node;
}
Node *delNode3(Node *tree, Node *target) {
if(tree == NULL || target == NULL) {
return NULL;
}
//要删除的节点在左子树,递归删除
if(target->data < tree->data) {
tree->left = delNode3(tree->left, target);
//要删除的节点在右子树,递归删除
} else if(target->data > tree->data) {
tree->right = delNode3(tree->right, target);
} else {
//1.待删除的节点有左右子树
if(tree->left && tree->right) {
//找到左子树的最大值节点或者找到右子树的最小值节点
Node *temp = findMax(tree->left);
// Node *temp = findMin(tree->right);
//交换值
tree->data = temp->data;
//重建左子树
tree->left = delNode3(tree->left, temp);
free(temp);
} else {
//2.待删除的节点有左/右子树
if(tree->left == NULL) {
tree = tree->right;
} else if(tree->right == NULL) {
tree = tree->left;
} else {
//3.待删除的节点没有左右子树
tree = NULL;
}
}
}
return tree;
}
进行测试打印输出是否是自己需要的结果
/*
10
/ \
5 15
/ \ \
3 7 20
/ \ / \
2 4 6 8
*/
Node *t = lookup(root,10);
Node *ret = delNode3(root, t);
printPreorder(ret);//preorder:8--5--3--2--4--7--6--15--20
Node *t = lookup(root,2);
Node *ret = delNode3(root, t);
printPreorder(ret);//preorder:10--5--3--4--7--6--8--15--20
Node *t = lookup(root,5);
Node *ret = delNode3(root, t);
printPreorder(ret);//preorder:10--4--3--2--7--6--8--15--20
