Yield Projecting Algorithm

After determining how we are going to represent the spines and heads of multidimensional trees in both the internal and external form, we were able to write a program that would take an n-dimensional tree and collapse it to return the (n-1)-dimensional tree with the same yield. Using this, we could easily extend it to take an n-dimensional tree and return it's string yield.

The algorithm works by recursively traversing down the tree from the root to the leaves. While most of our previous algorithms have used a bottom-up method, we ran into problems and decided to use a top-down method (solutions to these problems were not explored, we simply decided to take the easier route). At each node with an n-dimensional successor, the node is replaced with it's (n-1)-dimensional yield, and the node's successors in the other dimensions are hung on the proper heads of the new yield. At each node without an n-dimensional yield, the algorithm is recursively run on its other successors. When the algorithm returns, the tree has been transformed from an n-dimensional tree to an (n-1)-dimensional tree with the same yield.

| CS Home | Earlham College | WebDB | Earlham Mail | Earlham Libraries | Word Online |

Copyright © 1996-2002 by Earlham College Computer Science Department.
If you're curious about why we copyright, see Peter Suber's Why Copyright Web Documents?.

Looking for something that's not here? Contact:
Last updated: Monday, 26-Jul-2004 14:22:53 EST
#889