Bubble Structure and Operation to Facilitate Tree Traversal
Original Publication Date: 1984-Feb-01
Included in the Prior Art Database: 2005-Feb-02
This article describes a bubble hardware and an algorithm including swap/edit gates and a level indicator for performing tree traversal. I. Introduction A binary tree may be defined recursively as consisting of a root node, a left binary subtree, and a right binary subtree. Binary trees are often encountered in computer data and program structures; their applications and mathematical properties have been discussed extensively (e.g., see Knuth 1). In different hardwares the binary tree is represented, implemented and manipulated differently. For example, a complete binary tree (each node with two identical subtrees except for the terminal nodes) can be represented by labelling a node i, its left successor node 2i, and its right successor node 2i+1, starting with the root node labelled as 1.