### 二叉树循环遍历

二叉树是一个非常重要的数据结构，它是一个树结构，特点是每个节点至多只有 2 个子树。并且二叉树中的子树有左右之分，其次序不能任意颠倒。图 1 描述了一个二叉树。

图 1 二叉树

遍历二叉树主要有两种方式，一种是循环遍历二叉树，另一种是递归遍历二叉树。如果二叉树节点较多，采用递归遍历会占用很多系统资源。因此，在应用程序中我们通常采用循环的方式遍历二叉树。但是利用循环遍历二叉树相对于递归的方式要复杂一些。首先需要设计栈结构，用于存储遍历的节点，利用栈结构的后进先出的特点，遍历所有节点。其主要思路是首先根据根节点遍历其下左子节点，直至左子节点为空，如图 2 所示。

图 2 遍历二叉树

然后将栈顶元素出栈（编号为 6），访问其节点数据，然后再次将栈顶元素出栈（编号为 5），访问节点数据，接着判断节点（编号为 5）是否有右子节点，如果有，则将右子节点入栈。循环的结束条件是栈为空，即栈中没有元素。效果如图 3 所示。

图 3 遍历二叉树