基于单链表的二叉树非递归遍历算法

Non-recursive algorithm about two binary tree traversal based on a single linked list

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

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 non-recursive traversal algorithm.The algorithm testing shows： By limiting the operation of a single linked list,we get the linked stack and linked queue.The linked stack and linked queue can satisfy the stack and queue space requirements of the two binary tree non-recursive traversal algorithm,and increase or reduce the dynamic redundant stack and queue space.As a result this easy extendibility of the single linked list,it is well adapted to the two binary tree non-recursive traversal algorithm on the stack and queue space requirements,and greatly increases versatility and adaptability of the two binary tree non-recursive traversal algorithm.