文章目录
简介
二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；
二叉搜索树介绍
二叉排序树：BST（Binary Search Tree），对于二叉搜索树的任何一个非叶子结点。要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。
特别说明：如果有相同的值，可以将该节点放在左子节点或者右子节点。
二叉搜索树是能够高效地进行如下操作的数据结构
- 插入一个数值
- 查询是否包含某个数值
- 删除某个数值
在二叉搜索树中：
- 若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。
- 若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。
- 任意结点的左、右子树也分别为二叉搜索树。
比如数据（7，3，10，12，5，1，9），对应的二叉排序树为
再次基础上插入2：
二叉树的中序遍历
如上图 中序遍历（先输出左子节点然后是当前节点最后是右节点）后的输出为：
1，2，3，5，7，9，10，12
为递增序列
代码：
Node节点中的方法：（以便于在tree中调用）
public void infixOrder() {
if (this.left != null) {
this.left.infixOrder();
}
System.out.println(this);
if (this.right != null) {
this.right.infixOrder();
}
}
在二叉搜索树中的中序遍历：
public void infixOrder(){
if (root!=null){
root.infixOrder();
}else {
System.out.println("树为空，无法遍历");
}
}
插入结点
插入结点比较简单，主要逐个比较要插入结点，与当前结点的值的大小即可，如果小于当前结点的值。就继续往左边找，大于等于往右边找；
代码：
Node结点中的add代码
//添加结点的方法
public void add(Node node) {
if (node == null) {
return;
}
if (node.getData() < this.getData()) {
//如果小就往左边插入
if (this.left == null) {
this.left = node;
} else {
this.left.add(node);
}
//大于等于向右添加
} else {
if (this.right == null) {
this.right = node;
} else {
this.right.add(node);
}
}
}
BinarySortTree 中的插入结点的代码：
public void add(Node node) {
if (root == null) {
root = node;
} else {
root.add(node);
}
}
删除结点
- 叶子节点：直接删除，不影响原树。
思路：
1.首先找到需要删除的结点 targetNode
2.找到targetNode的父节点parent
3.根据targetNode是parent结点的左子节点还是右子结点
4.根据对应的情况进行删除
如果是parent的左子节点：parent.left = null；
如果是parent的右子节点：parent.right = null；
- 仅仅有左或右子树的节点：节点删除后，将它的左子树或右子树整个移动到删除节点的位置就可以，子承父业。
思路：
1.首先找到需要删除的结点 targetNode
2.找到targetNode的父节点parent
3.根据targetNode是parent结点的左子节点还是右子结点
4.1如果是parent的左子节点
如果target.left=null,那么令parent.left = target.right即可
如果target.right = null，那么令parent.left = target.left即可
4.2如果是parent的右子节点
如果target.left=null,那么令parent.right = target.right即可
如果target.right = null，那么令parent.right = target.left即可
- 既有左又有右子树的节点：找到须要删除的节点p的直接前驱或者直接后继s，用s来替换节点p，然后再删除节点s。
思路：
上面我们可以直到中序遍历的结果是一个升序的输出，那么我们是不是可以找一个结点代替这个要删除的结点，找那个了，就找输出序列根target相邻的结点，即左子树的最大值，或者右子树的最小值，具体是那个？你如果你插入值得时候相同得值放在右子树，那么删除得时候就找左子树得最大值，反之亦然。
1.首先找到需要删除的结点 targetNode
2.找到targetNode的父节点parent
3.从target得左子树或者右子树找到代替得点
4.用一个临时变量保存这个结点
5.然后删除这个结点
6.令target.value = temp.value即可
代码实现：
Node中得查找目标结点，查找父节点
//查找要删除的结点
public Node search(int value) {
//如果要查找的值等于当前结点的值 则直接返回
if (this.getData() == value) {
return this;
}
//如果不是当前值，并且要查找的值小于当前结点的值 则往左边进行查找
if (value < this.data) {
//如果左结点不为空 则向左查找
if (this.getLeft() != null) {
return this.getLeft().search(value);
} else {//为空则直接返回null 即没找到
return null;
}
} else {//在右边查找
//右子结点不为空 在右边查找
if (this.getRight() != null) {
return this.getRight().search(value);
} else {
return null;
}
}
}
//得到要删除结点的父节点
public Node searchParent(int value) {
//如果要删除的是根节点 逻辑在tree中处理即可
//如果当前结点的子结点就是要删除的结点 则直接返回
if ((this.left != null && this.left.data == value) || (this.right != null && this.right.data == value)) {
return this;
} else {
//如果查找的值 小于当前结点的值 就向左边查找
if (value < this.data && this.left != null) {
return this.left.searchParent(value);
} else if (value >= this.data && this.right != null) {//向右
return this.right.searchParent(value);
} else {
return null;
}
}
}
BinarySortTree中得删除代码：
public void deleteNode(int value){
//如果数为空 则直接结束
if (root==null){
return;
}
//首先得到目标结点
Node target = search(value);
//如果没有找到 则直接结束
if (target==null){
return;
}
//如果二叉树只有根节点 说明待删除的结点就是根节点
if (root.getLeft()==null && root.getRight()==null){
root = null;
return;
}
//得到父节点 开始删除
Node parent = searchParent(value);
if (target.getLeft()==null && target.getRight()==null){//需要删除得是叶子结点
//进行判断需要删除得结点得父结点
if (parent.getLeft()==target){
parent.setLeft(null);
}else {
parent.setRight(null);
}
}else if (target.getLeft()!=null && target.getRight()!=null){//有两个结点得时候
int min = GetMaxNode(target.getLeft());
target.setData(min);
}else {//删除单节点
//如果删除得是左子树
if (target.getLeft()!=null){
if (parent!=null){
if (parent.getLeft()==target){
parent.setLeft(target.getLeft());
}else {
parent.setRight(target.getLeft());
}
}else {
root = target.getLeft();
}
}else {//删除右子树
if (parent!=null){
if (parent.getLeft()==target){
parent.setLeft(target.getRight());
}else {
parent.setRight(target.getRight());
}
}else {
root = target.getRight();
}
}
}
}
//得到当前子树得最小值
private int GetMaxNode(Node node){
Node target =node;
while (target.getRight()!=null){
target = target.getRight();
}
deleteNode(target.getData());
return target.getData();
}
//得到需要删除的结点
private Node search(int value){
if (root == null){
return null;
}
return root.search(value);
}
//得到需要删除的父节点
private Node searchParent(int value){
if (root!=null){
if (value==root.getData()){
return null;
}else {
return root.searchParent(value);
}
}
return null;
}
完整代码：
Node结点：
package binarysorttree;
/**
* @ClassName: Node
* @Author
* @Date 2022/1/25
*/
public class Node {
private int data;
private Node left;
private Node right;
//构造方法
public Node(int data) {
this.data = data;
}
//添加结点的方法
public void add(Node node) {
if (node == null) {
return;
}
if (node.getData() < this.getData()) {
//如果小就往左边插入
if (this.left == null) {
this.left = node;
} else {
this.left.add(node);
}
//大于等于向右添加
} else {
if (this.right == null) {
this.right = node;
} else {
this.right.add(node);
}
}
}
//查找要删除的结点
public Node search(int value) {
//如果要查找的值等于当前结点的值 则直接返回
if (this.getData() == value) {
return this;
}
//如果不是当前值，并且要查找的值小于当前结点的值 则往左边进行查找
if (value < this.data) {
//如果左结点不为空 则向左查找
if (this.getLeft() != null) {
return this.getLeft().search(value);
} else {//为空则直接返回null 即没找到
return null;
}
} else {//在右边查找
//右子结点不为空 在右边查找
if (this.getRight() != null) {
return this.getRight().search(value);
} else {
return null;
}
}
}
//得到要删除结点的父节点
public Node searchParent(int value) {
//如果要删除的是根节点 逻辑在tree中处理即可
//如果当前结点的子结点就是要删除的结点 则直接返回
if ((this.left != null && this.left.data == value) || (this.right != null && this.right.data == value)) {
return this;
} else {
//如果查找的值 小于当前结点的值 就向左边查找
if (value < this.data && this.left != null) {
return this.left.searchParent(value);
} else if (value >= this.data && this.right != null) {//向右
return this.right.searchParent(value);
} else {
return null;
}
}
}
//中序遍历
public void infixOrder() {
if (this.left != null) {
this.left.infixOrder();
}
System.out.println(this);
if (this.right != null) {
this.right.infixOrder();
}
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
'}';
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
}
BinarySortTree代码：
package binarysorttree;
/**
* @ClassName: BinarySortTree
* @Author
* @Date 2022/1/25
*/
public class BinarySortTree {
Node root = null;
public void add(Node node) {
if (root == null) {
root = node;
} else {
root.add(node);
}
}
public void deleteNode(int value){
//如果数为空 则直接结束
if (root==null){
return;
}
//首先得到目标结点
Node target = search(value);
//如果没有找到 则直接结束
if (target==null){
return;
}
//如果二叉树只有根节点 说明待删除的结点就是根节点
if (root.getLeft()==null && root.getRight()==null){
root = null;
return;
}
//得到父节点 开始删除
Node parent = searchParent(value);
if (target.getLeft()==null && target.getRight()==null){//需要删除得是叶子结点
//进行判断需要删除得结点得父结点
if (parent.getLeft()==target){
parent.setLeft(null);
}else {
parent.setRight(null);
}
}else if (target.getLeft()!=null && target.getRight()!=null){//有两个结点得时候
int min = GetMaxNode(target.getLeft());
target.setData(min);
}else {//删除单节点
//如果删除得是左子树
if (target.getLeft()!=null){
if (parent!=null){
if (parent.getLeft()==target){
parent.setLeft(target.getLeft());
}else {
parent.setRight(target.getLeft());
}
}else {
root = target.getLeft();
}
}else {//删除右子树
if (parent!=null){
if (parent.getLeft()==target){
parent.setLeft(target.getRight());
}else {
parent.setRight(target.getRight());
}
}else {
root = target.getRight();
}
}
}
}
//得到当前子树得最小值
private int GetMaxNode(Node node){
Node target =node;
while (target.getRight()!=null){
target = target.getRight();
}
deleteNode(target.getData());
return target.getData();
}
//得到需要删除的结点
private Node search(int value){
if (root == null){
return null;
}
return root.search(value);
}
//得到需要删除的父节点
private Node searchParent(int value){
if (root!=null){
if (value==root.getData()){
return null;
}else {
return root.searchParent(value);
}
}
return null;
}
public void infixOrder(){
if (root!=null){
root.infixOrder();
}else {
System.out.println("树为空，无法遍历");
}
}
}
测试代码：
package binarysorttree;
/**
* @ClassName: Test
* @Author
* @Date 2022/1/25
*/
public class Test {
public static void main(String[] args) {
BinarySortTree bs = new BinarySortTree();
int[] arr = {7,7,3,10,12,5,1,9};
for (int i : arr){
bs.add(new Node(i));
}
System.out.println("插入后");
bs.infixOrder();
bs.deleteNode(7);
bs.deleteNode(3);
bs.deleteNode(10);
bs.deleteNode(12);
bs.deleteNode(5);
bs.deleteNode(1);
bs.deleteNode(9);
bs.deleteNode(9);
System.out.println("-----------------");
System.out.println("删除后");
bs.infixOrder();
}
}
结果：