examples/rosettacode/tree_traversal.nit

   1 #!/usr/bin/env nit
   2 #
   3 # This file is part of NIT ( http://www.nitlanguage.org ).
   4 # This program is public domain
   5
   6 # Task: Tree traversal
   7 #
   8 # SEE: http://rosettacode.org/wiki/Tree_traversal
   9 module tree_traversal
  10
  11 class Node
  12         var value: Int
  13         var left: nullable Node
  14         var right: nullable Node
  15
  16         fun preorder
  17         do
  18                 print value
  19                 var l = left
  20                 if l != null then l.preorder
  21                 var r = right
  22                 if r != null then r.preorder
  23         end
  24
  25         fun inorder
  26         do
  27                 var l = left
  28                 if l != null then l.inorder
  29                 print value
  30                 var r = right
  31                 if r != null then r.inorder
  32         end
  33
  34         fun postorder
  35         do
  36                 var l = left
  37                 if l != null then l.postorder
  38                 var r = right
  39                 if r != null then r.postorder
  40                 print value
  41         end
  42
  43         fun levelorder
  44         do
  45                 var q = new List[Node]
  46                 q.add self
  47                 while q.not_empty do
  48                         var n = q.shift
  49                         print n.value
  50                         var l = n.left
  51                         if l != null then q.push l
  52                         var r = n.right
  53                         if r != null then q.push r
  54                 end
  55         end
  56 end
  57
  58 var tree = new Node(1,
  59         new Node(2,
  60                 new Node(4,
  61                         new Node(7)),
  62                 new Node(5)),
  63         new Node(3,
  64                 new Node(6,
  65                         new Node(8),
  66                         new Node(9))))
  67
  68 print "preorder:"
  69 tree.preorder
  70 print "inorder:"
  71 tree.inorder
  72 print "postorder:"
  73 tree.postorder
  74 print "levelorder:"
  75 tree.levelorder