一种易理解的非递归二叉树遍历算法

An Intelligible Non-Recursive Algorithm of Traversing Binary Tree

大量已存在的二叉树非递归遍历算法的缺陷是过程不清晰。通过分析二叉树遍历过程中每个结点的进出栈情况,用简单的图示说明了一种易理解的非递归遍历二叉树的算法,实现了此算法,并说明了它的正确性,分析了它的时间及空间复杂度。三种遍历方式都可以通过此算法实现。

There are many non-recursive algorithms of traversing binary tree, the limitation of those is obscurity of their process. By analyzing how every node enters and exits stack in the process of traversing binary tree, illustrates a very intelligible non-recursive algorithm of traversing binary tree. The algorithm is realized and its correctness is illuminated, analyzes its time and space complexities. The algorithm applies to three modes of traversing binary tree.