二叉查找树Java实现

二叉查找树

首先是一棵二叉树，使其称为查找树的关键性质是其某节点的左子树中任意值都小于该节点，右子树中任意值都大于该节点。

代码如下：

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

    private TreeNode<T> root = null;
    private LinkedList<TreeNode<T>> trace = new LinkedList<>();// 用于非递归实现删除时存储访问路径

    BinaryTree(TreeNode<T> root) {
        this.root = root;
    }

    public void clear() {
        root = null;
    }

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

    public boolean contains(T element) {
        return contains0(root, element);
    }

    public void insert(T element) {
        TreeNode<T> node = new TreeNode<T>(element);
        insert0(root, node);
    }

    /** * * @Title: insert0 * * @Description: 递归插入 * * @param root * @param node * * @return: void * */
    private void insert0(TreeNode<T> root, TreeNode<T> node) {
        if (root.element.compareTo(node.element) < 0) {
            if (root.right == null) {
                root.right = node;
                return;
            } else {
                insert0(root.right, node);
            }
        }
        if (root.element.compareTo(node.element) > 0) {
            if (root.left == null) {
                root.left = node;
                return;
            } else {
                insert0(root.left, node);
            }
        }
    }

    // 删除一个子树的某个节点，返回新的子树根节点，给适当的父亲（左或者右），递归删除
    /** * * @Title: remove * * @Description: 递归删除 * * @param node * @param element * @return * * @return: TreeNode<T> * */
    public TreeNode<T> remove(TreeNode<T> node, T element) {
        if (node == null) {
            return node;
        }

        int compare = node.element.compareTo(element);
        // 寻找将要删除的节点
        if (compare > 0) {
            // 在节点左边 则去左边子树删除，并返回新的子树
            node.left = remove(node.left, element);
        } else if (compare < 0) {

            node.right = remove(node.right, element);
            // 找到了将要删除的节点
        } else if (node.left != null && node.right != null) {
            // 如果该节点有两个儿子，找到该节点右子树中的最小节点值赋值给当前节点
            TreeNode<T> min = findMin(node.right);
            node.element = min.element;
            // 再去右子树中删除该最小节点，并返回新的右子树给之前的节点
            node.right = remove(node.right, min.element);
        } else {
            // 如果该节点有左儿子则返回左儿子，有右儿子则返回右儿子（即该节点的儿子充当了新的子树），如果都没有则该叶子节点已经被删除
            node = node.left == null ? node.right : node.left;
        }
        return node;
    }

    /** * * @Title: delete * * @Description: 非递归删除，利用了栈来存储路径信息 * * @param element * @return * * @return: boolean * */
    public boolean delete(T element) {
        trace = findTrace(root, element);
        if (trace == null) {
            return false;
        }
        // 找到将要被删除的节点
        TreeNode<T> node = trace.pop();
        // 被删除节点没有儿子或者只有一个儿子
        if (node.left == null || node.right == null) {
            return delete0(root, element);
        }

        // 被删除节点有两个儿子
        // 找到节点右儿子中的最小值
        TreeNode<T> rightMin = findMin(node.right);
        // 直接删除该最小值节点
        if (delete0(root, rightMin.element)) {
            // 将最小右儿子的值赋给将要被删除的节点
            node.element = rightMin.element;
            return true;
        }
        return false;
    }

    private boolean delete0(TreeNode<T> nodeParent, T element) {
        trace.clear();
        trace = findTrace(nodeParent, element);
        if (trace == null) {
            return false;
        }
        TreeNode<T> node = trace.pop();
        // 被删除节点是叶子节点
        if (node.left == null && node.right == null) {
            TreeNode<T> parent = trace.peek();
            if (parent.left != null && parent.left.equals(node)) {
                parent.left = null;
                return true;
            }
            parent.right = null;
            return true;
        }
        // 被删除节点仅有一个右儿子
        if (node.left == null) {
            TreeNode<T> parent = trace.peek();
            if (parent.left != null && parent.left.equals(node)) {
                parent.left = node.right;
                node.right = null;
                return true;
            }
            parent.right = node.right;
            node.right = null;
            return true;
        }
        // 被删除节点仅有一个左儿子
        if (node.right == null) {
            TreeNode<T> parent = trace.peek();
            if (parent.left != null && parent.left.equals(node)) {
                parent.left = node.left;
                node.left = null;
                return true;
            }
            parent.right = node.left;
            node.left = null;
            return true;
        }

        return false;
    }

    public TreeNode<T> find(TreeNode<T> node, T element) {
        LinkedList<TreeNode<T>> trace = findTrace(node, element);
        return trace == null ? null : trace.pop();
    }

    private LinkedList<TreeNode<T>> findTrace(TreeNode<T> node, T element) {
        trace.push(node);
        if (node.element.equals(element)) {
            return trace;
        }
        if (node.right != null && node.element.compareTo(element) < 0) {
            return findTrace(node.right, element);
        }
        if (node.left != null && node.element.compareTo(element) > 0) {
            return findTrace(node.left, element);
        }
        return null;
    }

    public TreeNode<T> findMin(TreeNode<T> node) {
        if (node.left == null) {
            return node;
        }
        return findMin(node.left);
    }

    public void traverseInPostOrder(TreeNode<T> node) {
        if (node.left != null) {
            traverseInPostOrder(node.left);
        }
        if (node.right != null) {
            traverseInPostOrder(node.right);
        }
        System.out.print(node.element + " ");
    }

    public void traverseInPreOrder(TreeNode<T> node) {

        System.out.print(node.element + " ");

        if (node.left != null) {
            traverseInPreOrder(node.left);
        } else {
            System.out.print("# ");
        }

        if (node.right != null) {
            traverseInPreOrder(node.right);
        } else {
            System.out.print("# ");
        }
    }

    private boolean contains0(TreeNode<T> root, T element) {
        System.out.println(root.element.equals(element));
        if (root.element.equals(element)) {
            return true;
        }
        if (root.element.compareTo(element) < 0 && root.right != null) {
            return contains0(root.right, element);
        } else if (root.left != null) {
            return contains0(root.left, element);
        }
        return false;
    }

    private static class TreeNode<T> {
        T element;
        TreeNode<T> left;
        TreeNode<T> right;

        TreeNode(T element) {
            this.element = element;
        }

        public String toString() {
            return element.toString();
        }
    }