本篇文章总结二叉搜索树(BST)相关操作的Java实现代码,包括结点添加,结点的删除等方法。

1.结点的创建

1.1基本结构

首先构建二叉排序树结点的基本结构,也就是一个POJO,该结点类有三个属性,一个存放数据,两个指向左右子结点的指针变量。

class Node{
    int value;
    Node left;
    Node right;

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

    public int getValue() {
        return value;
    }

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

    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;
    }

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

1.2 中序遍历

要想让BST按值的大小顺序遍历,我们需要实现中序遍历:

//中序遍历
public void infixOrder(){
    if(this.left != null){
        this.left.infixOrder();
    }
    System.out.println(this);
    if(this.right != null){
        this.right.infixOrder();
    }
}

1.3 结点删除

对于BST结点的删除,共有三种情况,无论哪种情况都需要我们先找到要删除的目标节点以及目标节点的父结点,因此我们在结点类中实现这样个方法:

//找到要删除的结点
public Node search(int value){
    if(this.value == value){
        return this;
    }else if(this.value > value) {
        if(this.left == null){
            return null;
        }else {
            return this.left.search(value);
        }
    }else{
        if(this.right == null){
            return null;
        }else{
            return this.right.search(value);
        }
    }
}


//查找要删除结点的父结点
public Node searchParent(int value){
    //如果当前节点的左子节或右子结点不为空,且左子结点或右子结点就是要找的节点
    if((this.left != null && this.left.value == value)
        || (this.right != null && this.right.value == value )){
        return this;
    }else{
        if(value < this.value && this.left != null){
            //向左递归查找
            return  this.left.searchParent(value);
        }else if(value >= this.value && this.right != null){
            //向右递归查找
            return this.right.searchParent(value);
        }else{
            //没有父结点
            return null;
        }
    }
}

2.树的创建

在创建树的类中,我们要设置树的根节点,并以根节点为出发点,实现节点添加、遍历、寻找目标删除节点,寻找目标删除结点的父结点等函数,重头戏是实现三种情况的节点删除。

2.1 基本实现

class BinarySortTree{
    private Node root;

    //添加节点的方法
    public void add(Node node){
        if(root == null){
            root = node;
        }else{
            root.add(node);
        }
    }

    //遍历的方法
    public void infixOrder(){
        if(root != null){
            root.infixOrder();
        }else{
            System.out.println("二叉排序树为空,不能遍历");
        }
    }

    //查找要删除的节点
    public Node search(int value){
        if(root != null){
            return root.search(value);
        }else{
            return null;
        }
    }


    //查找要删除节点的父结点
    public Node searchParent(int value){
        if(root != null){
            return root.searchParent(value);
        }else{
            return null;
        }
    }
}

2.2 结点删除

//删除节点
public void deleNode(int value){
    if(root == null){
        return;
    }

    //查找要删除的结点
    Node tartgetNode = search(value);
    //如果没有要删除的结点,那么就直接返回
    if(tartgetNode == null){
        return;
    }

    //当二叉树只有一个结点,也就是根节点
    if(root.left == null && root.right ==null){
        root = null;
        return;
    }

    //查找待删除节点的父结点
    Node parentNode = searchParent(value);

    //情况一:待删除节点为叶子节点
    if(tartgetNode.left == null && tartgetNode.right == null){
        //判断待删除节点是父结点的左子树还是右子树
        if(parentNode.left != null && parentNode.left.value == value){
            //是左子树,那么把父结点左子树置为空
            parentNode.left = null;
        }else if(parentNode.right != null && parentNode.right.value == value){
            //是右子树,那么把父结点右子树置为空
            parentNode.right = null;
        }
    //情况二:待删除节点有两个子结点
    }else if(tartgetNode.left !=null && tartgetNode.right !=null){
        int minVal = deleteRightTreeMin(tartgetNode.right);
        tartgetNode.value = minVal;
    //情况三:待删除节点有一个子结点,需要判断该节点属于父结点的左还是右结点
    }else{
        //判断它是否有父结点
        if(parentNode != null){
            //该节点属于父结点左子节点
            if(parentNode.left != null && parentNode.left.value == value){
                if(parentNode != null){
                    //判断目标节点有左子节点还是右子结点
                    if(tartgetNode.left != null){
                        //将目标左子节点作为父结点的左子节点
                        parentNode.left = tartgetNode.left;
                    }else if(tartgetNode.right != null){
                        parentNode.left = tartgetNode.right;
                    }
                }
            }else if(parentNode.right != null && parentNode.right.value == value){
                //判断目标节点有左子节点还是右子结点
                if(tartgetNode.left != null){
                    //将目标左子节点作为父结点的左子节点
                    parentNode.right = tartgetNode.left;
                }else if(tartgetNode.right != null){
                    parentNode.right = tartgetNode.right;
                }
            }
        }else{
            if(tartgetNode.left!=null){
                root = tartgetNode.left;
            }else{
                root = tartgetNode.right;
            }
        }
    }
}

//删除右子树最小结点,并获取最小节点的值
public int deleteRightTreeMin(Node node){
    Node target = node;
    //循环查找最小的节点
    while (target.left != null){
        target = target.left;
    }
    //删除最小节点
    int minVal = target.value;
    deleNode(minVal);
    return minVal;
}

3.实现测试

这一节我们将测试刚刚写好的二叉排序树的功能,包括节点的添加、删除:

public class BSTCreateAndOrder {
    public static void main(String[] args) {
        int[] array = {7,3,10,12,5,1,9,0};
        BinarySortTree binarySortTree = new BinarySortTree();
        //循环添加节点到二叉排序树
        for(int i : array){
            binarySortTree.add(new Node(i));
        }

        //测试叶子节点删除
        System.out.println("删除前");
        binarySortTree.infixOrder();
        binarySortTree.deleNode(0);
        binarySortTree.deleNode(5);
        binarySortTree.deleNode(9);
        binarySortTree.deleNode(12);
        binarySortTree.deleNode(7);
        binarySortTree.deleNode(3);
        binarySortTree.deleNode(10);
        binarySortTree.deleNode(1);

        System.out.println("删除后");
        binarySortTree.infixOrder();
    }
}

参考资料

尚硅谷-韩顺平图解Java数据结构和算法