Java中如何实现非递归方式遍历二叉树？

本文共计1729个文字，预计阅读时间需要7分钟。

二叉树的非递归遍历主要借助栈来实现。这里先介绍非递归遍历的原理，然后比较先序遍历、中序遍历和后序遍历的简单性。

非递归遍历利用栈来保存节点访问的顺序，先序遍历的特点是先访问根节点，再遍历左子树，最后遍历右子树。中序遍历是先遍历左子树，再访问根节点，最后遍历右子树。后序遍历是先遍历左子树，再遍历右子树，最后访问根节点。

从简单性来看，先序遍历相对简单，因为只需要按照根-左-右的顺序访问即可。中序遍历稍微复杂一些，需要先访问左子树，但不需要考虑节点访问顺序。后序遍历最复杂，因为它需要先访问左子树和右子树，最后才访问根节点。

总结来说，非递归遍历通过栈来保存节点访问顺序，先序遍历最简单，后序遍历最复杂。

二叉树的递归遍历比较简单，这里就不聊了。今天主要聊聊二叉树的非递归遍历，主要借助于“栈”后进先出的特性来保存节点的顺序，先序遍历和中序遍历相对来说比较简单，重点理解后序遍历。

1. 先看看节点类型：

//二叉树的节点类型 private class Node{ int data; //节点值 Node leftChild; //左孩子 Node rightChild; //右孩子 public Node(int data) { this.data=data; } }

2.先序遍历。