二叉树系列（二）------ 二叉查找树代码实现

概念

• 二叉查找树是一种有序的存储结构，对于每个节点 X X X，它的左子树中所有节点小于X中的项，右子树所有节点大于X中的项

• 每个节点最多两个孩子

  本例中，说明下这种树结构的几种实现

• contains方法
• findMin和findMax
• insert

• remove

  下面就是一个二叉查找树

实现思路

1. contains方法

• 在树 T T T 中，查找 X X X,如果 存在，返回true,否则返回 false
• 如果 是空树返回 false,
• T 的项 和 X比较，如果X小于 T中的项，则继续在左边找，如果大于就在右边找，否则相等，返回 true

2. findMin和findMax

• 找最小的就一直遍历左边的树，找最大就遍历右边的树

3. insert

• 也是不断和节点进行对比，小的插入左边，大的插入右边，整个过程递归就行

4.remove

• 删除最复杂，要考虑要删除的项有两个节点还是一个节点
• 如果时一片叶子，直接删除就行
• 如果有一个儿子，则父节点调整一下，绕过这个节点就行

• 如果有两个儿子，用其右儿子的最小的数据替代该节点，同时删除最小项

  就像上图的，如果删除 3，直接删除，变为

如果删除4，4这个有一个子树，5直接连接3，将4 绕过去

如果要删除2 ，因为2 有两个儿子，按照原则，找到右儿子最小，所以3替换掉2 ，同时删掉3，变为

代码实现

package 树.二叉查找树;

import java.nio.BufferUnderflowException;

public class BinarySearchTree <T extends Comparable<? super T>>{
    // 1. 静态内部类定义 Node 节点
    private static class BinaryNode<T>{
        T element;
        BinaryNode left;
        BinaryNode right;

        public BinaryNode(T element) {
            this(element,null,null);
        }

        public BinaryNode(T element, BinaryNode left, BinaryNode right) {
            this.element = element;
            this.left = left;
            this.right = right;
        }
    }
    private BinaryNode<T> root;
    // 构造的是一个空树
    public BinarySearchTree() {
        root = null;
    }
    // 将 根节点设置为空，就清空了整个树
    public void makeEmpty(){
        root = null;
    }
    public boolean isEmpty(){
        return root==null;
    }
    public boolean contains(T x){
        return contains(x,root);
    }
    public T findMax(){
        if(isEmpty())
            throw new RuntimeException("树为空，不存在");
        return findMax(root).element;
    }
    public T findMin(){
        if(isEmpty())
            throw new RuntimeException("树为空，不存在");
        return findMin(root).element;
    }
    public void insert(T x){
        root = insert(x,root);
    }

    public void remove(T x){
        if(isEmpty())
            System.out.println("空树，无法删除");
        root = remove(x,root);

    }
    public void printTree(){
        if(isEmpty())
            System.out.println("空树，无法打印");
        else
            printTree(root);
    }
    public boolean contains(T x,BinaryNode<T> t){
        if(t==null) // 节点不存在，那肯定是false
            return false;
        int compareResult = x.compareTo(t.element); //比较结果
        if(compareResult>0) // 如果较大，就继续和该节点的右子节点比较
            return contains(x,t.right);
        else if(compareResult<0) // 如果较小，就继续和该节点的左子节点比较
            return contains(x,t.left);
        else  // 等于0,说明一样大，存在，返回true
            return true;
    }
    //查找最大和最小的很简单，只需要找到最左的和最右的节点
    // 最小的用递归实现
    public BinaryNode<T> findMin(BinaryNode<T> t){
        if(t==null)
            return null;
        else if(t.left==null)
            return t;
        else
            return findMin(t.left);
    }
    // 最大的用非递归
    public BinaryNode<T> findMax(BinaryNode<T> t){
        if(t!=null){
            while(t.right!=null){
                t = t.right;
            }
        }
        return t;
    }
    // 插入返回根节点就行，就是和左右进行比较，一直到比较的节点没有了左子节点或右子节点，插入到最小的额位置
    public BinaryNode<T> insert(T x,BinaryNode<T> t){
        if(t==null)
            return new BinaryNode(x,null,null);
        int compareResult = x.compareTo(t.element);
        if(compareResult<0)
            t.left = insert(x,t.left);
        else if(compareResult>0)
            t.right = insert(x,t.right);
        else
            ; // 如果相同，说明插入的值已经存在，可以什么都不做，或者做一些其他操作
        return t;
    }
    // 用中序打印的
    public void printTree(BinaryNode<T> t){
        if(t!=null){
            printTree(t.left);
            System.out.println(t.element);
            printTree(t.right);
        }
    }
    public BinaryNode<T> remove(T x,BinaryNode<T> t){
        if(t==null)
            return t;
        int compareResult = x.compareTo(t.element);
        if(compareResult<0)
            t.left = remove(x,t.left);
        else if(compareResult>0)
            t.right = remove(x,t.right);
        else if(t.left!=null && t.right!=null) // 两个子树
        {
            t.element = (T) findMin(t.right).element;
            t.right = remove(t.element, t.right);
        }
        else
            t = (t.left!=null) ? t.left:t.right;
        return t;
    }
}

           

测试

package 树.二叉查找树;

public class Test {
    public static void main(String[] args) {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insert(6);
        binarySearchTree.insert(2);
        binarySearchTree.insert(5);
        binarySearchTree.insert(1);
        binarySearchTree.insert(4);
        binarySearchTree.insert(3);
        binarySearchTree.insert(8);
        binarySearchTree.printTree();
        boolean c6 = binarySearchTree.contains(6);
        boolean c7 = binarySearchTree.contains(7);
        System.out.println("存在6？"+c6);
        System.out.println("存在7？"+c7);
        int min = (int)binarySearchTree.findMin();
        int max = (int)binarySearchTree.findMax();
        System.out.println("最小是："+min);
        System.out.println("最大是："+max);
        binarySearchTree.remove(2);
        binarySearchTree.printTree();


    }
}

           

结果打印

1
2
3
4
5
6
8
存在6？true
存在7？false
最小是：1
最大是：8
1
3
4
5
6
8
           

done!!!