简介

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

一棵空树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

【注】：以上的三种定义在不同的数据结构教材中均有不同的定义方式 但是都是正确的 在开发时需要根据不同的需求进行选择

【注2】：没有键值相等的结点。

代码实现

package com.zyp.tree;

/**
 * 二叉排序树
 * @author zyp
 * @create 2022/3/24
 */
public class BinarySortTree {
    private BinaryNode root;

    public static void main(String[] args){
        int[] array = new int[]{7,3,10,12,5,1,9,2,11};
        BinarySortTree binarySortTree = new BinarySortTree();
        for(int i = 0;i<array.length;i++ ){
            binarySortTree.addNode(new BinaryNode(array[i]));
        }
        binarySortTree.infixOrder();
//        binarySortTree.deleteNode(2);
//        binarySortTree.deleteNode(10);
        binarySortTree.deleteNode(12);
        System.out.println("----------------------------------");
        binarySortTree.infixOrder();

    }

    /**
     * 添加节点
     * @param binaryNode 被添加的节点
     */
    public void addNode(BinaryNode binaryNode){
        if(this.root == null){
            root = binaryNode;
        }else{
            root.addNode(binaryNode);
        }
    }

    /**
     * 中序排序
     */
    public void infixOrder(){
        if(this.root == null){
            return;
        }else{
            this.root.infixOrder();
        }
    }

    /**
     * 查询节点
     * @param value 节点的值
     * @return
     */
    public BinaryNode queryNode(int value){
        if(this.root == null){
            return null;
        }else{
            return this.root.queryNode(value);
        }
    }

    /**
     * 查询父节点
     * @param value 节点的值
     * @return
     */
    public BinaryNode queryParentNode(int value){
        if(this.root == null){
            return null;
        }else{
            return this.root.queryParentNode(value);
        }
    }


    /**
     * 删除节点
     * @param value 节点的值
     */
    public void deleteNode(int value){
        //先查询到被删除的节点
        BinaryNode deleteNode = queryNode(value);
        if (deleteNode == null) {
            return;
        }
        //查询被删除节点的父节点
        BinaryNode parentNode = queryParentNode(value);
        //说明要删除的就是顶级节点
        if (parentNode == null) {
            if (deleteNode.getLeftNode() == null && deleteNode.getRightNode() == null) {
                this.root = null;
            }else if(deleteNode.getLeftNode() != null && deleteNode.getRightNode() != null){
                int minValue = deleteNode(deleteNode.getRightNode());
                this.root.setValue(minValue);
            }else{

            }
        } else {
            //说明是叶子节点
            if (deleteNode.getLeftNode() == null && deleteNode.getRightNode() == null) {
                //判断被删除的节点是做节点还是右节点
                if (parentNode.getValue() > deleteNode.getValue()) {
                    parentNode.setLeftNode(null);
                } else {
                    parentNode.setRightNode(null);
                }
            } else if (deleteNode.getLeftNode() != null && deleteNode.getRightNode() != null) {//说明被删除的存在两个子节点
                int minValue = deleteNode(deleteNode.getRightNode());
                deleteNode.setValue(minValue);
            } else {//说明被删除的存在一个子节点
                //判断被删除的节点的子节点是左子节点还是右子节点
                BinaryNode binaryNode;
                if(deleteNode.getLeftNode() != null){
                    binaryNode = deleteNode.getLeftNode();
                }else{
                    binaryNode = deleteNode.getRightNode();
                }
                //判断被删除的节点是做节点还是右节点
                if (parentNode.getValue() > deleteNode.getValue()) {
                    parentNode.setLeftNode(binaryNode);
                } else {
                    parentNode.setRightNode(binaryNode);
                }
            }
        }


    }

    /**
     * 删除节点，并返回该节点下的最小值
     * @param node 节点
     * @return 该节点下的最小值
     */
    public int deleteNode(BinaryNode node){
        BinaryNode leftNode = node;
        while(leftNode.getLeftNode() != null){
            leftNode = leftNode.getLeftNode();
        }
        deleteNode(leftNode.getValue());
        return leftNode.getValue();
    }


}

class BinaryNode {
    private int value;
    private BinaryNode leftNode;
    private BinaryNode rightNode;

    public BinaryNode(int value) {
        this.value = value;
    }


    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public BinaryNode getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(BinaryNode leftNode) {
        this.leftNode = leftNode;
    }

    public BinaryNode getRightNode() {
        return rightNode;
    }

    public void setRightNode(BinaryNode rightNode) {
        this.rightNode = rightNode;
    }

    /**
     * 添加节点
     * @param binaryNode 被添加的节点
     */
    public void addNode(BinaryNode binaryNode){
        if(this.value > binaryNode.getValue()){
            if(this.leftNode == null){
                this.setLeftNode(binaryNode);
            }else{
                this.leftNode.addNode(binaryNode);
            }
        }else{
            if(this.rightNode == null){
                this.setRightNode(binaryNode);
            }else{
                this.rightNode.addNode(binaryNode);
            }
        }
    }

    /**
     * 中序排序
     */
    public void infixOrder(){
        if(this.leftNode != null){
            this.leftNode.infixOrder();
        }
        System.out.println(this);
        if (this.rightNode != null){
            this.rightNode.infixOrder();
        }
    }


    /**
     * 根据节点的值查询对应的节点
     * @param value 节点的值
     * @return
     */
    public BinaryNode queryNode(int value){
        if(this.value == value){
            return this;
        }else if(this.value <= value){
            if(this.getRightNode() == null){
                return null;
            }else{
                return this.getRightNode().queryNode(value);
            }
        }else{
            if(this.leftNode == null){
                return null;
            }
            return this.getLeftNode().queryNode(value);
        }
    }

    /**
     * 查询父节点
     * @param value 节点的值
     * @return 父节点
     */
    public BinaryNode queryParentNode(int value){
        if(this.value == value){
            return null;
        }else if(this.value > value){
            if(this.getLeftNode() == null){
                return null;
            }else{
                if(this.getLeftNode().value == value){
                    return this;
                }else{
                    return this.getLeftNode().queryParentNode(value);
                }
            }
        }else{
            if(this.getRightNode() == null){
                return null;
            }else{
                if(this.getRightNode().value == value){
                    return this;
                }else{
                    return this.getRightNode().queryParentNode(value);
                }
            }
        }
    }

    @Override
    public String toString() {
        return "BinaryNode{" +
                "value=" + value +
                '}';
    }
}

代码分析

添加节点：从顶级节点开始，如果顶级节点为空，第一个加入的就作为，顶级节点。如果顶级节点不为空，则比较节点的值，如果添加的节点比当前节点的值大，则在树的右边继续比较添加。如果添加的节点比当前节点的值小，则在树的左边继续比较添加

查询节点：将查找的值和树的节点进行比较，从树的顶级节点开始比较，如果查找的值大于节点的值，将继续向树的右边进行查找。如果查找的值小于节点的值，将继续向树的左边进行查找

删除节点:先要找到要删除的节点。

1）如果要删除的节点是叶子节点

只要将它的父节点指向null即可

2）如果删除的节点下有一个子节点

要将它的父节点指向该子节点即可

3）如果删除的节点下有两个字节点

要将找到该右子树中最小的值，来替换要删除的节点的值即可