期刊论文

中文

武汉轻工大学学报

2095-7386

2012

4

59-63

10.3969/j.issn.1009-4881.2012.04.016

国家自然科学基金资助项目（61179032）；

本校为第一机构

针对现有二叉树的非递归遍历算法在分配栈空间和队列空间方面的不足,提出了一个适用于二叉树非递归遍历算法的动态栈和动态队列,其中动态栈应用于先序遍历、中序遍历和后序遍历的非递归算法,而动态队列应用于层次遍历二叉树的非递归算法。给出了二叉树非递归遍历的算法描述和算法实现。算法测试表明:通过限制单链表的操作得到的链栈和链队列既满足了二叉树非递归遍历算法对栈空间和队列空间的需求,又能伴随遍历的进行动态增加和减少多余的栈空间和队列空间。由于单链表的这种易于扩充性很好地适应二叉树非递归遍历算法对栈空间和队列空间的需求,使得二叉树的非递归遍历算法的通用性和适应性大大...

In view of the existing deficiency in the allocation of stack and queue space of the two binary tree non-recursive traversal algorithm,this paper presents an applicable dynamic stack and dynamic queue to two binary tree non-recursive traversal algorithm.On the one hand,the dynamic stack is applied preorder,inorder and postorder traversal non-recursive algorithm.On the other hand,the dynamic queue is applied to the level traversal of the two forks tree non-recursive algorithm.It supplies the description and implementation of the two binary tree ...