Trees, representation of trees, traversal of trees

Definitions: nodes, parent-child relationship, root, leaves, external and internal nodes, ordered trees. Preorder traversal, postorder traversal. Binary trees, in-order traversal.
Arithmetic expression tree. Representation of trees: textual (left parenthetic and right parenthetic expressions, indented text, composite names), pointer structures. Implementation and examples.

Tree, Representation of a Tree, Traversal of a Tree using Java

Tree (ordered):


Example: Tree of an Arithmetic Expression

Aritmeetilise avaldise puu  



Infix:  (5 - 1) * 7 + 6 / 3

Prefix:  + (* (- (5, 1), 7), / (6, 3))

Postfix:  (((5, 1)-, 7)*, (6, 3)/ )+

RPN:  5 1 - 7 * 6 3 / +


Traversal of a Tree

Pre-order:

  1. Process a root
  2. Apply pre-order to all children from left to right

Post-order (end-order):

  1. Apply post-order to all children from left to right
  2. Process a root
In-order for a binary tree:
  1. Apply in-order to left subtree
  2. Process a root
  3. Apply in-order to right subtree

Prefix expression corresponds to pre-order, postfix expression and RPN to end-order, infix expression is not uniquely coded by in-order.

Puu


Pre-order: A B D G H E F I C J

Post-order: G H D E I F B J C A


Tree Representations

Graphical


Left parenthetic representation

A(B(D(G,H),E,F(I)),C(J))


Right parenthetic representation

(((G,H)D,E,(I)F)B,(J)C)A


Indentation

A

B

D
G

H
E

F
I
C

J

Composite names

A, A.B, A.C, A.B.D, A.B.E, A.B.F, A.B.D.G, A.B.D.H, A.B.F.I, A.C.J

Graph representations if the tree is not ordered: adjacency list, matrix etc.

Computer processing:

Pointer structures

       Illustration  

Examples


Tree in Java



import java.util.*;

public class TreeNode {

   private String name;
   private TreeNode rightSibling;
   private TreeNode firstChild;
   private int info;

   TreeNode (String s, TreeNode p, TreeNode a) {
      setName (s);
      setRightSibling (p);
      setFirstChild (a);
   }

   TreeNode (String s, TreeNode p, TreeNode a, int i) {
      setName (s);
      setRightSibling (p);
      setFirstChild (a);
      setInfo (i);
   }

   TreeNode() {
      this ("", null, null, 0);
   }

   TreeNode (String s) {
      this (s, null, null, 0);
   }

   TreeNode (String s, TreeNode p) {
      this (s, p, null, 0);
   }

   public void setName(String s) {
      name = s;
   }

   public String getName() {
      return name;
   }

   public void setRightSibling (TreeNode p) {
      rightSibling = p;
   }

   public TreeNode getRightSibling() {
      return rightSibling;
   }

   public void setFirstChild (TreeNode a) {
      firstChild = a;
   }

   public TreeNode getFirstChild() {
      return firstChild;
   }

   public void setInfo (int i) {
      info = i;
   }

   public int getInfo() {
      return info;
   }

   @Override
   public String toString() {
      return getName();  // TODO!!!
   }

   public void processTreeNode() {
      System.out.print (getName() + " ");
   }

   public void addChild (TreeNode a) {
      if (a == null)
         throw new IllegalArgumentException ("cannot add child null");
      TreeNode ptr = getFirstChild();
      if (ptr == null)
         setFirstChild (a);
      else {
         ptr = getFirstChild();
         while (ptr.getRightSibling() != null) {
            ptr = ptr.getRightSibling();
         }
         ptr.setRightSibling (a);
      }
   }

   public boolean isLeaf() {
      return (getFirstChild() == null);
   }

   public int size() {
      int n = 1; // root
      TreeNode ptr = getFirstChild();
      while (ptr != null) {
         n = n + ptr.size();
         ptr = ptr.getRightSibling();
      }
      return n;
   }

   public void preorder() {
      processTreeNode();
      TreeNode ptr = getFirstChild();
      while (ptr != null) {
         ptr.preorder();
         ptr = ptr.getRightSibling();
      }
   }

   public void postorder() {
      TreeNode ptr = getFirstChild();
      while (ptr != null) {
         ptr.postorder();
         ptr = ptr.getRightSibling();
      }
      processTreeNode();
   }

   public static TreeNode createTree() {
      TreeNode root = new TreeNode ("+", null,
         new TreeNode ("*",
            new TreeNode ("/", null,
               new TreeNode ("6",
                  new TreeNode ("3", null, null),
                  null)),
            new TreeNode ("-",
               new TreeNode ("4", null, null),
               new TreeNode ("2",
                  new TreeNode ("1", null, null),
                  null))));
      return root;
   }

   public static void main (String[] param) {
      TreeNode t = createTree();
      System.out.println ("Number of nodes: " + String.valueOf (t.size()));
      System.out.print ("Preorder:  ");
      t.preorder();
      System.out.println();
      System.out.print ("Postorder: ");
      t.postorder();
      System.out.println();
   }

}

Jaanus Pöial