6.10.  Recursions on Binary Trees

There are many natural algorithms on binary trees that could be described recursivly. The scheme for recursions on binary trees is suggested in the following figure:

Procedure recursive_on_tree( node n)

Examples:

Action = print the label of the node

• Preorder traversion:

  Procedure Preorder_Traversion( node n)

  

• Inorder traversion:

  Procedure Inorder_Traversion( node n)

  

• Postorder traversion:

  Procedure Postorder_Traversion( node n)

  

Examples:

• Tree 1:

  

Traverse the tree in (in | post | pre)-order

• Tree 2:

  

Last modified 22/May/97