1、每个节点最多有两个子节点,分别为左子节点和右子节点。
2、左子节点的值小于或等于父节点的值。右子节点的值大于父节点的值。
3、对BST进行中序遍历,可以得到升序排列的节点值序列。
从根节点开始,比较待插入的值与当前节点的值。
若待插入的值小于当前节点的值,移至左子树;否则,移至右子树。
重复以上步骤,直到找到一个为空的位置,将待插入的值放入此位置。
从根节点开始,比较待查找的值与当前节点的值。
若待查找的值等于当前节点的值,返回当前节点;若小于当前节点的值,移至左子树;否则,移至右子树。
重复以上步骤,直到找到目标值或者遇到空节点。
先查找到待删除节点。
如果节点没有子节点,直接删除;如果有一个子节点,用子节点替代待删除节点;
如果有两个子节点,用右子树中的最小值节点(或左子树的最大值节点)替代待删除节点,然后删除最小值节点(或最大值节点)。
元素:54,25,36,47,36,88,11,86,60
import java.util.ArrayList;
import java.util.Arrays;
class TreeNode {
Integer val;
TreeNode left, right;
public TreeNode(Integer val) {
this.val = val;
}
}
public class Test2 {
public static void main(String[] args) {
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(54, 25, 36, 47, 36, 88, 11, 86, 60
));
// 构建BST
TreeNode root = null;
for (Integer val : arr) {
if (root == null) {
root = new TreeNode(val);
}
addNode(root, val);
}
// 54 25 11 36 47 88 86 60
dlr(root);
System.out.println();
ldr(root);
System.out.println();
System.out.println(searchNode(root, 1));
System.out.println(searchNode(root, 54));
System.out.println(searchNode(root, 33));
// del
assert root != null;
final int delVal = 54;
delNode(root, delVal, null);
dlr(root);
System.out.println();
ldr(root);
}
private static void del(TreeNode node, TreeNode preRoot) {
// 判断节点是否存在子节点 若不存在直接删除该节点
if (node.left == null && node.right == null) {
// 判断 node 是 preRoot 的左节点还是右节点
if (node.val > preRoot.val) {
preRoot.right = null;
} else {
preRoot.left = null;
}
} else if (node.left == null) {
preRoot.right = node.right;
} else if (node.right == null) {
preRoot.left = node.left;
} else {
// 使用左子树的最大节点代替待删除节点并删除最大节点
TreeNode maxNode;
if (node.left.right == null) {
maxNode = node;
preRoot.left = maxNode.left;
} else {
maxNode = getAndDelLeftTreeMax(node.left, node);
}
node.val = maxNode.val;
}
}
/**
* 获取最大左子树最大节点,并移除该节点
*
* @param node
* @param preRoot
* @return
*/
private static TreeNode getAndDelLeftTreeMax(TreeNode node, TreeNode preRoot) {
if (node.right == null) {
preRoot.right = node.left;
return node;
}
return getAndDelLeftTreeMax(node.right, node);
}
/**
* if not found ,return -1
* or return searchVal
*
* @param root
* @param searchVal
* @return
*/
private static Integer searchNode(TreeNode root, int searchVal) {
if (root == null) {
return -1;
}
if (root.val == searchVal) {
return root.val;
} else if (searchVal > root.val) {
return searchNode(root.right, searchVal);
} else {
return searchNode(root.left, searchVal);
}
}
/**
* 删除树中的节点值
*
* @param root
* @param val
* @param preNode
* @return
*/
private static boolean delNode(TreeNode root, int val, TreeNode preNode) {
if (root == null) {
return false;
}
if (root.val == val) {
del(root, preNode);
return true;
} else if (val > root.val) {
return delNode(root.right, val, root);
} else {
return delNode(root.left, val, root);
}
}
/**
* 添加节点
*
* @param node
* @param val
*/
private static void addNode(TreeNode node, Integer val) {
if (node.val.equals(val)) {
return;
}
if (node.val > val) {
if (node.left != null) {
addNode(node.left, val);
} else {
node.left = new TreeNode(val);
}
} else {
if (node.right != null) {
addNode(node.right, val);
} else {
node.right = new TreeNode(val);
}
}
}
/**
* 先根遍历
*
* @param root
*/
private static void dlr(TreeNode root) {
// 二叉树的先根遍历
if (root != null) {
System.out.print(root.val + " ");
dlr(root.left);
dlr(root.right);
}
}
/**
* 中根遍历
*
* @param root
*/
private static void ldr(TreeNode root) {
// 二叉树的先根遍历
if (root != null) {
ldr(root.left);
System.out.print(root.val + " ");
ldr(root.right);
}
}
}
👋 你好,我是 Lorin 洛林,一位 Java 后端技术开发者!座右铭:Technology has the power to make the world a better place.
🚀 我对技术的热情是我不断学习和分享的动力。我的博客是一个关于Java生态系统、后端开发和最新技术趋势的地方。
🧠 作为一个 Java 后端技术爱好者,我不仅热衷于探索语言的新特性和技术的深度,还热衷于分享我的见解和最佳实践。我相信知识的分享和社区合作可以帮助我们共同成长。
💡 在我的博客上,你将找到关于Java核心概念、JVM 底层技术、常用框架如Spring和Mybatis 、MySQL等数据库管理、RabbitMQ、Rocketmq等消息中间件、性能优化等内容的深入文章。我也将分享一些编程技巧和解决问题的方法,以帮助你更好地掌握Java编程。
🌐 我鼓励互动和建立社区,因此请留下你的问题、建议或主题请求,让我知道你感兴趣的内容。此外,我将分享最新的互联网和技术资讯,以确保你与技术世界的最新发展保持联系。我期待与你一起在技术之路上前进,一起探讨技术世界的无限可能性。
📖 保持关注我的博客,让我们共同追求技术卓越。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。