二叉搜索树

二叉搜索树（BST）binary search tree，左边节点小于等于跟节点，右边节点大于等于根节点，就是一个有序的树，自带递归特性，因为每个子树也都是一颗BST
老规矩盗一张图

BST

查找

二叉树的查找代码比较简单直接看一下,底下的节点定义和树构建和上一篇完全二叉树及遍历方式基本一样的，重点就是getNode方法和getNodeNumber方法。

public class Bst {
    public static void main(String[] args) {
        BstNode n = getNodeNumber(13, createNote());
        if (n != null) {
            System.out.println("找到了-->>" + n.getValue());
        } else {
            System.out.println("not exists");
        }
    }

    /**
     * 递归版本
     * @param v
     * @param node
     * @return
     */
    public static BstNode getNode(int v, BstNode node) {
        if (node == null) {
            return null;
        }
        if (node.getValue() == v) {
            return node;
        } else if (node.getValue() > v) {
            return getNode(v, node.getLeft());
        } else {
            return getNode(v, node.getRight());
        }

    }
    /**
     * 非递归版本
     * @param v
     * @param node
     * @return
     */
    public static BstNode getNodeNumber(int v, BstNode node) {
        while (node != null) {
            if (node.getValue() == v) {
                return node;
            }else if(node.getValue()>v){
                node = node.getRight();
            }else if(node.getValue()<v){
                node = node.getLeft();
            }
        }
        return null;
    }


    public static BstNode createNote() {
        BstNode four = new BstNode(4, null, null);
        BstNode seven = new BstNode(7, null, null);
        BstNode thirteen = new BstNode(13, null, null);
        BstNode one = new BstNode(1, null, null);
        BstNode six = new BstNode(6, four, seven);
        BstNode fourteen = new BstNode(14, thirteen, null);
        BstNode ten = new BstNode(10, null, fourteen);
        BstNode three = new BstNode(3, one, six);
        BstNode eight = new BstNode(8, three, ten);
        return eight;
    }

    static class BstNode {
        int value;
        BstNode left;
        BstNode right;

        public BstNode(int value, BstNode left, BstNode right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }

        public int getValue() {
            return value;
        }

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

        public BstNode getLeft() {
            return left;
        }

        public void setLeft(BstNode left) {
            this.left = left;
        }

        public BstNode getRight() {
            return right;
        }

        public void setRight(BstNode right) {
            this.right = right;
        }
    }
}

插入

插入新节点，和查找是一样的，也是一个递归的过程。再把图放一下

BST

假设要插入节点的值是5
1.和8比
2.和3比
3.和6比
4.和4比，放在4的右节点

假设要插入节点的值是18
1.和8比
2.和10比
3.和14比
4.放14的右节点

通过这个顺序可以看出来，就是一个查找，没的比较了 就放在谁的下面 大于放右 小于放左。
代码

  public static void insertNode(BstNode node, int v) {

        if (node.getValue() > v) {
            if (node.getLeft() != null) {
                insertNode(node.getLeft(), v);
            } else {
                node.setLeft(new BstNode(v, null, null));
            }
        }
        if (node.getValue() < v) {
            if (node.getRight() != null) {
                insertNode(node.getRight(), v);
            } else {
                node.setRight(new BstNode(v, null, null));
            }
        } else {
            System.out.println("节点已存在");
            return ;
        }

    }

debug查看18节点

通过debug可以看到已经放到了14的右子节点

debug查看5节点

通过debug可以看到已经放到了4的右子节点