一种新的二叉树后序遍历的非递归算法  

A New Non-recursive Algorithm of Post-order Ttraversal of a Binary Tree

作　　者：张建波 ZHANG Jian-bo(School of Mathematics and Statistics,Northeastern University at Qinhuangdao,Qinhuangdao 066004,China)

机构地区：[1]东北大学秦皇岛分校数学与统计学院,河北省秦皇岛市066004

出　　处：《电脑与信息技术》2020年第5期19-22,共4页Computer and Information Technology

基　　金：2019年河北省高等教育教学改革与实践项目(项目编号:2018GJJG419)。

摘　　要：目前,大多数《数据结构》教材在提到二叉树后序遍历非递归算法时,都要求树中每个结点两次进栈和出栈才能被访问,因此算法效率不高。针对该问题,文章提出了一种新的二叉树后序遍历非递归算法。与教材给出的算法相比,所提算法不需要设置“退栈标记”,且每个结点只需一次进栈和出栈,因此所提算法的时空效率优于教材中的算法。最后,本文通过实例验证了所提算法的有效性。At present,the non-recursive algorithm of post-order traversal of binary tree presented in most of the“Data Structure”textbooks is not efficient since it needs each tree node“Push”and“Pop”stack operation two times before it visited.So,author proposed a new non-recursive algorithm of post-order traversal.Comparing to the existing algorithms,the proposed method does not introduce“existing-stack mark”in each node,and needs“Push”and“Pop”operation only once.Therefore,the proposed method need lesser time and space costs than the existing ones.Finally,an experiment is given and demonstrates the effectiveness of the proposed approach.

关 键 词：二叉树遍历 后序遍历 递归 非递归 栈 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论]