要找出中序遍历的下一个结点，要分几种情况探讨。
如果当前结点的右子结点不为空，那么下一个结点就是以该右子结点为根的子树的最左子结点；如果当前结点的右子结点为空，看它的父结点。此时分两种情况，如果父结点的右子结点就是当前结点，说明这个结点在中序遍历中已经被访问过了，需要继续往上看其父结点…直到父结点的左子结点是当前结点为止，该父结点就是下一个结点。如果在一直往上的过程中已经到达根结点，而根结点的父结点为null，这种情况说明当前结点已经是中序序列的最后一个结点了，不存在下一个结点，应该返回null. package Chap2; public class InOrderNextNode { private class TreeLinkNode { int val; TreeLinkNode left = null; TreeLinkNode right = null; // next指向父结点 TreeLinkNode next = null; TreeLinkNode(int val) { this.val = val; } } public TreeLinkNode GetNext(TreeLinkNode pNode) { // 如果当前结点右子树不空，那么中序下一个结点是右子树的最左子结点（如果有的话）；如果右子树没有左子结点就返回右子树根结点 if (pNode.right != null) { pNode = pNode.right; while (pNode.left != null) { pNode = pNode.left; } return pNode; } // 如果当前子结点pNode右子树为空 // 返回上层的父结点，如果父结点的右子结点就是当前结点，继续返回到上层的父结点...直到父结点的左子结点等于当前结点 while (pNode.next != null && pNode.next.right == pNode) { pNode = pNode.next; } // 如果父结点的左子结点等于当前结点，说明下一个要遍历的结点就是父结点了；或者父结点为空（说明当前结点是root），还是返回父结点（null） // pNode.next == null 或者 pNode.next.left == pNode return pNode.next; } }本文参考文献： [1]github.com/haiyusun/data-structures
快乐李同学(李俊德-大连理工大学) 认证博客专家 数据结构 Java Android B站/微博/微信公众号:快乐李同学。大连理工大学软件工程2020毕业学生。大连理工大学2018-2019学年科技创新奖学金。2个国家级项目，2个国家级奖项，5个省级奖项，8个校级奖项（总项目经费和竞赛奖金达2万2千元）。2018-2019年在中国核心期刊《现代计算机》发表2篇项目相关论文，分别署名第一、第二作者（知网可查）。2018-2019年申请2份项目软件著作权，并发布软件(编程乐园、编程学院)到Google,腾讯,百度,华为,小米等应用商店。大学英语六级568分。