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

读完题目画出如下图所示示意图。分情况讨论题目中树中的结点会是哪些点。不同的点按照中序遍历的下一个结点也不一样。

 

根据图中所示，大致将结点分为以下几种情况：

1、当前结点有右子节点，且其右子节点

      （1）有最左子节点，则下一个结点为最左子节点，如图中的结点1的下一个结点为结点6

      （2）无最左子节点，则下一个结点为当前结点的右结点，如图中的结点5的下一个结点为结点9

2、当前结点没有右子节点，且当前结点

      （1）为左子节点，则下一个结点为其父节点，如图结点8的下一个结点为结点4

      （2）为右子节点，则下一个结点为其祖宗里面作为左节点的父节点。如图  结点9的下一个结点为结点1

代码如下：

private static TreeLinkNode GetNext(TreeLinkNode pNode) { if (pNode==null) { return null; } if (pNode.right !=null) { //当前结点有右子节点 pNode = pNode.right; while (pNode.left!=null) { //其右子节点有最左子节点 pNode = pNode.left; //则下一个结点为最左子节点 } return pNode; } while (pNode.next!=null) { if (pNode.next.left==pNode) { //当前结点为左子节点 return pNode.next; //下一个结点为其父节点 } pNode=pNode.next;//右子节点，则下一个结点为其祖宗里面作为左节点的父节点 } return null; }

总结

这一题的核心主要是要考虑所有结点的可能出现位置，然后理解中序遍历的内涵，准确对下一个结点进行判断。