二叉排序树(BST)

2024-05-30 17:05:21 浏览数 (2)

二叉排序树（Binary Sort Tree）

前言： 二叉排序树是二叉树中十分重要的一种，又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。

Node节点类代码

代码语言：javascript复制
package day7_test;

public class Node {
    public int val;
    public Node right;
    public Node left;

    /**
     * 查找要删除的节点并返回
     * @param index 要删除的节点的val值
     * @return 返回要删除的节点
     */
    public  Node searchNode(int index){

        if(this.val == index){
            return this;
        }else if(index < this.val) {
            if(this.left == null){
                return null;
            }else{
                return this.left.searchNode(index);
            }
        }else {
            if (this.right == null){
                return null;
            }else {
                return this.right.searchNode(index);
            }
        }
    }

    /**
     * 找到要删除的节点的父节点
     * @param index 要删除的节点的索引
     * @return 返回父节点
     */
    public Node searchParent(int index){
        //情况一： 当前节点就是要删除节点的父节点
        if((this.left != null && this.left.val == index) ||(this.right != null && this.right.val == index)){
            return this;
        }else {
            //左节点不为空，并且左节点就是parent
            if(index < this.val && this.left != null){
                return this.left.searchParent(index);
            }else if (index >= this.val && this.right != null){
                return this.right.searchParent(index);
            }else {
                return null;
            }
        }
    }
    //添加节点
    public void add(Node node){
        if(node == null){
            return;
        }
        if(node.val < this.val){
            if(this.left == null){
                this.left = node;
            }else{
                this.left.add(node);
            }
        }else{
            //node.val >= this.val
            if(this.right == null){
                this.right = node;
            }else{
                this.right.add(node);
            }
        }
    }

    //中序遍历二叉树
    public void infix(){
        if(this.left != null){
            this.left.infix();
        }
        System.out.println(this);

        if (this.right != null){
            this.right.infix();
        }
    }
    public Node(int val) {
        this.val = val;
    }
    @Override
    public String toString() {
        return "Node["  
                "val="   val  
                ']';
    }
}

二叉排序树的添加功能

思路：

每传进来一个node节点，我们就与当前节点进行比较

  1. node的val值 < 当前节点的val值： ​ 向左进行递归，一直递归到this.left == null时，加入node节点
  2. node的val值 >= 当前节点的val值： ​ 向右进行递归，知道this.right == null时，加入node节点

代码实现：

代码语言：javascript复制
   //添加节点
public void add(Node node){
    if(node == null){
        return;
    }
    if(node.val < this.val){
        if(this.left == null){
            this.left = node;
        }else{
            this.left.add(node);
        }
    }else{
        //node.val >= this.val
        if(this.right == null){
            this.right = node;
        }else{
            this.right.add(node);
        }
    }
}

结果：

Node[val=0] Node[val=1] Node[val=3] Node[val=5] Node[val=7] Node[val=9] Node[val=10] Node[val=12]

二叉排序树删除功能详解

思路：

首先分三种情况进行处理：

① 所删除的节点为叶子节点（left 和right 节点上为空）

② 所删除的节点为非叶子节点，并且left 或 right节点上只有一个不为空

③ 所删除的节点为非叶子节点，并且left 和 right 都不为空

在处理这三种情况之前，先再Node节点类中增添方法，用来查询要删除的目标节点targetNode 以及targetNode的父节点 parent节点

代码如下：

代码语言：javascript复制
/**
 * 查找要删除的节点并返回
 * @param index 要删除的节点的val值
 * @return 返回要删除的节点
 */
public  Node searchNode(int index){

    if(this.val == index){
        return this;
    }else if(index < this.val) {
        if(this.left == null){
            return null;
        }else{
            return this.left.searchNode(index);
        }
    }else {
        if (this.right == null){
            return null;
        }else {
            return this.right.searchNode(index);
        }
    }
}

/**
 * 找到要删除的节点的父节点
 * @param index 要删除的节点的索引
 * @return 返回父节点
 */
public Node searchParent(int index){
    //情况一： 当前节点就是要删除节点的父节点
    if((this.left != null && this.left.val == index) ||(this.right != null && this.right.val == index)){
        return this;
    }else {
        //左节点不为空，并且左节点就是parent
        if(index < this.val && this.left != null){
            return this.left.searchParent(index);
        }else if (index >= this.val && this.right != null){
            return this.right.searchParent(index);
        }else {
            return null;
        }
    }
}
情况一：删除的是叶子节点
步骤：【
  1. 找到目标节点targetNode 及其它的父节点 parent
  2. 确定targetNode是parent的left节点 还是right 节点
  3. parent.left = null 或 parent.right = null ;

】

代码：

代码语言：javascript复制
Node targetNode = root.searchNode(index);
if (targetNode == null){
      System.out.println("没有找到要删除的节点！");
    return;
}
if (root.left == null && root.right == null){
    root = null;
    return;
}
Node parent = root.searchParent(index);
//要删除的是叶子节点
if(targetNode.left == null && targetNode.right == null){
    if(parent.left!= null && parent.left.val == targetNode.val){
        parent.left = null;
    }else if(parent.right != null && parent.right.val == targetNode.val ) {
        parent.right = null;
    }
}
情况二：要删除的节点只有一个子节点
步骤【
  1. 找到父节点和targetNode目标节点后
  2. 先判断targetNode的left 和right 是否为空 ，如果不为空再判断是否有parent节点，因为很可能这个节点是root节点 ，root节点没有parent节点
  3. 接下来就是四种判断 targetNode 有左节点 ，targetNode是parent的左节点；—–> parent.left = targetNode.left;

​ targetNode 有左节点 ，targetNode是parent的右节点；—–> parent.right = targetNode.left;

​ targetNode 有右节点 ，targetNode是parent的左节点；—–>parent.left = targetNode.right;

​ targetNode 有右节点 ，targetNode是parent的右节点；—–>parent.right = targetNode.right;

】

代码实现：

代码语言：javascript复制
//要删除的节点只有一个子节点
else{
    if(targetNode.left != null){
        //要删除的节点有左子节点
        if(parent != null){
            if (parent.left == targetNode){
                parent.left = targetNode.left;
            }else{
                parent.right = targetNode.left;
            }
        }else {
            root = targetNode.left;
        }
    }
    else {
        if(parent != null){
            if (parent.left == targetNode){
                parent.left = targetNode.right;
            }else{
                parent.right = targetNode.right;
            }
        }else {
            root = targetNode.right;
        }
    }
}
情况三：要删除的节点只有一个子节点

这种情况我们有两种解决办法

步骤 【

​ 方法一：以当前要删除的节点为根节点，找到left边的最大值，然后用临时变量保存值，删除该最大值所在的节点

​ 方法二：以当前要删除的节点为根节点，找到right边的最小值，然后用临时变量保存值，删除该最小值所在的节点

】

代码实现：

代码语言：javascript复制
            //要删除的是有两个子节点的节点
            else if (targetNode.left != null && targetNode.right !=null){
                /*
                  方法一：以当前要删除的节点为根节点，找到left边的最大值，然后用临时变量保存值，删除该最大值所在的节点
                  方法二：以当前要删除的节点为根节点，找到right边的最小值，然后用临时变量保存值，删除该最小值所在的节点
                 */
//                int tempMin = 0;
//                Node tempNode = targetNode.right;
//                while(tempNode.left != null){
//                    tempNode = tempNode.left;
//                }
//                tempMin = tempNode.val;
//                deleteNode(tempMin);
//                targetNode.val = tempMin;
                int tempMax = 0;
                Node tempNode = targetNode.left;
                while(tempNode.right != null){
                    tempNode = tempNode.right;
                }
                tempMax = tempNode.val;
                deleteNode(tempMax);
                targetNode.val = tempMax;
            }

main方法代码

代码语言：javascript复制
public static void main(String[] args) {
    int arr[] ={7,3,10,12,5,1,9,0};
    BinarySortTree b = new BinarySortTree();
    for(int i=0;i<arr.length;i  ){
        b.add(new Node(arr[i]));
    }
    b.infix(b.root);
    b.deleteNode(3);
    b.deleteNode(12);
    b.deleteNode(5);
    b.deleteNode(1);
    b.deleteNode(7);
    b.deleteNode(9);
    b.deleteNode(10);
    b.deleteNode(0);

    System.out.println("删除之后~~~");
    b.infix(b.root);

}

整体代码实现：

代码语言：javascript复制
package day7_test;

public class BinarySortTree {
    public Node root;

    public static void main(String[] args) {
        int arr[] ={7,3,10,12,5,1,9,0};
        BinarySortTree b = new BinarySortTree();
        for(int i=0;i<arr.length;i  ){
            b.add(new Node(arr[i]));
        }
        b.infix(b.root);
        b.deleteNode(3);
        b.deleteNode(12);
        b.deleteNode(5);
        b.deleteNode(1);
        b.deleteNode(7);
        b.deleteNode(9);
        b.deleteNode(10);
        b.deleteNode(0);

        System.out.println("删除之后~~~");
        b.infix(b.root);

    }

    /**
     * 删除二叉树节点
     * @param index 要删除的节点的val值
     */
    public void deleteNode(int index){
        if (root == null){
            return;
        }
        else{
            Node targetNode = root.searchNode(index);
            if (targetNode == null){
                  System.out.println("没有找到要删除的节点！");
                return;
            }
            if (root.left == null && root.right == null){
                root = null;
                return;
            }
            Node parent = root.searchParent(index);
            //要删除的是叶子节点
            if(targetNode.left == null && targetNode.right == null){
                if(parent.left!= null && parent.left.val == targetNode.val){
                    parent.left = null;
                }else if(parent.right != null && parent.right.val == targetNode.val ) {
                    parent.right = null;
                }
            }
            //要删除的是有两个子节点的节点
            else if (targetNode.left != null && targetNode.right !=null){
                /*
                  方法一：以当前要删除的节点为根节点，找到left边的最大值，然后用临时变量保存值，删除该最大值所在的节点
                  方法二：以当前要删除的节点为根节点，找到right边的最小值，然后用临时变量保存值，删除该最小值所在的节点
                 */
//                int tempMin = 0;
//                Node tempNode = targetNode.right;
//                while(tempNode.left != null){
//                    tempNode = tempNode.left;
//                }
//                tempMin = tempNode.val;
//                deleteNode(tempMin);
//                targetNode.val = tempMin;
                int tempMax = 0;
                Node tempNode = targetNode.left;
                while(tempNode.right != null){
                    tempNode = tempNode.right;
                }
                tempMax = tempNode.val;
                deleteNode(tempMax);
                targetNode.val = tempMax;
            }
            //要删除的节点只有一个子节点
            else{
                if(targetNode.left != null){
                    //要删除的节点有左子节点
                    if(parent != null){
                        if (parent.left == targetNode){
                            parent.left = targetNode.left;
                        }else{
                            parent.right = targetNode.left;
                        }
                    }else {
                        root = targetNode.left;
                    }
                }
                else {
                    if(parent != null){
                        if (parent.left == targetNode){
                            parent.left = targetNode.right;
                        }else{
                            parent.right = targetNode.right;
                        }
                    }else {
                        root = targetNode.right;
                    }
                }
            }
        }
    }

    //添加节点
    public void add(Node node){
        if (root == null){
            root = node;
        }else {
            root.add(node);
        }
    }
    //中序遍历
    public void infix(Node root){
        if (root == null){
            System.out.println("空树！");
            return;
        }
        root.infix();
    }
}

运行结果：

删除3 后 Node[val=0] Node[val=1] Node[val=5] Node[val=7] Node[val=9] Node[val=10] Node[val=12] 删除3,12,5,1 后 Node[val=0] Node[val=7] Node[val=9] Node[val=10] 删除3,12,5,1,7,9 后 Node[val=0] Node[val=10] 删除所有的之后 空树！

变量 排序 null parent return

0 人点赞