二叉树的下一个节点

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。如下图所示{d,b,h,e,i,a,f,c,g}

分析：如果一个节点有右子树，那么它的下一个节点就是它的右子树中的最左子节点。例如节点b的下一个节点是h

如果一个节点没有右子树，第一种情况：如果节点是它父节点的左子节点，那么它的下一个节点就是它的父节点，例如d的下一个节点是b

第二种情况：如果是它父节点的右子节点，我么可以沿着只想父节点的指针一直向上遍历，找到一个是它父节点的左子节点，如果这样节点存在，那么它的下一个节点节点就是它的父节点，例如i的父节点是a,b是a的左子节点，所以下各个节点是b的父节点a

 public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if(pNode==null){
            return null;
        }
        TreeLinkNode pNext=null;
        if(pNode.right!=null){
            TreeLinkNode right=pNode.right;
            while(right.left!=null){
                right=right.left;
            }
            pNext=right;
            
        }else if(pNode.next!=null){
            TreeLinkNode current=pNode;
            TreeLinkNode parent=pNode.next;
            while(parent!=null&&current==parent.right){
                current=parent;
                parent=parent.next;
            }
            pNext=parent;
            
        }
        return pNext;
    }