二叉排序树删除功能模块
时间: 2023-08-21 18:32:50 浏览: 36
二叉排序树的删除操作比较复杂,需要分多种情况进行讨论,具体步骤如下:
1. 如果要删除的节点是叶子节点(没有子节点):直接删除该节点即可;
2. 如果要删除的节点只有一个子节点:将该节点的子节点替代该节点即可;
3. 如果要删除的节点有两个子节点:找到该节点右子树中的最小节点(即该节点右子树中最左侧的节点),用该节点的值替代要删除的节点的值,然后删除该最小节点。
实现这个功能模块的方法,可以采用递归和迭代两种方式。递归方式相对简单,可以通过以下伪代码实现:
```
TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return null;
}
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 && root.right == null) {
root = null;
} else if (root.right != null) {
root.val = successor(root);
root.right = deleteNode(root.right, root.val);
} else {
root.val = predecessor(root);
root.left = deleteNode(root.left, root.val);
}
}
return root;
}
int successor(TreeNode root) {
root = root.right;
while (root.left != null) {
root = root.left;
}
return root.val;
}
int predecessor(TreeNode root) {
root = root.left;
while (root.right != null) {
root = root.right;
}
return root.val;
}
```
迭代方式则需要借助一个辅助指针进行遍历,可以通过以下伪代码实现:
```
TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return null;
}
TreeNode cur = root, pre = null;
while (cur != null && cur.val != key) {
pre = cur;
if (key < cur.val) {
cur = cur.left;
} else {
cur = cur.right;
}
}
if (cur == null) {
return root;
}
if (cur.left == null || cur.right == null) {
TreeNode child = cur.left != null ? cur.left : cur.right;
if (pre == null) {
root = child;
} else if (pre.left == cur) {
pre.left = child;
} else {
pre.right = child;
}
} else {
TreeNode successor = cur.right, preSuc = cur;
while (successor.left != null) {
preSuc = successor;
successor = successor.left;
}
cur.val = successor.val;
if (preSuc.left == successor) {
preSuc.left = successor.right;
} else {
preSuc.right = successor.right;
}
}
return root;
}
```
这样,我们就可以通过二叉排序树删除模块实现节点的删除操作。