Tree traversal (a Rosetttacode.org Task)

The Task
From this tree

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

We want to do some traversals, so this is the output:
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




Solutions:

Using a tuple for tree

A tuple is an "auto array" in M2000 Interpreter. (,) is the zero length array.

 Module CheckIt {
      Null=(,)
      Tree=((((Null,7,Null),4,Null),2,(Null,5,Null)),1,(((Null,8,Null),6,(Null,9,Null)),3,Null))

      Module preorder (T) {
            Print "preorder:    ";
            printtree(T)
            Print
            sub printtree(T)
                  Print T#val(1);" ";
                  If len(T#val(0))>0 then printtree(T#val(0))
                  If len(T#val(2))>0 then printtree(T#val(2))
            end sub
      }
      preorder Tree

      Module inorder (T) {
            Print "inorder:     ";
            printtree(T)
            Print
            sub printtree(T)
                  If len(T#val(0))>0 then printtree(T#val(0))
                  Print T#val(1);" ";
                  If len(T#val(2))>0 then printtree(T#val(2))
            end sub
      }
      inorder Tree

      Module postorder (T) {
            Print "postorder:   ";
            printtree(T)
            Print
            sub printtree(T)
                  If len(T#val(0))>0 then printtree(T#val(0))
                  If len(T#val(2))>0 then printtree(T#val(2))
                  Print T#val(1);" ";
            end sub
      }
      postorder Tree

      Module level_order (T) {
            Print "level-order: ";
            Stack New {
                  printtree(T)
                  if empty then exit
                  Read T
                  Loop
            }
            Print
            sub printtree(T)
                  If Len(T)>0 then
                        Print T#val(1);" ";
                        Data T#val(0), T#val(2)
                  end if
            end sub
      }
      level_order Tree
}
CheckIt


Using OOP(1)

Now tree is nodes with pointers to nodes (a node ifs a Group, the user object) The "as pointer" is optional, but we can use type check if we want.
 
Module OOP {
      \\ Class is a global function (until this module end)
      Class Null {
      }
      \\ Null is a pointer to an object returned from class Null()
      Global Null->Null()
      Class Node {
      Public:
            x, Group LeftNode, Group RightNode
      Class:
            \\ after class:  anything exist one time,
            \\ not included in final object
            Module Node {
                  .LeftNode<=Null
                  .RightNode<=Null
                  Read .x
                  \\ read ? for optional values
                  Read ? .LeftNode, .RightNode
            }
      }
      \\ NodeTree return a pointer to a new Node
      Function NodeTree {
            \\ ![] pass currrent stack to Node()
            ->Node(![])
      }

      Tree=NodeTree(1, NodeTree(2,NodeTree(4, NodeTree(7)), NodeTree(5)), NodeTree(3, NodeTree(6, NodeTree(8), NodeTree(9))))

      Module preorder (T) {
            Print "preorder:    ";
            printtree(T)
            Print
            sub printtree(T as pointer)
                  If T is Null then Exit sub
                  Print T=>x;" ";
                  printtree(T=>LeftNode)
                  printtree(T=>RightNode)
            end sub
      }
      preorder Tree
      Module inorder (T) {
            Print "inorder:     ";
            printtree(T)
            Print
            sub printtree(T as pointer)
                  If T is Null then Exit sub
                  printtree(T=>LeftNode)
                  Print T=>x;" ";
                  printtree(T=>RightNode)
            end sub
      }
      inorder Tree
      Module postorder (T) {
            Print "postorder:   ";
            printtree(T)
            Print
            sub printtree(T as pointer)
                  If T is Null then Exit sub
                  printtree(T=>LeftNode)
                  printtree(T=>RightNode)
                  Print T=>x;" ";
            end sub
      }
      postorder Tree
      Module level_order (T) {
            Print "level-order: ";
            Stack New {
                  printtree(T)
                  if empty then exit
                  Read T
                  Loop
            }
            Print
            sub printtree(T as pointer)
                  If T is Null else
                        Print T=>x;" ";
                        Data T=>LeftNode, T=>RightNode
                  end if
            end sub
      }
      level_order Tree
}
OOP


Using OOP(2)
We can put modules inside Node Class as methods also i put a visitor as a call back (a lambda function called as module)

Module OOP {
      \\ Class is a global function (until this module end)
      Class Null {
      }
      \\ Null is a pointer to an object returned from class Null()
      Global Null->Null()
      Class Node {
      Public:
            x, Group LeftNode, Group RightNode
            Module preorder (visitor){
                  T->This
                  printtree(T)
                  sub printtree(T as pointer)
                        If T is Null then Exit sub
                        call visitor(T=>x)
                        printtree(T=>LeftNode)
                        printtree(T=>RightNode)
                  end sub
            }
            Module inorder (visitor){
                  T->This
                  printtree(T)
                  sub printtree(T as pointer)
                        If T is Null then Exit sub
                        printtree(T=>LeftNode)
                        call visitor(T=>x)
                        printtree(T=>RightNode)
                  end sub
            }
            Module postorder (visitor) {
                  T->This
                  printtree(T)
                  sub printtree(T as pointer)
                        If T is Null then Exit sub
                        printtree(T=>LeftNode)
                        printtree(T=>RightNode)
                        call visitor(T=>x)
                  end sub
            }
            Module level_order (visitor){
                  T->This
                  Stack New {
                        printtree(T)
                        if empty then exit
                        Read T
                        Loop
                  }
                  sub printtree(T as pointer)
                        If T is Null else
                              call visitor(T=>x)
                              Data T=>LeftNode, T=>RightNode
                        end if
                  end sub
            }
      Class:
            \\ after class:  anything exist one time,
            \\ not included in final object
            Module Node {
                  .LeftNode<=Null
                  .RightNode<=Null
                  Read .x
                  \\ read ? for optional values
                  Read ? .LeftNode, .RightNode
            }
      }
      \\ NodeTree return a pointer to a new Node
      Function NodeTree {
            \\ ![] pass currrent stack to Node()
            ->Node(![])
      }

      Tree=NodeTree(1, NodeTree(2,NodeTree(4, NodeTree(7)), NodeTree(5)), NodeTree(3, NodeTree(6, NodeTree(8), NodeTree(9))))

      printnum=lambda (title$) -> {
            Print
            Print title$;
            =lambda (x)-> {
                  Print x;" ";
            }
      }
      Tree=>preorder printnum("preorder:    ")
      Tree=>inorder printnum("inorder:     ")
      Tree=>postorder printnum("postorder:   ")
      Tree=>level_order printnum("level-order: ")
}
OOP

Using OOP(3)
Using Event object as visitor
Module OOP {
      \\ Class is a global function (until this module end)
      Class Null {
      }
      \\ Null is a pointer to an object returned from class Null()
      Global Null->Null()
      Class Node {
      Public:
            x, Group LeftNode, Group RightNode
            Module preorder (visitor){
                  T->This
                  printtree(T)
                  sub printtree(T as pointer)
                        If T is Null then Exit sub
                        call event visitor, T=>x
                        printtree(T=>LeftNode)
                        printtree(T=>RightNode)
                  end sub
            }
            Module inorder (visitor){
                  T->This
                  printtree(T)
                  sub printtree(T as pointer)
                        If T is Null then Exit sub
                        printtree(T=>LeftNode)
                        call event visitor, T=>x
                        printtree(T=>RightNode)
                  end sub
            }
            Module postorder (visitor) {
                  T->This
                  printtree(T)
                  sub printtree(T as pointer)
                        If T is Null then Exit sub
                        printtree(T=>LeftNode)
                        printtree(T=>RightNode)
                        call event visitor, T=>x
                  end sub
            }
            Module level_order (visitor){
                  T->This
                  Stack New {
                        printtree(T)
                        if empty then exit
                        Read T
                        Loop
                  }
                  sub printtree(T as pointer)
                        If T is Null else
                              call event visitor, T=>x
                              Data T=>LeftNode, T=>RightNode
                        end if
                  end sub
            }
      Class:
            \\ after class:  anything exist one time,
            \\ not included in final object
            Module Node {
                  .LeftNode<=Null
                  .RightNode<=Null
                  Read .x
                  \\ read ? for optional values
                  Read ? .LeftNode, .RightNode
            }
      }
      \\ NodeTree return a pointer to a new Node
      Function NodeTree {
            \\ ![] pass currrent stack to Node()
            ->Node(![])
      }

      Tree=NodeTree(1, NodeTree(2,NodeTree(4, NodeTree(7)), NodeTree(5)), NodeTree(3, NodeTree(6, NodeTree(8), NodeTree(9))))
      Event PrintAnum {
            read x
      }
      Function PrintThis(x) {
                Print x;" ";
      }
      Event PrintAnum New PrintThis()
      printnum=lambda PrintAnum (title$) -> {
            Print
            Print title$;
            =PrintAnum
      }
      Tree=>preorder printnum("preorder:    ")
      Tree=>inorder printnum("inorder:     ")
      Tree=>postorder printnum("postorder:   ")
      Tree=>level_order printnum("level-order: ")
}
OOP