二叉树的下一个节点

题目：

给定一棵二叉树和其中一个节点，如何找出中序遍历序列的下一个节点？树中的节点除了有两个分别指向左、右子节点的指针，还有一个个指向父节点的指针。

代码：

public class BinaryTreePoint {

    char value;
    BinaryTreePoint left;
    BinaryTreePoint right;
    BinaryTreePoint next;

    public BinaryTreePoint(char value) {
        this.value = value;
    }

    public BinaryTreePoint() {

    }
}

public class NextPointTree {

    public static BinaryTreePoint getNext(BinaryTreePoint pNode) {

        /**
         * 这里需要注意的是pNode.next是pNode结点的父结点
         * 1、如果有右子树，那么下一个结点就是右子树最左边的节点。
         * 2、如果没有右子树，分两种情况：
         *     第一种情况是如果该结点为父结点的左孩子，则该结点的父节点pNode.next则为该结点的下一个结点。
         *     第二种情况则是如果该结点为父节点的右孩子，则向上找父节点，直到父节点为该父节点的左孩子，则该父节点的父节点为下一个结点。
         */
        if (pNode == null) {
            return null;
        }

        if (pNode.right != null) { //1、如果有右子树，那么下一个结点就是右子树最左边的节点。
            pNode = pNode.right;
            while (pNode.left != null) pNode = pNode.left;
            return pNode;
        }

        while (pNode.next != null) { //这个则是在没有右子树的情况下，求下一个结点。
            if(pNode.next.left != null) return pNode.next;
            pNode = pNode.next;
        }

        return pNode;
    }
}