Task

Implement a binary tree where each node carries an integer,   and implement:

   pre-order,
   in-order, 
   post-order,     and 
   level-order   traversal. 


Use those traversals to output the following tree:

         1
        / \
       /   \
      /     \
     2       3
    / \     /
   4   5   6
  /       / \
 7       8   9

The correct output should look like this:

preorder:    1 2 4 7 5 3 6 8 9
inorder:     7 4 2 5 1 8 6 9 3
postorder:   7 4 5 2 8 9 6 3 1
level-order: 1 2 3 4 5 6 7 8 9



See also

   Wikipedia article:   Tree traversal.


 
﻿﻿use Collection;
 
class Test {
  function : Main(args : String[]) ~ Nil {
    one := Node->New(1);
    two := Node->New(2);
    three := Node->New(3);
    four := Node->New(4);
    five := Node->New(5);
    six := Node->New(6);
    seven := Node->New(7);
    eight := Node->New(8);
    nine := Node->New(9);
 
    one->SetLeft(two); one->SetRight(three);
    two->SetLeft(four); two->SetRight(five);
    three->SetLeft(six); four->SetLeft(seven);
    six->SetLeft(eight); six->SetRight(nine);
 
    "Preorder: "->Print(); Preorder(one); 
    "\nInorder: "->Print(); Inorder(one);
    "\nPostorder: "->Print(); Postorder(one);
    "\nLevelorder: "->Print(); Levelorder(one);
    "\n"->Print();
  }
 
  function : Preorder(node : Node) ~ Nil {
    if(node <> Nil) {
      System.IO.Console->Print(node->GetData())->Print(", ");
      Preorder(node->GetLeft());    
      Preorder(node->GetRight());    
    };
  }  
 
  function : Inorder(node : Node) ~ Nil {
    if(node <> Nil) {
      Inorder(node->GetLeft());  
      System.IO.Console->Print(node->GetData())->Print(", ");
      Inorder(node->GetRight());    
    };
  }
 
  function : Postorder(node : Node) ~ Nil {
    if(node <> Nil) {
      Postorder(node->GetLeft());    
      Postorder(node->GetRight());
      System.IO.Console->Print(node->GetData())->Print(", ");
    };
  }
 
  function : Levelorder(node : Node) ~ Nil {
    nodequeue := Collection.Queue->New();
    if(node <> Nil) {
      nodequeue->Add(node);
    };
 
    while(nodequeue->IsEmpty() = false) {
      next := nodequeue->Remove()->As(Node);
      System.IO.Console->Print(next->GetData())->Print(", ");
      if(next->GetLeft() <> Nil) {
        nodequeue->Add(next->GetLeft());
      };
 
      if(next->GetRight() <> Nil) {
        nodequeue->Add(next->GetRight());
      };
    };
  }
}
 
class Node from BasicCompare {
  @left : Node;
  @right : Node;
  @data : Int;
 
  New(data : Int) {
    Parent();
    @data := data;
  }  
 
  method : public : GetData() ~ Int {
    return @data;
  }
 
  method : public : SetLeft(left : Node) ~ Nil {
    @left := left;
  }
 
  method : public : GetLeft() ~ Node {
    return @left;
  }
 
  method : public : SetRight(right : Node) ~ Nil {
    @right := right;
  }
 
  method : public : GetRight() ~ Node {
    return @right;
  }
 
  method : public : Compare(rhs : Compare) ~ Int {
    right : Node := rhs->As(Node);
    if(@data = right->GetData()) {
      return 0;
    }
    else if(@data < right->GetData()) {
      return -1;
    };
 
    return 1;
  }
}
 