Premium
Generalized non‐recursive traversal of binary trees
Author(s) -
Kilgour A. C.
Publication year - 1981
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.4380111207
Subject(s) - tree traversal , pointer (user interface) , binary tree , computer science , binary search tree , algorithm , pascal (unit) , graph traversal , binary number , notation , generalization , theoretical computer science , mathematics , arithmetic , programming language , mathematical analysis , computer vision
A non‐recursive algorithm for the traversal of a binary tree is presented in which the order of traversal is defined by an external data array, allowing any of the six possible orders to be selected without modification to the algorithm itself. The extra storage requirements are three pointer variables and two bits per node (or two bits per level if an auxiliary stack is used.) The algorithm is a generalization of the pointer reversal method of Schorr and Waite and is derived by transformation of a generalized recursive version. The algorithm is described using the notation and conventions of Pascal.