Representing Two-Dimensional Trees

Internal Two-Dimensional Tree Representation

When writing the internal representation of trees it is simpler to not acknowledge nodes as separate from trees. The label and state values are hence associated with instances of trees rather than nodes. Beyond the label and state stored in each instance of the tree class there are links which point to the right and left children of the node with a NULL pointer representing links that are empty because there is no child.

Relevant portion of the 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.                   *
 *                                                                      *
 * void set_left( tree<sobj, qobj>* new_link)                           *
 *  Sets the left link of the tree to point to new_link                 *
 *                                                                      *
 * void set_right( tree<sobj, qobj>* new_link)                          *
 *  Sets the right link of the tree to point 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.                                      *
 *                                                                      *
 ************************************************************************/

enum nodes {LEFT = 0, RIGHT, THIRD};

 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* new_link) { lnk[l] = new_link; }
  void set_left( tree* new_link) { set_link( LEFT, new_link ); }
  void set_right( tree* new_link) { set_link( RIGHT,
                                                          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;
};

External Two-Dimensional Tree Representation

The recursive definition for the linear representation of trees begins with the empty tree which we designate as a tilde, "~". It is also possible to add a parent to any tree. This can either designate only left children or left and right children of a parent. These are represented as the label symbol of the parent followed by the left and right children in parenthesis separated by commas. Thus, all leaves will look like X(~,~). And above this other nodes may be added by designating the leaves as children of parent nodes.

Inductive Definition

An empty tree is defined as ~.
X(tl,tr) is a tree.
No other strings are trees.

X values are elements of the label set.
tl and tr are tree representations (left and right children).

Example Tree

Linear Representation of Example Tree

a(b(c(~,~),d(~,~)),e(f(~,~),~))

Looking for something that's not here? Contact:

Last updated: Monday, 26-Jul-2004 14:22:53 EST
#504