手写一个二叉搜索树（BST）

余生大大

发布于 2022-11-02 16:36:07

2900

发布于 2022-11-02 16:36:07

文章被收录于专栏：余生大大余生大大

前言

在上一篇写了一个简单的双向链表，难度是简简单单，这次来尝试二叉树，难度是也还行吧，多少有点夸张的成分了，不过对于大佬来说这些就是简简单单。

难度列表：

集合：有手就行
链表：简简单单
队列：基础操作
二叉树：也还行吧
平衡二叉树：普普通通
红黑树：有点难度了
堆/栈：难度提升了
图：今天是高端局

属性

二叉树是有一个根节点的，大部分操作都是基于根节点进行向下处理，所以需要显式的定义一个根节点root。

private Node root;

二叉树的每个节点都有左右节点跟它自身的属性值，所以Node内容中需要有左右节点的属性left和right，至于自身属性Demo还是用数值类型Integer

代码如下：

    private class Node{
        private Node left;
        private Node right;
        private Integer data;
        
        public Node(Integer data){
            this.data = data;
        }
        
    }

ADD

第一步：判断root是否为空，为空则初始化root节点，否则执行add方法

    private void add(int data) {
        if (Objects.isNull(root)){
            root = new Node(data);
        }else{
            root.add(data);
        }
    }

第二步：add方法，判断参数值是否小于节点值，小于挪移到左节点处理，大于挪移到右节点处理

        private void add(Integer data) {
            if (this.data >= data){
                // left
            }else{
                // right
            }
        }

第三步：判断左/右节点是否为空，为空则初始化节点，否则递归进行add方法

        private void add(Integer data) {
            if (this.data >= data){
                if (Objects.isNull(this.left)){
                    this.left = new Node(data);
                }else{
                    this.left.add(data);
                }
            }else{
                if (Objects.isNull(this.right)){
                    this.right = new Node(data);
                }else{
                    this.right.add(data);
                }
            }
        }

GET

二叉搜索树查询值有三种遍历方式：

前序遍历
中序遍历
后续遍历

这里不每一个都将了，就选择最常用的中序遍历作为我们查询值内容的遍历方式

代码如下：

        public Node get(Integer data) {
            Node now = this;
            if (now.data == data){
                return now;
            }else{
                if (now.left != null){
                    Node left = now.left.get(data);
                    if (left != null){
                        return left;
                    }
                }
                if (now.right != null){
                    Node right = now.right.get(data);
                    if (right != null){
                        return right;
                    }
                }
            }
            return null;
        }

Delete

删除操作是二叉搜索树里最复杂的了，根据删除节点的不同需要进行调整，分类有以下几类：

叶子节点：叶子节点是左右节点属性都没有的节点，这种的可以直接删除
单向非叶子节点：单向非叶子节点代表左右节点只有一个节点存在，这种的直接将指向删除节点的指针指向子节点即可
双向非叶子节点：如果删除节点的左右节点都存在，这种的是最复杂的，因为如果删除这种节点需要对子节点进行挪移，找到左节点的最右节点进行替换现在删除节点的位置，之前节点位置删除。

删除代码：

        public Node delete(Node parrent, Integer data) {
            if (this != null){
                if (this.data == data){
                    if (this.left == null && this.right == null){
                        if (parrent.left != null && parrent.left.data == data){
                            parrent.left = null;
                        }else {
                            parrent.right = null;
                        }
                    }else if(this.left != null && this.right == null){
                        parrent.left = this.left;
                    }else if(this.left == null && this.right != null){
                        parrent.right = this.right;
                    }else{
                        Node node = this.left.getRightNode(this.left);
                        node.left = this.left;
                        node.right = this.right;
                        if (parrent.left != null && parrent.left.data == data){
                            parrent.left = node;
                        }else {
                            parrent.right = node;
                        }
                    }
                }else{
                    if (data > this.data) {
                        this.right.delete(this,data);
                    } else {
                        this.left.delete(this,data);
                    }
                    return this;
                }
            }
            return null;
        }

获取最左叶子节点并删除返回

这个获取最左节点的方式我写了两种，一种是递归、一种是循环

递归方式：

        private Node getRightNode(Node node){
            if(this.right != null){
            	return this.right.getRightNode(this);
            }
            node.right = null;
            return this;
        }

循环方式：

        private Node getRightNode(Node node){
            Node now = this;
            Node buffer = this;
            while(now.right != null){
                buffer = now;
                now = now.right;
            }
            buffer.right = null;
            return now;
        }

验证

往树结构内写入部分数据并删除其中节点，查看输出内容是否对应。

代码如下：

    public static void main(String[] args) {
        OrdinaryBinaryTree tree = new OrdinaryBinaryTree();
        tree.add(4);tree.add(7);tree.add(8);tree.add(2);
        tree.add(-1);tree.add(3);tree.add(0);tree.add(11);tree.add(14);tree.add(21);tree.add(9);
        tree.print();
        tree.delete(2);
        tree.print();
    }

结果：