中文摘要：

提出树遍历统一的新解法,使其非递归算法像递归算法一样简单.首先以后序遍历为例,基于结点状态标记和遍历规则提取,从遍历定义导出遍历的递推公式,由此机械获得非递归算法和循环不变式,并用形式化方法证明其正确性.之后按不同遍历定义变换公式参数,获得二叉树前序、中序和K叉树前序、后序的递推公式,所得算法比传统算法更简洁直观,表明本解法的有效性和通用性.

英文摘要：

A united solution of tree traversal is presented.It makes its non-recursive algorithms are same easy as its recursive algorithms.From the definition of postorder,by marking node states and extracting rules,the recurrence formula of postorder is derived.Then,non-recursive algorithm and its loop invariant are obtained mechanically according to the formula,their correctness are proved formally.Furthermore,some recurrence formulas of other kinds of traversals,including preorder/inorder of binary tree,and preorder/postorder of K-ary tree,are obtained by changing formula＇s parameters according to their traversal definitions,and the algorithms are more simple than the traditional.Results show that our solution is valid and united.