算法-8.二叉树的下一个结点

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

    public static TreeLinkNode getInOrderNext(TreeLinkNode node) {
        // 如果当前需要找的结点的右子树不为null
        // 则判断其右子树是否有左边子树，如果有找到最左结点
        if (node.right != null) {
            TreeLinkNode node1 = node.right;
            while (node.left != null) {
                node1 = node1.left;
            }
            return node1;
        } else {
            // 如果当前需要找的结点的右子树为null
            // 则找其父结点，判断其父结点的左子树是否是当前结点
            // 如果是，则返回
            while (node.next != null) {
                TreeLinkNode parent = node.next;
                if (parent.left == node) {
                    return parent;
                }
                node = node.next;
            }
        }
        return null;
    }