engleski

Recursive and Nonrecursive Traversal Algorithms for Dynamically Created Binary Trees

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 ε-trees and ε-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(2^D) 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 -trees; algorithms; tree traversal; preorder; inorder; postorder; recursive; nonrecursive; space-time complexity

nije evidentirano