二叉搜索树

前言

树是数据结构中必学的一种数据结构。在实际应用中，常见的树结构有二叉搜索树、B树、B+树、AVL树、红黑树、字典树等。
对应的用途列举如下：

• B/B+树：主要用于文件系统以及数据库中做索引
• AVL树：平衡二叉树，windows对进程地址空间的管理用到了AVL
• 红黑树：平衡二叉树的一种改进，广泛的应用在C++STL中，如map、set，以及JDK中的HashMap、TreeMap等
• Trie（字典树）：又经常叫做前缀树，主要用于字符串检索、文本预测、词频统计等

二叉搜索树（BST Binary Search Tree）

概述

二叉搜索树也叫做二叉排序树，二叉搜索树采用二分思维将数据按照规则组装在一个树形结构中，大大提高了数据检索的效率。对于一颗普通的二叉树进行中序遍历，即可获取一个有序的数序列

特点

• 非空左子树的所有键值小于根节点的值
• 非空右子树的所有键值大于根节点的值
• 左右子树都是二叉搜索树

局限性

从图中可见，在改变一串数列组内顺序后，会得到不同的二叉搜索树。最好的情况下，搜索数据的时间复杂度为O(logN)，最坏的情况下，该树会退化为线性表，导致时间复杂度变为O(N)，因此，在二叉搜索树的基础上，又衍生出了AVL树和红黑树。后者基于二叉搜索树，做出了更多的限制。

代码实现

首先，我们需要构建一颗二叉树。首当其冲，我们顶一个数的节点类

public class Node<T extends Comparable<T>> {

    /**
     * 数据域
     */
    public T data;

    /**
     * 节点子树的高度
     */
    public int height;

    /**
     * 左孩子
     */
    public Node<T> leftChild;

    /**
     * 右孩子
     */
    public Node<T> rightChild;

    public Node(T data) {
        this(data, null, null);
    }

    public Node(T data, Node<T> leftChild, Node<T> rightChild) {
        this.data = data;
        this.leftChild = leftChild;
        this.rightChild = rightChild;
    }

}

data字段由于不限定传入的对象类型，在这里使用泛型可以很好的规范

构建二叉树

public class BsTree<T extends Comparable<T>> {

    private Node<T> root;

    public void createTree(T data) {
        if (data == null) {
            return;
        }
        root = insert(root, data);
    }

    private Node<T> insert(Node<T> root, T data) {
        // 根节点为空，说明树为空，则创建一颗树
        if (root == null) {
            return new Node<>(data);
        } else {
            if (compare(root, data) > 0) {
                root.leftChild = insert(root.leftChild, data);
            } else if (compare(root, data) < 0) {
                root.rightChild = insert(root.rightChild, data);
            }
            return root;
        }
    }

    private T getMin(Node<T> root) {
        Node<T> temp = root;
        while (temp.leftChild != null) {
            temp = temp.leftChild;
        }
        return temp.data;
    }

    private T getMax(Node<T> root) {
        Node<T> temp = root;
        while (temp.rightChild != null) {
            temp = temp.rightChild;
        }
        return temp.data;
    }


    private int compare(Node<T> root, T data) {
        return root.data.compareTo(data);
    }

    public void printTree() {
        System.out.print("前序遍历： ");
        preOrder(root);
        System.out.println();
        System.out.print("中序遍历： ");
        inOrder(root);
        System.out.println();
        System.out.print("后序遍历： ");
        postOrder(root);
        System.out.println();
    }

    private void preOrder(Node<T> root) {
        if (root != null) {
            System.out.print(root.data);
            System.out.print(" ");
            preOrder(root.leftChild);
            preOrder(root.rightChild);
        }
    }

    private void inOrder(Node<T> root) {
        if (root != null) {
            inOrder(root.leftChild);
            System.out.print(root.data);
            System.out.print(" ");
            inOrder(root.rightChild);
        }
    }

    private void postOrder(Node<T> root) {
        if (root != null) {
            postOrder(root.leftChild);
            postOrder(root.rightChild);
            System.out.print(root.data);
            System.out.print(" ");
        }
    }
}

• createTree方法，每当要插入一个新节点时，便调用该函数。该函数会递归的搜索整棵树，确保找到一个合适的位置插入新的节点（比根节点小则插在左子树，大则插在右子树）
• printTree方法，用于打印建造完成的树。底层提供前序、中序、后序三种遍历方式
• compare方法用于比较两个节点的大小，这里简单使用hashcode来作比较。众所周知，Integer对象的hashcode即为本身

删除节点

在二叉搜索树中，删除一个节点算是相当复杂的一份工作。主要面临三种情况

• 节点为叶子节点，则直接删除
• 只包含左子树或者右子树的节点，则将父节点指向待删除的节点的唯一直接子节点
• 包含左右子树的节点，则寻找右子树最小值或左子树最大值替换该节点

示例代码：

public void deleteNode(T data) {
    if (data == null) {
        return;
    }
    root = delete(root, data);
}

private Node<T> delete(Node<T> root, T data) {
    if (compare(root, data) < 0) {
        root.rightChild = delete(root.rightChild, data);
    } else if (compare(root, data) > 0) {
        root.leftChild = delete(root.leftChild, data);
    } else {
        // 该节点拥有左右子树
        if (root.leftChild != null && root.rightChild != null) {
            T temp = getMin(root.rightChild);
            root.data = temp;
            root.rightChild = delete(root.rightChild, temp);
        } else {
            if (root.leftChild != null) {
                root = root.leftChild;
            } else {
                root = root.rightChild;
            }
        }
    }
    return root;
}

其中，getMin方法用于寻找树中的最小节点。在一颗二叉排序树中，一目了然的，最小节点就是这棵树最靠左的节点

private T getMin(Node<T> root) {
       Node<T> temp = root;
       while (temp.leftChild != null) {
           temp = temp.leftChild;
       }
       return temp.data;
}

测试检验

编写单元测试，检验结果：

private static final Integer[] arrays = new Integer[]{50, 66, 60, 26, 21, 30, 70, 68};

@Test
public void createBsTree() {
    BsTree<Integer> bsTree = new BsTree<>();
    for (Integer data : arrays) {
        bsTree.createTree(data);
    }
    bsTree.printTree();
}

@Test
public void deleteNode() {
    BsTree<Integer> bsTree = new BsTree<>();
    for (Integer data : arrays) {
        bsTree.createTree(data);
    }
    bsTree.deleteNode(50);
    bsTree.printTree();
}

其中createBsTree方法建立的二叉搜索树为：

前序遍历： 50 26 21 30 66 60 70 68 
中序遍历： 21 26 30 50 60 66 68 70 
后序遍历： 21 30 26 60 68 70 66 50 

deleteNode方法测试结果为：

前序遍历： 60 26 21 30 66 70 68 
中序遍历： 21 26 30 60 66 68 70 
后序遍历： 21 30 26 68 70 66 60 

观察得到，中序遍历的结果就是一组升序排列的数列

相关代码可以在 https://github.com/Cheung0-bit/tree-practice 中找到