About this Computer Science article
Traversing binary tree structures with shift register memories (Recent Results) by W. E. Kluge is a Computer Science article available to read on EtoBox.
The paper proposes a tree-structured shift register memory in which traversals of binary data tress in pre-or end-order are performed as sequences of two non-cyclic data permutations which move the data tree relative to a unique access port that is located in the root node of the memory tree. These two permutations, denoted A and B, emulate elementary traversal steps. Permutations A correspond to traversals between nodes of an even tree level and the next higher odd level, permutations B correspond to traversals between nodes of an odd tree level and the next higher even level. Traveling from a node to its left successor requires one permutation, traveling to its right successor requires two identical permutations in succession. Three identical permutations in succession perform a counter-clockwise cyclic traversal within a subtree which comprises a (root) node, its left successor node and its right successor node; i.e. subsequences AAA and BBB yield identity. Accordingly, if the conventional address assignment of trees applies, then the permutation (traversal) sequence that is effective on the memory corresponds to the address of the node that is actually being visited. Starting t
It is typically read by researchers, students, and practitioners in Computer Science.
- Author
- W. E. Kluge
- Publisher
- ACM
- Published
- 1976
- Language
- EN
- Field
- Computer Science (Physical Sciences)