General Trees

Suitable for representing hierarchies

AbstractDataType tree{ 
  instances 
    A set of elements: (1) empty or having a distinguished root element 
    (2) each non-root element having exactly one parent element 
  operations 
    root() 
    degree() 
    child(k) 
} 

Concepts: tree, subtree, root, leaf, parent, children, level, degree of node, degree of tree, height

Properties

• Full tree A tree with all the leaves at the same level, and all the non-leaves having the same degree.
  
• Complete Tree A full tree in which the ‘last’ elements are deleted.
  
• Level h of a full tree has d^h-1 nodes.
• The first h levels of a full tree have
  
  nodes.
• A tree of height h and degree d has at most d^h - 1 elements
  

Traversal

Level order

x := root() 
if( x ) queue (x) 
while( queue not empty ){ 
  x := dequeue() 
  visit() 
  i=1; while( i <= degree() ){ 
     queue( child(i) ) 
  } 
} 

Preorder

procedure preorder(x){ 
  visit(x) 
  i=1; while( i <= degree() ){ 
     preorder( child(i) ) 
  } 
} 

Postorder

procedure postorder(x){ 
  i=1; while( i <= degree() ){ 
     postorder( child(i) ) 
  } 
  visit(x) 
} 

Inorder

Meaningful just for binary trees.

procedure inorder(x){ 
  if( left_child_for(x) ) { inorder( left_child(x)  ) } 
  visit(x) 
  if( right_child_for(x) ) { inorder( right_child(x)  ) } 
} 

Usages for ‘visit’: determine the height, count the number of elements

Representations

1. Nodes consisting of a data field and k pointers
   
2. Nodes consisting of w data field and two pointers: a pointer to the first child, and a pointer to the next sibling.
   
3. A tree of degree k assumes an array for holding a complete tree of degree k, with empty cells assigned for missing elements.