2023年6月22日发(作者：)

⼆叉树遍历算法之⼆：中序遍历中序遍历的递归实现中序遍历遍历指的是先访问⼆叉树中节点的左孩⼦，再访问当前节点，最后再访问其右孩⼦。具体访问步骤如下：1. ⾸先访问根节点，判断根节点是否有左孩⼦，如果有，进⾏第⼆步；如果没有，跳到第三步；2. 访问左孩⼦，继续判断当前节点是否有左孩⼦，如果有则继续访问其左孩⼦，直到某节点的左孩⼦为空3. 判断是否有右孩⼦，如果有，则继续判断当前节点是否有左孩⼦，⼀直到某节点没有左孩⼦为⽌4. 把第⼆步访问的节点做为当前节点（该节点⽆左孩⼦，如图中的15节点），按照规则，下⼀步应该访问其右孩⼦5. 返回到第四部节点的双亲节点（15的双亲节点是5），并设为当前访问的节点，下⼀步访问的是其右孩⼦（这⾥5没有右孩⼦）6. 继续访问第五步访问节点的双亲节点（5的双亲节点是6），下⼀步仍然访问其右孩⼦。7. 左⼦树访问完毕，继续第三步中右⼦树的访问，步骤与上⾯⼀直，最终每个节点都将访问⼀遍仍然以上⼀篇博客中前序遍历的例⼦作为说明：按照中序遍历的访问规则，最终的输出序列应该是15，24，5，6，7，8，30，9，10，11，2815，24，5，6，7，8，30，9，10，11，28。可以发现这是⼀个递归过程，其递归代码也很简单，代码如下：package ;public class TravelTree { static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val) { = val; } } public void inOrderTraverse(TreeNode node) { if (node == null) return; inOrderTraverse(); ( + " "); inOrderTraverse(); } public static void main(String[] args) { TreeNode root = new TreeNode(8); TreeNode node1 = new TreeNode(6); TreeNode node2 = new TreeNode(10); TreeNode node3 = new TreeNode(5); TreeNode node4 = new TreeNode(7); TreeNode node5 = new TreeNode(9); TreeNode node6 = new TreeNode(11); TreeNode node7 = new TreeNode(15); TreeNode node8 = new TreeNode(24); TreeNode node9 = new TreeNode(30); TreeNode node10 = new TreeNode(28); = node1; = node2; = node3; = node7; = node8; = node4; = node5; = node6; = node9; = node10; new TravelTree().inOrderTraverse(root); }}中序遍历的⾮递归实现下⾯我们讨论⼀下⾮递归实现，与上⼀篇前序遍历的⾮递归实现由⼀些类是，主要的访问次序的改变，所以只需要在前⾯代码的基础上做⼀些适当修改就可以了，下⾯是对中序遍历代码的实现（经测试可⽤）：public void inOrderTraverse2(TreeNode node){ Stack s = new Stack(); while(node != null || !y()){ //遍历左⼦树 while(node != null){ (node); node = ; } //遍历右⼦树 if(!y()){ node = (); ( + " "); node = ; } } }