Binary Search Tree - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki

// Comparable是为了比较两个结点之间的值（遍历操作，插入删除操作），具体的比较方法需要在值的类型确定后才能确定
public class BinarySearchTree<T extends Comparable<T>> implements Tree<T> {

    private BinaryNode<T> root;

    public BinaryNode<T> getRoot() {
        return root;
    }

    public void setRoot(BinaryNode<T> root) {
        this.root = root;
    }

    // 初始化一个空的二叉搜索树
    public BinarySearchTree() {
        this.root = null;
    }

    // 初始化一个根结点
    public BinarySearchTree(BinaryNode<T> root) {
        this.root = root;
    }

    // 根据先序遍历和中序遍历，或中序遍历和后序遍历构造二叉树
    // list可以是先序遍历或后序遍历
    public BinarySearchTree(T[] list, T[] inOrderList, boolean isPreOrder) {
        if (list == null|| inOrderList == null) {
            throw new RuntimeException("lists cannot be null");
        }
        if (isPreOrder) {
            // 先序遍历和中序遍历构建二叉树
            this.root = createBinarySearchTreeByPreIn(list, inOrderList, 0, list.length - 1, 0, inOrderList.length - 1);
        }else {
            // 中序遍历和后序遍历构建二叉树
            this.root = createBinarySearchTreeByPostIn(list, inOrderList, 0, list.length - 1, 0, inOrderList.length - 1);
        }
    }

    /**
     * 根据先序遍历和中序遍历构造二叉树
     * @param preOrderList 先序遍历数组
     * @param inOrderList 中序遍历数组
     * @param preOrderStart 先序遍历数组的头结点位置
     * @param preOrderEnd 先序遍历数组的尾结点的位置
     * @param inOrderStart 中序遍历数组的头结点位置
     * @param inOrderEnd 中序遍历数组的尾结点的位置
     * return root 最终返回的根结点
     */
    public BinaryNode<T> createBinarySearchTreeByPreIn(
            T[] preOrderList, T[] inOrderList, int preOrderStart ,int preOrderEnd ,int inOrderStart ,int inOrderEnd) {

        // 先序遍历第一个点是根结点root
        BinaryNode<T> p = new BinaryNode<>(preOrderList[preOrderStart]);
        // 如果没有其它元素，就说明结点已构建完成
        if (preOrderStart == preOrderEnd && inOrderStart == inOrderEnd) {
            return p;
        }

        // 找出中序遍历的根结点下标rootIndex
        int rootIndex = 0;
        for (rootIndex = inOrderStart; rootIndex < inOrderEnd; rootIndex++) {
            // preOrderList[preOrderStart]是先序遍历第一个点，即是根结点root
            // 如果中序遍历中的元素值与先序遍历的根结点相等，则该下标index即为inOrderList中的根结点下标
            if (preOrderList[preOrderStart].compareTo(inOrderList[rootIndex]) == 0){
                break;
            }
        }

        // 获取左子树的长度
        int leftLength = rootIndex - inOrderStart;
        // 获取右子树的长度
        int rightLength = inOrderEnd - rootIndex;
        // 递归构建左子树
        if (leftLength > 0) {
            // 左子树的先根序列：preOrderList[1], ... , preOrderList[i]
            // 左子树的中根序列：inOrderList[0], ... , inOrderList[i-1]
            p.setLeft(createBinarySearchTreeByPreIn(
                    preOrderList, inOrderList, preOrderStart + 1,preOrderStart + leftLength, inOrderStart, rootIndex - 1));
        }
        // 递归构建右子树
        if (rightLength > 0) {
            // 右子树的先根序列：preOrderList[i+1], ... , preOrderList[n-1]
            // 右子树的中根序列：inOrderList[i+1], ... , inOrderList[n-1]
            p.setRight(createBinarySearchTreeByPreIn(
                    preOrderList, inOrderList,preOrderStart + leftLength + 1, preOrderEnd,rootIndex + 1, inOrderEnd));
        }
        return p;
    }

    /**
     * 根据中序遍历和后序遍历构造二叉树
     * @param postOrderList 后序遍历数组
     * @param inOrderList 中序遍历数组
     * @param postOrderStart 后序遍历数组的头结点位置
     * @param postOrderEnd 后序遍历数组的尾结点的位置
     * @param inOrderStart 中序遍历数组的头结点位置
     * @param inOrderEnd 中序遍历数组的尾结点的位置
     * @return 最终返回的根结点
     */
    public BinaryNode<T> createBinarySearchTreeByPostIn(
            T[] postOrderList, T[] inOrderList, int postOrderStart, int postOrderEnd, int inOrderStart, int inOrderEnd) {

        // 后序遍历最后一个点是根结点root
        BinaryNode<T> p = new BinaryNode<>(postOrderList[postOrderEnd]);
        // 如果没有其它元素，就说明结点已构建完成
        if (postOrderStart == postOrderEnd && inOrderStart == inOrderEnd) {
            return p;
        }

        // 找出中序遍历的根结点下标rootIndex
        int rootIndex = 0;
        for (rootIndex = inOrderStart; rootIndex < inOrderEnd; rootIndex++) {
            // postOrderList[postOrderEnd]是后序遍历最后一个点，即是根结点root
            // 如果中序遍历中的元素值与后序遍历的根结点相等，则该下标index即为inOrderList中的根结点下标
            if (postOrderList[postOrderEnd].compareTo(inOrderList[rootIndex]) == 0){
                break;
            }
        }

        // 获取左子树的长度
        int leftLength = rootIndex - inOrderStart;
        // 获取右子树的长度
        int rightLength = inOrderEnd - rootIndex;
        // 递归构建左子树
        if (leftLength > 0) {
            // 左子树的后根序列：postOrderList[0], ... , postOrderList[i-1]
            // 左子树的中根序列：inOrderList[0], ... , inOrderList[i-1]
            p.setLeft(createBinarySearchTreeByPostIn(
                    postOrderList, inOrderList, postOrderStart, postOrderStart + leftLength - 1, inOrderStart,rootIndex - 1));
        }
        // 递归构建右子树
        if (rightLength > 0) {
            // 右子树的后根序列：preOrderList[i], ... , preOrderList[n-2]
            // 右子树的中根序列：inOrderList[i+1], ... , inOrderList[n-1]
            p.setRight(createBinarySearchTreeByPostIn(
                    postOrderList, inOrderList, postOrderStart + leftLength, postOrderEnd - 1,rootIndex + 1, inOrderEnd));
        }
        return p;
    }

    // 判断二叉树搜索是否为空
    // 只需要判断根结点是否存在即可
    @Override
    public boolean isEmpty() {
        return root == null;
    }

    // 思路：获取二叉树节点数，需要获取以某个节点为根的子树的节点数实现。
    // 如果节点为空，则个数肯定为0；如果不为空，则算上这个节点之后，继续递归计算所有子树的节点数，全部相加即可
    @Override
    public int size() {
        return size(root);
    }

    private int size(BinaryNode<T> subtree) {
        if (subtree == null) {
            // 如果结点为空，则返回节点数为0
            return 0;
        } else {
            // 计算本节点 所以要 +1
            // 递归获取左子树节点数和右子树节点数，最终相加
            // 对比汉诺塔：H(n) = H(n-1) + 1 + H(n-1)
            return size(subtree.getLeft()) + size(subtree.getRight()) + 1;
        }
    }

    // 思路：首先需要一种获取以某个节点为子树的高度方法，使用递归实现。
    // 如果一个节点为空，那么这个节点肯定是一颗空树，高度为0；
    // 如果不为空，则遍历地比较它的左右子树高度，高的一个为这颗子树的最大高度，然后加上自身的高度即可
    private int height(BinaryNode<T> subtree) {
        if (subtree == null) {
            // 递归结束，空子树高度为0
            return 0;
        } else {
            // 递归获取左子树高度
            int l = height(subtree.getLeft());
            // 递归获取右子树高度
            int r = height(subtree.getRight());
            // 高度应该算更高的一边，+1是因为药算上自身这一层
            return l > r ? (l + 1) : (r + 1);
        }
    }

    @Override
    public int height() {
        return height(root);
    }

    // 若二叉树为空，则退出，否则进行下面操作
    // 访问根结点
    // 先根遍历左子树
    // 先根遍历右子树
    // 退出
    public String preOrder(BinaryNode<T> subtree) {
        StringBuilder sb = new StringBuilder();
        // 递归结束条件
        if (subtree != null) {
            // 访问根结点
            sb.append(subtree.getData()).append(",");
            // 遍历左子树
            sb.append(preOrder(subtree.getLeft()));
            // 遍历右子树
            sb.append(preOrder(subtree.getRight()));
        }
        return sb.toString();
    }

    @Override
    public String preOrder() {
        String sb = preOrder(root);
        if (sb.length() > 0) {
            // 去掉尾部","号
            sb = sb.substring(0, sb.length() - 1);
        }
        return sb;
    }

    // 若二叉树为空，则退出，否则进行下面操作
    // 中根遍历左子树
    // 访问根节点
    // 中根遍历右子树
    // 退出
    public String inOrder(BinaryNode<T> subtree) {
        StringBuilder sb = new StringBuilder();
        // 递归结束条件
        if (subtree != null) {
            // 遍历左子树
            sb.append(inOrder(subtree.getLeft()));
            // 访问根结点
            sb.append(subtree.getData()).append(",");
            // 遍历右子树
            sb.append(inOrder(subtree.getRight()));
        }
        return sb.toString();
    }

    @Override
    public String inOrder() {
        String sb = inOrder(root);
        if (sb.length() > 0) {
            // 去掉尾部","号
            sb = sb.substring(0, sb.length() - 1);
        }
        return sb;
    }

    // 若二叉树为空，则退出，否则进行下面操作
    // 后根遍历左子树
    // 后根遍历右子树
    // 访问根节点
    // 退出
    public String postOrder(BinaryNode<T> subtree) {
        StringBuilder sb = new StringBuilder();
        if (subtree != null) {
            // 遍历左子树
            sb.append(postOrder(subtree.getLeft()));
            // 遍历右子树
            sb.append(postOrder(subtree.getRight()));
            // 访问根结点
            sb.append(subtree.getData()).append(",");
        }
        return sb.toString();
    }

    @Override
    public String postOrder() {
        String sb = postOrder(root);
        if (sb.length() > 0) {
            // 去掉尾部","号
            sb = sb.substring(0, sb.length() - 1);
        }
        return sb;
    }

    // 方法：
    // 1. 入队第一个根结点
    // 2. 出队一个结点
    // 3. 马上入队这个结点的子结点，先左子结点再右子结点
    // 4. 重复2和3
    @Override
    public String levelOrder() {
        // 存放需要遍历的结点，左结点一定优先右节点遍历
        Queue<BinaryNode<T>> queue = new PriorityQueue<>();
        StringBuilder sb = new StringBuilder();
        BinaryNode<T> node = this.root;
        while (node != null) {
            // 记录经过的结点
            sb.append(node.getData());
            // 先按层次遍历结点，左结点一定在右结点之前访问
            if (node.getLeft() != null) {
                // 子结点入队
                queue.add(node.getLeft());
            }
            if (node.getRight() != null) {
                // 子结点入队
                queue.add(node.getRight());
            }
            // 访问下一个结点
            node = queue.poll();
        }

        return sb.toString();
    }

    // 非递归的先序遍历
    // 任何递归的本质，实际上就是入栈出栈的过程
    public String preOrder2() {
        StringBuilder sb = new StringBuilder();
        // 构建用于存放结点的栈
        Stack<BinaryNode<T>> stack = new Stack<>();
        BinaryNode<T> p = this.root;

        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                // 访问根结点
                sb.append(p.getData()).append(",");
                // 将已访问过的结点入栈
                stack.push(p);
                // 继续访问其左子树
                p = p.getLeft();

            }
            //若p=null且栈不为空，则说明已沿左子树访问完一条路径, 从栈中弹出栈顶结点,并访问其右子树
            else {
                p = stack.pop();
                p = p.getRight();
            }
        }
        // 去掉最后一个逗号
        if (sb.length() > 0) {
            return sb.substring(0, sb.length() - 1);
        } else {
            return sb.toString();
        }
    }

    // 非递归的中序遍历
    public String inOrder2() {
        StringBuilder sb = new StringBuilder();
        // 构建用于存放结点的栈
        Stack<BinaryNode<T>> stack = new Stack<>();
        BinaryNode<T> p = this.root;

        while (p != null || !stack.isEmpty()) {
            // 把左子树都入栈，直到左子树为null
            while (p != null) {
                stack.push(p);
                p=p.getLeft();
            }
            // 如果栈不为空,因为前面左孩子已全部入栈
            if(!stack.isEmpty()){
                p = stack.pop();
                // 访问根结点
                sb.append(p.getData()).append(",");
                // 访问p结点的右子树
                p = p.getRight();
            }
        }
        if (sb.length() > 0) {
            return sb.substring(0, sb.length() - 1);
        } else {
            return sb.toString();
        }
    }

    // 非递归后序遍历
    public String postOrder2() {
        StringBuilder sb = new StringBuilder();
        // 构建用于存放结点的栈
        Stack<BinaryNode<T>> stack = new Stack<>();

        BinaryNode<T> p = this.root;
        BinaryNode<T> prev = this.root;

        while (p != null || !stack.isEmpty()) {
            // 把左子树都入栈，直到左子树为null
            while (p != null) {
                stack.push(p);
                p = p.getLeft();
            }

            // 开始访问当前结点的父结点的右子树
            if (!stack.isEmpty()) {
                // 获取子树
                // peek()函数返回栈顶的元素，但不弹出该栈顶元素
                BinaryNode<T> temp = stack.peek().getRight();
                // 先判断是否有右子树或者右子树是否已被访问过
                // 没有右子树，则可以记录当前根结点；
                // 右子树已被访问过，则可以记录当前根结点；
                if (temp == null || temp == prev) {
                    // 没有右子树或右子树已被访问过，则弹出父结点并访问
                    p = stack.pop();
                    // 访问根结点
                    sb.append(p.getData()).append(",");
                    // 记录已访问过的结点
                    prev = p;
                    // 置空当前结点
                    p = null;
                } else {
                    // 有子树，则开始遍历右子树
                    p = temp;
                }
            }
        }
        // 去掉最后一个逗号
        if (sb.length() > 0) {
            return sb.substring(0, sb.length() - 1);
        } else {
            return sb.toString();
        }
    }

    // 插入操作，递归实现
    private BinaryNode<T> insert(T data, BinaryNode<T> p) {
        if (p == null) {
            p = new BinaryNode<>(data, null, null);
        }
        int compareResult = data.compareTo(p.getData());
        // 相同元素不必重复插入
        // 如果小于0，从左子树遍历
        if (compareResult < 0) {
            p.setLeft(insert(data, p.getLeft()));
        }
        // 如果大于0，从右子树遍历
        else if (compareResult > 0) {
            p.setRight(insert(data, p.getRight()));
        }
        return p;
    }

    @Override
    public void insert(T data) {
        if (data == null) {
            throw new RuntimeException("data cannot be null!");
        }
        // 插入操作
        root = insert(data, root);
    }

    // 分3种情况
    // 1. 删除叶子结点(也就是没有孩子结点)
    // 2. 删除拥有一个孩子结点的结点(可能是左孩子也可能是右孩子)
    // 3. 删除拥有两个孩子结点的结点
    private BinaryNode<T> remove(T data, BinaryNode<T> p){
        //没有找到要删除的元素，递归结束
        if (p == null) {
            return null;
        }
        int compareResult = data.compareTo(p.getData());
        // 如果小于0，从左子树遍历
        if (compareResult < 0) {
            // 删除结点，更新子树
            p.setLeft(remove(data,p.getLeft()));
        }
        // 如果大于0，从右子树遍历
        else if (compareResult > 0) {
            // 删除结点，更新子树
            p.setRight(remove(data,p.getRight()));
        }
        // 3. 删除拥有两个孩子结点的结点
        else if (p.getLeft() != null && p.getRight() != null) {
            // 中继替换，找到右子树中最小的元素并替换需要删除的元素值
            p.setData(findMin(p.getRight()).getData());
            // 移除用于替换的结点
            p.setRight(remove(p.getData(), p.getRight()));
        }
        // 1. 删除叶子结点(也就是没有孩子结点)
        // 2. 删除拥有一个孩子结点的结点(可能是左孩子也可能是右孩子)
        else {
            // 直接删除结点，再把子树拼接上来
            p = (p.getLeft() != null) ? p.getLeft() : p.getRight();
        }
        // 返回该结点
        return p;
    }

    @Override
    public void remove(T data) {
        if(data == null) {
            throw new RuntimeException("data cannot be null!");
        }
        // 删除结点
        root = remove(data, root);
    }

    // 非递归删除
    // 分3种情况
    // 1. 删除叶子结点(也就是没有孩子结点)
    // 2. 删除拥有一个孩子结点的结点(可能是左孩子也可能是右孩子)
    // 3. 删除拥有两个孩子结点的结点
    public boolean remove2(T data) {
        if (data == null) {
            throw new RuntimeException("data cannot be null!");
        }
        //从根结点开始查找
        BinaryNode<T> current = this.root;
        //记录父结点
        BinaryNode<T> parent = this.root;
        //判断左右孩子的flag
        boolean isLeft = true;

        //找到要删除的结点
        while (data.compareTo(current.getData()) != 0) {
            //更新父结点记录
            parent = current;
            int result = data.compareTo(current.getData());
            // 如果小于0，从左子树遍历
            if (result < 0) {
                isLeft = true;
                current = current.getLeft();
            }
            // 如果大于0，从右子树遍历
            else if (result > 0) {
                isLeft = false;
                current = current.getRight();
            }
            // 如果没有找到,返回null
            if (current == null){
                return false;
            }
        }

        // 到这里说明已找到要删除的结点
        // 1. 删除叶子结点(也就是没有孩子结点)
        if (current.getLeft() == null && current.getRight() == null) {
            if (current == this.root) {
                this.root = null;
            } else if (isLeft) {
                parent.setLeft(null);
            } else {
                parent.setRight(null);
            }
        }
        // 2. 删除拥有一个右孩子结点的结点
        else if (current.getLeft() == null) {
            if (current == this.root) {
                this.root = current.getRight();
            }
            // current为parent的左子树
            else if (isLeft) {
                parent.setLeft(current.getRight());
            }
            // current为parent的右子树
            else {
                parent.setRight(current.getRight());
            }
        }
        // 2. 删除拥有一个左孩子结点的结点
        else if (current.getRight() == null) {
            if (current == this.root){
                this.root = current.getLeft();
            }
            // current为parent的左子树
            else if (isLeft) {
                parent.setLeft(current.getLeft());
            }
            // current为parent的右子树
            else {
                parent.setRight(current.getLeft());
            }
        }
        // 3. 删除拥有两个孩子结点的结点
        else {
            // 找到当前要删除结点current的右子树中的最小值元素
            BinaryNode<T> successor = findSuccessor(current);
            if(current == root) {
                this.root = successor;
            }
            // current为parent的左子树
            else if(isLeft) {
                parent.setLeft(successor);
            }
            // current为parent的右子树
            else {
                parent.setRight(successor);
            }
            // 把当前要删除的结点的左右子树赋值给successor
            successor.setLeft(current.getLeft());
            successor.setRight(current.getRight());
        }
        return true;
    }

    // 判断树T中是否包含data
    private boolean contains(T data, BinaryNode<T> p) {
        if (p == null || data == null) {
            return false;
        }
        // 计算比较结果
        int compareResult = data.compareTo(p.getData());
        // 如果小于0，从左子树遍历
        if (compareResult < 0) {
            return contains(data, p.getLeft());
        }
        // 如果大于0，从右子树遍历
        else if (compareResult > 0) {
            return contains(data, p.getRight());
        }
        // 如果等于0，即找到值
        else {
            return true;
        }
    }

    @Override
    public boolean contains(T data) {
        return contains(data, root);
    }

    // 查找最小值结点
    private BinaryNode<T> findMin(BinaryNode<T> p) {
        // 结束条件
        if (p == null) {
            return null;
        }
        // 遍历左子树即可
        // 如果没有左结点,那么t就是最小的
        else if (p.getLeft() == null) {
            return p;
        }
        return findMin(p.getLeft());
    }

    @Override
    public T findMin() {
        if (isEmpty()) {
            throw new RuntimeException("BinarySearchTree is empty!");
        }
        return findMin(root).getData();
    }

    // 查找最大值结点
    private BinaryNode<T> findMax(BinaryNode<T> p) {
        // 结束条件
        if (p == null) {
            return null;
        }
        else if (p.getRight() == null) {
            return p;
        }
        return findMax(p.getRight());
    }

    @Override
    public T findMax() {
        if (isEmpty()) {
            throw new RuntimeException("BinarySearchTree is empty!");
        }
        return findMax(root).getData();
    }

    // 根据data查找结点
    private BinaryNode<T> findNode(T data, BinaryNode<T> p) {
        if (p == null || data == null) {
            return null;
        }
        // 计算比较结果
        int compareResult = data.compareTo(p.getData());
        // 如果小于0，从左子树遍历
        if (compareResult < 0) {
            return findNode(data, p.getLeft());
        }
        // 如果大于0，从右子树遍历
        else if (compareResult > 0) {
            return findNode(data, p.getRight());
        }
        // 如果等于0，即找到值
        else {
            return p;
        }
    }

    @Override
    public BinaryNode<T> findNode(T data) {
        return findNode(data, root);
    }

    // 查找后继结点
    // 1. 存在右子树，找右子树最小值结点
    // 2. 不存在右子树，只能向上找（沿着到根结点的路径，可以理解为搜索该结点的路径）
    //     a. 若该结点是其父结点的左结点，则其后继结点是其父结点
    //     b. 若该结点是其父结点的右结点，则需要继续往上找，直到路径中出现第一个结点x是x的父结点的左结点，则该结点的后继结点是x的父结点
    @Override
    public BinaryNode<T> findSuccessor(BinaryNode<T> p) {
        if (p == null || p.getData() == null) {
            return null;
        }

        // 1. 存在右子树，找右子树最小值结点
        if (p.getRight() != null) {
            return findMin(p);
        }

        // 创建两个Stack，记录从根结点到当前结点中的所有结点和方向
        // true代表向左遍历，false代表向右遍历
        Stack<Boolean> directions = new Stack<>();
        Stack<BinaryNode<T>> nodes = new Stack<>();

        BinaryNode<T> current = root;
        nodes.push(current);
        while (current != null && (current.getLeft() != null || current.getRight() != null)) {

            // 计算比较结果
            int compareResult = p.getData().compareTo(current.getData());
            // 如果小于0，从左子树遍历
            if (compareResult < 0) {
                current = current.getLeft();
                directions.push(true);
                nodes.push(current);
            }
            // 如果大于0，从右子树遍历
            else if (compareResult > 0) {
                current = current.getRight();
                directions.push(false);
                nodes.push(current);
            }
            // 如果等于0，即找到值
            else {
                break;
            }
        }

        // 到这里路径已经记录好
        if (current == null) {
            return null;
        }
        while (!directions.isEmpty()) {
            // 若该结点是其父结点的右结点，则需要继续往上找
            if (!directions.peek()) {
                directions.pop();
                nodes.pop();
            }
            // 直到路径中出现第一个结点x是x的父结点的左结点，则该结点的后继结点是x的父结点
            else {
                // pop出当前结点，再pop出父结点
                nodes.pop();
                return nodes.pop();
            }
        }
        return null;
    }

    // 查找前驱结点
    // 1. 存在左子树，找左子树最大值结点
    // 2. 不存在左子树，只能向上找（沿着到根结点的路径，可以理解为搜索该结点的路径）
    //     a. 若该结点是其父结点的右结点，则其前驱结点是其父结点
    //     b. 若该结点是其父结点的左结点，则需要继续往上找，直到路径中出现第一个结点x是x的父结点的右结点，则该结点的后继结点是x的父结点
    @Override
    public BinaryNode<T> findPredecessor(BinaryNode<T> p) {
        if (p == null || p.getData() == null) {
            return null;
        }

        // 1. 存在左子树，找左子树最大值结点
        if (p.getLeft() != null) {
            return findMax(p);
        }

        // 创建两个Stack，记录从根结点到当前结点中的所有结点和方向
        // true代表向左遍历，false代表向右遍历
        Stack<Boolean> directions = new Stack<>();
        Stack<BinaryNode<T>> nodes = new Stack<>();

        BinaryNode<T> current = root;
        nodes.push(current);
        while (current != null && (current.getLeft() != null || current.getRight() != null)) {

            // 计算比较结果
            int compareResult = p.getData().compareTo(current.getData());
            // 如果小于0，从左子树遍历
            if (compareResult < 0) {
                current = current.getLeft();
                directions.push(true);
                nodes.push(current);
            }
            // 如果大于0，从右子树遍历
            else if (compareResult > 0) {
                current = current.getRight();
                directions.push(false);
                nodes.push(current);
            }
            // 如果等于0，即找到值
            else {
                break;
            }
        }

        // 到这里路径已经记录好
        if (current == null) {
            return null;
        }
        while (!directions.isEmpty()) {
            // 若该结点是其父结点的左结点，则需要继续往上找
            if (directions.peek()) {
                directions.pop();
                nodes.pop();
            }
            // 直到路径中出现第一个结点x是x的父结点的右结点，则该结点的后继结点是x的父结点
            else {
                // pop出当前结点，再pop出父结点
                nodes.pop();
                return nodes.pop();
            }
        }
        return null;
    }

    @Override
    public void clear() {
        root = null;
    }

    // 中序遍历的形式打印树
    private void printTree(BinaryNode<T> note) {
        if (note != null) {
            printTree(note.getLeft());
            System.out.println(note.getData());
            printTree(note.getRight());
        }
    }

    // 将树转换成字符串并打印在控制台上，用L表示左子树，R表示右子树
    @Override
    public void print() {
        LinkedList<BinaryNode<T>> tree = getCompleteBinaryTree();
        //获取树的深度
        int depth = height();
        Iterator<BinaryNode<T>> iterator = tree.iterator();

        int maxPosition = 1;

        // 层数，从1开始
        for (int floor = 1; floor <= depth; floor++) {
            // 左移相当于1*2^(floor-1)
            maxPosition = 1 << (floor - 1);
            //输出元素前需要打印的空白符
            //左移相当于1*2^( depth - floor ) - 1
            printBlank((1 << (depth - floor)) - 1);

            //开始打印元素
            for (int position = 0; position < maxPosition; position++) {
                if (iterator.hasNext()) {
                    BinaryNode<T> node = iterator.next();
                    if (node != null) {
                        System.out.print(node.getData());
                    } else {
                        System.out.print(" ");
                    }
                    //再次打印间隔空白符
                    printBlank((1 << (depth - floor + 1)) - 1);
                }
            }
            //换行
            System.out.println();
        }
    }

    // 打印空白
    private void printBlank(int length) {
        while (length -- > 0) {
            System.out.print(" ");
        }
    }

    // 将二叉树用空节点补充成完全二叉树，并以水平遍历形式返回
    private LinkedList<BinaryNode<T>> getCompleteBinaryTree() {
        Queue<BinaryNode<T>> queue = new LinkedList<>();
        LinkedList<BinaryNode<T>> tree = new LinkedList<>(); // 把树补充成完全二叉树，放在这个链表中
        queue.add(root);
        int nodeCount = 1; // 队列中非空节点数
        while (queue.size() > 0 && nodeCount > 0) {
            BinaryNode<T> node = queue.remove();
            if (node != null) {
                nodeCount--;
                tree.add(node);
                BinaryNode<T> left = node.getLeft();
                BinaryNode<T> right = node.getRight();
                if (left == null) {
                    queue.add(null);
                } else {
                    queue.add(left);
                    nodeCount++;
                }
                if (right == null) {
                    queue.add(null);
                } else {
                    queue.add(right);
                    nodeCount++;
                }
            } else {
                tree.add(null);
                queue.add(null);
                queue.add(null);
            }
        }
        return tree;
    }
}