二叉查找树

树
- 树的概念
二叉查找树

树

树的概念

一棵树是N个节点和N-1条边的集合。其中最顶端的节点，称为根(root)。根节点使用若干根线连接着若干个节点，这些节点即是根节点的子节点(child)，而根节点则是这些子节点的父节点(parent)。没有子节点的节点称为叶子节点(leaf)。拥有相同父节点的节点称为兄弟。

一棵树.jpg
上图即为一棵普通的树，A为该树的根节点。
对于一棵树，我们还需了解两个重要的概念：

深度：对于任意一个节点，深度(depth)是从根节点到该节点的唯一路径的长。例如上图中K节点的深度为2，而整棵树的深度则为最大深度为P、Q节点的深度3。
高度：对于任意一个节点，高度(height)是从该节点到一个叶子节点的最长路径的长。例如E节点的高度为2，而D节点的高度为1。一棵树的高度总是等于它的深度。
二叉查找树
二叉树以及二叉查找树
我们已经了解了树的一些基本概念。接下来我们学习特殊一点的树，二叉树(binary tree)以及它的升级版二叉查找树(binary search tree)。

二叉树：每个节点都不能有多于两个子节点的树，即为二叉树

而使二叉树成为二叉查找树的性质是，对于树中的每个节点X，它的左子节点的值总是小于右子节点的值。
两棵二叉树.jpg
如上图所示的两棵树，只有左边的树才是二叉查找树。
从以上内容我们了解了何为二叉查找树，然后我们需要使用程序语言定义一棵树，并写出它的一些基本操作方法，比如contains()、insert()、remove()、findMin()以及findMax()。

用Java语言定义一棵二叉树

private static class BinaryNode<T extends Comparable<T>> {
    T element;
    BinaryNode<T> left;
    BinaryNode<T> right;
    BinaryNode(T element) {
          this(element, null, null);
    }
    BinaryNode(T element, BinaryNode<T> left, BinaryNode<T> right) {
        this.element = element;
        this.left = left;
        this.right = right;
    }
}

一个二叉树节点中，包含该节点的元素，以及左右节点的引用。

contains方法

如果树T中存在含有X的节点，返回true，否则返回false

private boolean contains(T x, BinaryNode<T> t) {
    if (t == null)
          return false;
    int compareResult = x.compareTo(t.element);
    if (compareResult < 0)
          return contains(x, t.left);
    else if (compareResult > 0)
          return contains(x, t.right);
    else
          return true;
}

将X与节点T的值比对，如果小于，则再与T的左节点比对，如果大于，与右节点比对。如此递归比对，直到找到相等的值的节点。或者找到一个叶子节点上，依然没有找到，则该树中不含有该节点X。

insert方法

插入.jpg

上图是插入5之前和之后的二叉查找树
我们可以像contains方法一样遍历树，找到合适的位置后，将数据插入。

private 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);
    return t;
}

findMin方法和findMax方法

这两个方法分别返回树中最小元素的节点和最大元素的节点。查找最小元素，只需要从根节点开始，一直往左边遍历过去即可，同样，向右则能找到最大的元素的节点。
使用递归编写findMin方法并使用非递归实现findMax方法：

private BinaryNode<T> findMin(BinaryNode<T> t) {
    if (t == null)
          return null;
    else if (t.left == null)
          return t;
    return findMin(t.left);
}
private BinaryNode<T> findMax(BinaryNode<T> t) {
    if (t != null) {
        while (t.right != null)
              t = t.right;
    }
    return t;
}

remove方法

删除一个节点，我们需要考虑几种可能情况。
如果节点是叶子节点，那么它可以被立即删除。如果节点有一个子节点，则让子节点替代该节点。如果具有两个子节点，一般的删除策略是用其右子树的最小的数据代替该节点的数据并递归地删除那个节点。

private BinaryNode<T> remove(T x, BinaryNode<T> t) {
    if (t == null)
            return null;
    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 = findMin(t.right).element;
            t.right = remove(t.element, t.right);
    } else {
            t = t.left != null ? t.left : t.right;
    }
    return t;
}

树

树的概念