本文共 4816 字，大约阅读时间需要 16 分钟。

二叉搜索树

1. 二叉搜索树是一种特殊的二叉树，TreeSet,TreeMap的底层实现结构
   1）根节点的左子树的值都比根节点的值小
   2）根节点的右子树的值都比根节点的值大
2. 中序遍历二叉搜索树，得到的是一个有序序列
   最核心的用途：用来查找元素
   3.二叉树的操作：查找，插入，删除

插入操作

public static class Node {
           int key;        Node left;        Node right;        Node root=null;        public Node(int key) {
               this.key = key;        }    }    //根节点,root为空的时候表示这是个空树    private Node root = null;    public Node find(int key) {
           //查找key是否在树中存在，如果存在·返回对应的Node        Node cur = root;        while (cur != null) {
               if (key < cur.key) {
                   //就去左子树中找                cur = cur.left;            } else if (key > cur.key) {
                   //就去右子树中找找                cur = cur.right;            } else {
                   //相等就是找到了                return cur;            }        }        //循环结束之后也没找到，key就不存在        return null;    }

插入操作

先找到待插入元素的合适位置，再插入元素

//二叉搜索树中不允许存在相同的key的元素    //如果发现新插入的key重复了，那就插入失败，返回false    //插入成功返回true    public boolean insert(int key) {
           if (root == null) {
               //如果当前树为空树，直接让root指向key对应的新节点即可            root = new Node(key);            return true;        }        //和查找类似，需要先找到合适的位置，再去插入元素        Node cur = root;        Node parent = null;  //parent始终指向cur的父节点        while (cur != null) {
               if (key < cur.key) {
                   parent = cur;                cur = cur.left;            } else if (key > cur.key) {
                   parent = cur;                cur = cur.right;            } else {
                   //找到了和待插入元素值相同的元素                //插入失败                return false;            }        }        //循环结束的时候，cur就指向null，当前元素就要插入到parent的子树位置上        //再比较看是插入到左子树还是右子树        if (key < parent.key) {
               parent.left = new Node(key);        } else {
               parent.right = new Node(key);        }        return true;    }

删除操作

需要考虑多种情况

public boolean remove(int key){
           //key在树中存在，就删除成功        //key在树中不存在，就删除失败        //找到待删除元素后，再去判定是a-f中的哪一种情况        Node cur=root;        Node parent=null;        while(cur!=null){
               if(key
   
    cur.key){
                   parent=cur;                cur=cur.right;            }else {
                   removeNode(parent,cur);                return true;            }        }        return false;    }    private void removeNode(Node parent, Node cur) {
           if(cur.left==null){
               //1.要删除的元素没有左子树            if(cur==root){
                   //1.1要删除的节点为根节点                root=cur.right;            }else if(cur==parent.left){
                   //1.2 cur是parent的左子树，对应情况a                //如果cur也没有右子树，则相当于parent.left=null                parent.left=cur.right;            }else{
                   //1.3cur是parent的右子树，对应情况b                parent.right=cur.right;            }        }else if(cur.right==null){
               //2.要删除的元素没有右子树            if(cur==root){
                   //2.1要删除的为根节点                root=cur.left;            }else if(cur==parent.left){
                   //2.2 cur是parent的左子树，对应情况c                parent.left=cur.left;            }else{
                   //2.3 cur是parent的右子树，对应情况d                parent.right=cur.left;            }        }else{
               //3.左右子树都不为空,对应情况e和f            //1）先找到右子树中的最小元素            Node goatParent=cur;            Node scopeGoat=cur.right;            while(scopeGoat.left!=null){
                   goatParent=scopeGoat;                scopeGoat=scopeGoat.left;            }            //循环结束时，scopeGoat指向了右子树中的最小值            //2）把刚才找到的替罪羊的值赋给待删除结点            cur.key=scopeGoat.key;            //3)删除替罪羊结点            //替罪羊结点一定没有左子树（和情况a,b类似）            if(scopeGoat==goatParent.left){
                   goatParent.left=scopeGoat.right;            }else{
                   goatParent.right=scopeGoat.right;            }        }    }
   

public void preOrder(Node root){
           if(root==null){
               return;        }        System.out.print(root.key+" ");        preOrder(root.left);        preOrder(root.right);    }    public void inOrder(Node root){
           if(root==null){
               return;        }        inOrder(root.left);        System.out.print(root.key+" ");        inOrder(root.right);    }    public static void main(String[] args) {
           BinarySearchTree tree=new BinarySearchTree();        tree.insert(9);        tree.insert(5);        tree.insert(2);        tree.insert(7);        tree.insert(3);        tree.insert(6);        tree.insert(8);        //为了查看到树的结构，打印出先序和中序遍历结果        tree.preOrder(tree.root);        System.out.println();        tree.inOrder(tree.root);        System.out.println();        Node cur=tree.find(100);        System.out.println(cur);        tree.remove(5);        tree.preOrder(tree.root);        System.out.println();        tree.inOrder(tree.root);    }}

总结

转载地址：http://xdlzi.baihongyu.com/