详解二叉搜索树 (BST) 的 Java 实现和五种遍历方式
//用来记录我们插入的节点的父节点
TreeNode<E> parent = null;
//记作当前节点
TreeNode<E> current = root;
//current 为 null，跳出循环，parent 节点代表我们要插入元素的父节点
while (current != null) {
//如果我们要插入的节点小于当前节点，就去遍历其左子树
//否则遍历右子树
if (o.compareTo(current.element) < 0) {
parent = current;
current = current.left;
} else if (o.compareTo(current.element) > 0) {
parent = current;
current = current.right;
} else {
//树中存在当前要插入的元素，则插入失败
return false;
}
}
//比较当前元素和父节元素的大小
if (o.compareTo(parent.element) < 0) {
//小于父节点的元素，则新建元素节点作为父节点的左节点
parent.left = new TreeNode<>(o);
} else {
//大于父节点的元素，则新建元素节点作为父节点的右节点
parent.right = new TreeNode<>(o);
}
}
//当前树种存储的元素+1
size++;
return true;
}
当我们需要在 BST 中查找一个节点时，就从根节点从下扫描，直到找到匹配的元素或者达到一个空子树(树中不存在当前要查找的元素)，下面我们来看下它的 Java 实现：
//返回 true 表示查询成功，false 表示没右查询到
public boolean search(E o) {
//记录遍历时的当前节点
TreeNode<E> current = root;
while (current != null) {
//小于当前节点元素遍历其左子树
if (o.compareTo(current.element) < 0) {
current = current.left;
/大于当前节点元素遍历其右子树
} else if (o.compareTo(current.element) > 0) {
current = current.right;
} else {
//查到
return true;
}
}
return false;
}
当我们要在 BST 中删除一个元素，首先需要定位该元素的位置。然后在删除它时，比插入的时候要复杂一点，因为需要考虑两种情况：
1.当前元素节点没有左子节点。
2.当前元素节点右左子节点。
下面我们直接从代码角度来看看如何来删除一个节点：
//删除成功返回 true,否则返回 false
public boolean de
lete(E o) {
//指向当前节点的父节点
TreeNode<E> parent = null;
//指向当前节点
TreeNode<E> current = root;
//遍历二叉树
while (current != null) {
if (o.compareTo(current.element) < 0) {
parent = current;
current = current.left;
} else if (o.compareTo(current.element) > 0) {
parent = current;
current = current.right;
} else {
//找到跳出循环 current 就是要删除的节点
break;
}
}
//如果为 null 返回 false
if (current == null) {
return false;
}
//如果要删除的节点没有左节点
if (current.left == null) {
//如果当前要删除节点是根节点，当前节点的右子节点作为根节点。
if (parent == null) {
root = current.right;
} else {
//比较当前要删除的元素和父节点元素的大小
//如果当前要删除的元素是父节点的左子节点
//当前节点的右子节点作为父节点的左子节点
if (o.compareTo(parent.element) < 0) {
parent.left = current.right;
} else {
//如果当前要删除的元素是父节点的右子节点
//当前节点的右子节点作为父节点的右子节点
parent.right = current.right;
}
}
} else {
//如果存在要删除的节点存在左子节点,找到 current 的左子树的最大元素节点
//parentOfRightMost 指向 最大元素节点的父节点
//最大元素节点不会存在右节点只会存在左节点(如果存在，就不是最大了)
TreeNode<E> parentOfRightMost = current;
TreeNode<E> rightMost = current.left;
while (rightMost.right != null) {
parentOfRightMost = rightMost;
rightMost = rightMost.right;
}
//最大元素节点替换要删除的节点
current.element = rightMost.element;
//如果最大元素节点是其父节点的右节点，左子节点作为父元素的右子节点
if (parentOfRightMost.right == rightMost) {
parentOfRightMost.right = rightMost.left;
} else {
//如果最大元素节点是其父节点的左节点 左子节点作为父元素的左子节点
parentOfRightMost.left = rightMost.left;
}
}
size--;
return true;
}
还未添加个人签名 2021.10.31 加入
还未添加个人简介
评论