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

package Day43;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/**
 * @Author Zhongger
 * @Description 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
 * @Date 2020.3.15
 */
public class GetNextSolution {
    public  List<TreeLinkNode> treeNodeArrayList = new ArrayList<>();
    public static void main(String[] args) {
        GetNextSolution getNextSolution = new GetNextSolution();
        TreeLinkNode root = new TreeLinkNode(8);
        TreeLinkNode node6 = new TreeLinkNode(6);
        TreeLinkNode node10 = new TreeLinkNode(10);
        TreeLinkNode node5 = new TreeLinkNode(5);
        TreeLinkNode node7 = new TreeLinkNode(7);
        TreeLinkNode node9 = new TreeLinkNode(9);
        TreeLinkNode node11 = new TreeLinkNode(11);
        root.left=node6;
        root.right=node10;
        node6.left=node5;
        node6.right=node7;
        node10.left=node9;
        node10.right=node11;
        System.out.println(getNextSolution.infixOrder(root));
        System.out.println(getNextSolution.GetNext(root));
    }
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if (pNode==null){
            return null;
        }
        if (treeNodeArrayList.get(treeNodeArrayList.size()-1).val==pNode.val){//中序遍历序列中，pNode恰好是最后一个节点，那它的下一个节点就为空
            return null;
        }
        Iterator<TreeLinkNode> iterator = treeNodeArrayList.iterator();//迭代器
        while (iterator.hasNext()){
            TreeLinkNode next = iterator.next();
            if (next.val==pNode.val){//当前节点值与传入的节点值相同
                return iterator.next();
            }
        }
        return null;
    }
    public List<TreeLinkNode> infixOrder(TreeLinkNode root){//中序遍历
        if (root.left!=null){
            infixOrder(root.left);
        }
        System.out.println(root);
        treeNodeArrayList.add(root);
        if (root.right!=null){
            infixOrder(root.right);
        }
        return treeNodeArrayList;
    }
}
class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;
    TreeLinkNode(int val) {
        this.val = val;
    }
    @Override
    public String toString() {
        return "TreeLinkNode{" +
                "val=" + val +
                '}';
    }
}

  public TreeLinkNode GetNext(TreeLinkNode pNode){
        if (pNode==null){
            return null;
        }
        if (pNode.right != null) {//当前节点有右子节点，那么当前节点的下一个节点就是它右子节点的最左子节点
            TreeLinkNode node = pNode.right;
            while (node.left != null)
                node = node.left;
            return node;  //找到了最左节点后，就把结果节点指向它，然后返回
        } else { //当前节点没有右子节点
            while (pNode.next != null) { //沿着父节点的指针遍历，直到找到一个节点成为它的父节点的左子节点
                TreeLinkNode parent = pNode.next;
                if (parent.left == pNode)
                    return parent;
                pNode = pNode.next;
            }
        }
        return null;
    }