二叉树的中序遍历也可以循环地完成(二叉树中序遍历是怎么遍历的)

导语：循环实现二叉树的中序遍历

01 二叉树的中序遍历回顾

中序遍历即父节点在中间遍历，遍历的顺序是左孩子，父节点，右孩子。对于整棵树来说，0是父节点，左边的树枝是左孩子节点，右边的树枝是右孩子节点。如下图所示。

遍历过程如下：

对于 0的整个左孩子树枝来说，又是一个父子结构， 3是左孩子节点，1是父节点，4是右孩子节点。他们的遍历顺序是3，1，4。

遍历父节点，0

对于0的整个右孩子树枝也类似。先遍历2的左孩子节点结构7，5，遍历2，最后遍历6。

故中序遍历的结果如下，3，1，4，0（的左孩子结束），7，5，2，6。

02 图解循环实现中序遍历

① 0入栈

② 1，3，入栈。

③ 3没有左孩子节点了，3弹出栈输出

④检查3没有右孩子节点，1出栈，输出

⑤1有右孩子节点，入栈1的右孩子节点4，以及4的所有持续左孩子节点。

⑥弹出栈顶元素输出 4，检查4无右孩子

⑦继续弹出栈顶元素0，输出

⑧将0的右孩子节点2，及2遍历所有的左孩子入栈

⑨因无左孩子可以再遍历入栈，弹出栈顶元素输出

弹出7输出，7无右孩子节点，继续弹栈

弹出栈顶元素5，5无右孩子节点，继续弹栈

弹出栈顶元素2，输出2，2有右孩子节点，将2对用的右孩子节点6，及，6的持续左孩子节点，入栈

⑩ 弹出栈顶元素6，输出，栈为空。3，1，4，0，7，5，2，6。结束循环

03 总结和代码

总结：总的来理解，分为两部分，1.右孩子节点的持续左孩子入栈，直到左孩子为空。

2.弹出栈元素输出，检查是否有右孩子节点，如果有进行1，如果没有继续弹出栈元素输出。

代码：

public static void inTraversalTree(BinaryTreeNode root) { if (root == null) { return; } Stack<BinaryTreeNode> stack = new Stack<>(); BinaryTreeNode enterStackNode = root; do { while (enterStackNode != null) { stack.push(enterStackNode); enterStackNode = enterStackNode.leftChild; } BinaryTreeNode printNode = stack.pop(); System.out.print(printNode.value + " "); enterStackNode = printNode.rightChild; }while (!stack.isEmpty() || enterStackNode != null);}

本文内容由小德整理编辑！