A note on the nonrecursive traversal of binary trees

Open Access
Publisher Website
Google Scholar
Abstract
A nonrecursive procedure is developed for traversing unthreaded binary trees in a fixed space and in time proportional to tree size. Burkhard (1975) gives a way to do this without requiring a tag field, but with the requirement that descendent nodes have greater addresses than parents. Knuth (1968) gives a way to do such a traverse but requires a tag field. This paper develops one program that realises either variation (for preorder, symmetric order or endorder traversal for tagged or ordered trees). The development is based on a careful, stepwise rewriting of a simple traversal program, confirming Knuth's claim (1974) that program manipulation is a useful technique for program development.

This publication has 0 references indexed in Scilit: