题目： 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
思路： 可分为两种情况： （1）有右子结点的： 下个结点是以该右孩子为根节点的子树的最左边的结点； （2）没有右子结点的： （i）是父结点的左孩子，那么父结点就是下一结点； （ii）是父结点的右孩子，找它父结点的父结点的父结点…直到当前结点是其父结点的左孩子，如果没有，则它是尾结点，返回空。
程序：
class TreeLinkNode { int val; TreeLinkNode left = null; TreeLinkNode right = null; TreeLinkNode next = null; TreeLinkNode(int val) { this.val = val; } } public class subject57 { public 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; } public static void main(String args[]) { // 1 // // \\ // 2 3 // // \\ // 4 5 // inorder->42513 TreeLinkNode root = new TreeLinkNode(1); root.left = new TreeLinkNode(2); root.left.next = root; root.right = new TreeLinkNode(3); root.right.next = root; root.left.left = new TreeLinkNode(4); root.left.left.next = root.left; root.left.right = new TreeLinkNode(5); root.left.right.next = root.left; System.out.println(GetNext(root.left.left).val); System.out.println(GetNext(root.left).val); System.out.println(GetNext(root.left.right).val); System.out.println(GetNext(root).val); System.out.println(GetNext(root.right)); } }