查找二叉樹(shù)首先也是個(gè)二叉樹(shù)，符合二叉樹(shù)的一切特點(diǎn)。

原文地址:http://blog.csdn.net/qq_25806863/article/details/74638590

簡(jiǎn)單介紹

但是查找二叉樹(shù)要求對(duì)樹(shù)中的每個(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)的左子樹(shù)中所有的值要小于自己，右子樹(shù)中所有的值要大于自己。

下面是兩個(gè)的區(qū)別：

查找二叉樹(shù)：

查找二叉樹(shù)

不是查找二叉樹(shù)：

不是查找二叉樹(shù)

簡(jiǎn)單實(shí)現(xiàn)

主要是查詢，插入和刪除的方法

public class MySearchTree<E extends Comparable<E>> {

    private BinaryNode<E> root;

    public MySearchTree() {
        root = null;
    }

    public void makeEmpty() {
        root = null;
    }

    public boolean isEmpty() {
        return root == null;
    }

    public boolean contains(E x) {
        return contains(x, root);
    }

    public E findMin() {
        return findMin(root).element;
    }

    public E findMax() {
        return findMax(root).element;
    }

    public void insert(E x) {
        root =  insert(x, root);
    }

    public void remove(E x) {
        remove(x, root);
    }

    public void printTree() {
        printTree(root);
    }


    /**
     * 如果這個(gè)樹(shù)上的值就是要查找的x，返回true
     * 如果樹(shù)為空，說(shuō)明不存在這個(gè)值，返回false
     * 如果x小于這個(gè)樹(shù)上的值，就在這個(gè)樹(shù)的左子樹(shù)上遞歸查找
     * 如果x大于這個(gè)樹(shù)上的值，就在這個(gè)樹(shù)的右子樹(shù)上遞歸查找
     */
    private boolean contains(E x, BinaryNode<E> tree) {
        if (tree == null) {
            return false;
        }
        int compareResult = x.compareTo(tree.element);
        if (compareResult < 0) {
            return contains(x, tree.left);
        } else if (compareResult > 0) {
            return contains(x, tree.right);
        } else {
            return true;
        }
    }


    /**
     * 只要有左子樹(shù)就一直往左找，左子樹(shù)為空說(shuō)明這個(gè)就是最小值
     */
    private BinaryNode<E> findMin(BinaryNode<E> tree) {
        if (tree == null) {
            return null;
        } else if (tree.left == null) {
            return tree;
        } else {
            return findMin(tree.left);
        }

    }

    /**
     * 只要有右子樹(shù)就一直往左找，右子樹(shù)為空說(shuō)明這個(gè)就是最大值
     */
    private BinaryNode<E> findMax(BinaryNode<E> tree) {
        if (tree == null) {
            return null;
        } else if (tree.right == null) {
            return tree;
        } else {
            return findMax(tree.right);
        }
    }

    /**
     * 如果要插入的樹(shù)是null，說(shuō)明這個(gè)就是要插入的值該放的位置，new一個(gè)子樹(shù)，綁定到對(duì)應(yīng)的父親上
     * 如果樹(shù)不為null，說(shuō)明這個(gè)樹(shù)上有值，拿x和這個(gè)值進(jìn)行比較
     * 如果兩個(gè)值相等，說(shuō)明已經(jīng)有這個(gè)值了，可以進(jìn)行一些處理
     * 如果x小于樹(shù)上的值，就往該樹(shù)的左子樹(shù)上遞歸插入
     * 如果x大于樹(shù)上的值，就往該樹(shù)的右子樹(shù)上遞歸插入
     */
    private BinaryNode<E> insert(E x, BinaryNode<E> tree) {
        if (tree == null) {
            return new BinaryNode<E>(x, null, null);
        }
        int compareResult = x.compareTo(tree.element);
        if (compareResult < 0) {
            tree.left= insert(x, tree.left);
        } else if (compareResult > 0) {
            tree.right =  insert(x, tree.right);
        } else {
            //說(shuō)明已經(jīng)有這個(gè)值了。
            System.out.println("已經(jīng)有這個(gè)值了");
        }
        return tree;
    }


    /**
     * 比較x和樹(shù)的值
     * 如果x小于樹(shù)的值，在樹(shù)的左子樹(shù)中遞歸刪除
     * 如果x大于樹(shù)的值，在樹(shù)的右子樹(shù)中遞歸刪除
     * 如果x等于樹(shù)的值，那么這個(gè)值就是要?jiǎng)h除的值。
     * 因?yàn)閯h除一個(gè)值就要對(duì)樹(shù)進(jìn)行重新排列，所以這個(gè)位置上不能空。
     * 如果這個(gè)樹(shù)只有一個(gè)子樹(shù)，那么就直接把這個(gè)子樹(shù)放在這個(gè)位置上
     * 如果這個(gè)樹(shù)有兩個(gè)子樹(shù)，那么需要找到右子樹(shù)的最小值，將這個(gè)最小值賦值在要?jiǎng)h除的位置上，
     * 然后遞歸調(diào)用從右子樹(shù)中刪除剛剛找到的這個(gè)最小值
     */
    private BinaryNode<E> remove(E x, BinaryNode<E> tree) {
        if (tree == null) {
            //沒(méi)有這個(gè)樹(shù)
            return tree;
        }
        int compareResult = x.compareTo(tree.element);
        if (compareResult < 0) {
            tree.left = remove(x, tree.left);
        } else if (compareResult > 0) {
            tree.right = remove(x, tree.right);
        } else if (tree.left != null && tree.right != null) {
            tree.element = findMin(tree.right).element;
            tree.right = remove(tree.element, tree.right);
        } else {
            tree = (tree.left != null) ? tree.left : tree.right;
        }
        return tree;

    }

    private void printTree(BinaryNode<E> tree) {
        if (tree == null) {
            return;
        }
        System.out.print(tree.element+" ");
        printTree(tree.left);
        printTree(tree.right);

    }

    public static class BinaryNode<E> {
        E element;
        BinaryNode<E> left;
        BinaryNode<E> right;

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

        public BinaryNode(E element, BinaryNode<E> left, BinaryNode<E> right) {
            this.element = element;
            this.left = left;
            this.right = right;
        }
    }
}

實(shí)現(xiàn)的缺點(diǎn)

在代碼中，注意remove方法中的一段代碼：

else if (tree.left != null && tree.right != null) {
    tree.element = findMin(tree.right).element;
    tree.right = remove(tree.element, tree.right);

這里對(duì)刪除的處理是，找到右子樹(shù)中的最小值，把這個(gè)最小值放在當(dāng)前節(jié)點(diǎn)上，然后從右子樹(shù)中刪除這個(gè)值。

而在insert的時(shí)候，是根據(jù)比較而隨機(jī)的插入在左右子樹(shù)上的。

所以如果交叉調(diào)用insert和remove很多次的話，這個(gè)二叉樹(shù)會(huì)變得很不平衡，即左右子樹(shù)的高度差很大。

這種平衡的查找二叉樹(shù)叫平衡查找樹(shù)。

一個(gè)最古老的平衡查找樹(shù)是AVL樹(shù)。

參考《數(shù)據(jù)結(jié)構(gòu)與算法分析java版》