Recursive and Nonrecursive Traversal Algorithms for Dynamically Created Binary Trees  

作　　者：Robert Logozar 

机构地区：[1]Polytechnic of Varazdin, HR-42000 Varazdin, Croatia

出　　处：《Computer Technology and Application》2012年第5期374-382,共9页计算机技术与应用（英文版）

摘　　要：The modeling of dynamical systems from a time series implemented by our DSA program introduces binary trees of height D with all leaves on the same level, and the related subtrees of height L 〈 D. These are called e-trees and e-subtrees. The recursive and nonrecursive versions of the traversal algorithms for the trees with dynamically created nodes are discussed. The original nonrecursive algorithms that return the pointer to the next node in preorder, inorder and postorder traversals are presented. The space-time complexity analysis shows and the execution time measurements confirm that for these O（2D） algorithms, the recursive versions have approximately 10-25% better time constants. Still, the use of nonrecursive algorithms may be more appropriate in several occasions.

关 键 词：Binary e-trees algorithms tree traversal PREORDER inorder postorder RECURSIVE nonrecursive space-time complexity. 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TP311.12[自动化与计算机技术—计算机科学与技术]