[logo.png] computerscience@earlham.edu

Representing
Multidimensional Trees


Representing Multidimensional Trees


External Representation

N-dimensional trees can be represented as strings using the node label followed by parentheses to enclose the list of children that each node is a parent of. This list is separated by commas. A tilde is used to represent a location where there is no child. For any node A with no children, the string representation would be A(~,~,~,...,~) where the number of tildes is equal to the number of dimensions. The first element of the list is the child in the nth dimension, the next is the child in the n-1th dimension, and so on until the last element of the list the is the first dimensional child. This model allows trees of unbounded dimension and there is no restriction on the branching factor. Compared with our two-dimensional model, the notion of a "left" and "right" child is lost. Realize that in this new model, the parent's left child is the second dimensional child and the parent's right child is the first dimensional child of the second dimensional child.

Inductive Definition

Example 1

Consider the following tree:

            A      
           / \     
          B   C    
             / \   
            D   E  
This 2-dimensional tree would be written A(B(~,C(D(~,E(~,~)),~)),~). This can be better visualized by redrawing the tree:

           A--~
           |
           B--C--~
           |  |
           ~  D--E--~
              |  |
              ~  ~

Example 2

While it becomes hard to draw trees of more dimensions, the string representation of them remains almost as simple. Lets keep the tree above and consider this tree to be hanging in the third dimension underneath node C:

          F--~
          |
          G--H--I--~
          |  |  |
          ~  ~  ~
Since we are now in three dimensions, we must add a tilde to every node (except C) signifying no child in the third dimension. We get the string A(~,B(~,~,C(F(~,G(~,~,H(~,~,I(~,~,~))),~),D(~,~,E(~,~,~)),~)),~).


Internal Data Structures

To represent these trees as data structures, we use a directed graph to store the nodes and edges. The class "tree" is one node and holds the state, label, and list of edges (pointers to other instances of tree). The list is implemented as a vector, so the dimensionality of the tree can be dynamically changed. The constructor will take the label, initial state, and dimensionality of the node. There are member functions to set each link and access the links, set and access the label and state, and get the dimensionality of the node.

The standard method of creating a tree is to declare the root node of the tree, and use the set_link function to add nodes, using the constructor in the arguments to create the tree in dynamic memory.

Tree class definition


/************************************************************************
 * File: tree.h                                                         *
 *                                                                      *
 * tree(const sobj& init_label = sobj( ),                               *
 *      const qobj& init_state = qobj( ),                               *
 *      unsigned int n_dims = 3)                                        *
 *  The constructor sets the label of the node to init_label and the    *
 *   state to init_state.  It also creates a vector of null pointers    *
 *   of length n_dims to represent the number of dimensions of the tree.*
 *                                                                      *
 * tree( const tree& source )                                           *
 *  The tree will be initialized to be equal to source.                 *
 *                                                                      *
 * ~tree( )                                                             *
 *  Recursively deletes itself and all children.                        *
 *                                                                      *
 * void set_label(const sobj& new_label)                                *
 *  Sets the label of the node to new_label.                            *
 *                                                                      *
 * void set_state(const qobj& new_state)                                *
 *  Sets the state of the node new_state;                               *
 *                                                                      *
 * void set_link(int l, tree< sobj, qobj >* new_link)                   *
 *  Sets the l dimensional child pointer to new_link.                   *
 *                                                                      *
 * const sobj* label( ) const                                           *
 * sobj& label( )                                                       *
 *  Returns the label of the node.                                      *
 *                                                                      *
 * const qobj* state( ) const                                           *
 * qobj& state( )                                                       *
 *  Returns the state of the node.                                      *
 *                                                                      *
 * unsigned int dim( ) const                                            *
 *  Returns the dimensionality of the node.                             *
 *                                                                      *
 * const tree< sobj, qobj >* link(int l) const                          *
 * tree< sobj, qobj >* link(int l)                                      *
 *  Returns a pointer to the child in the l dimension.                  *
 ************************************************************************/
 
 

template < class sobj, class qobj > class tree
{
 public:
  
  // CONSTRUCTORS
  tree(const sobj& init_label = sobj( ),
       const qobj& init_state = qobj( ),
       unsigned int n_dims = 3);
  tree( const tree& source);
  ~tree( );
   
  tree< sobj, qobj >* operator=(const tree& source);
    
  // Member functions to set the data and link fields
  void set_label(const sobj& new_label); 
  void set_state(const qobj& new_state); 
  void set_link(int l, tree< sobj, qobj >* new_link);
  
  // Constant member function to retrieve the current data
  const sobj& label( ) const; 
  sobj& label( ); 
  const qobj& state( ) const;
  qobj& state( );
  unsigned int dim( ) const; 
  const tree< sobj, qobj >* link(int l) const; 
  tree< sobj, qobj >* link(int l);
    
 private:
  sobj label_field;
  qobj state_field;
  vector< tree< sobj, qobj >* > lnk;
};

[an error occurred while processing this directive]