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.


 
#define NULL 0
 
Dim Shared As Byte maxnodos = 100
Dim Shared As Byte raiz = 0     
Dim Shared As Byte izda = 1     
Dim Shared As Byte dcha = 2     
Dim Shared As Byte arbol(maxnodos, 3)
 
Sub crear_arbol()
    arbol(1, raiz) = 1
    arbol(1, izda) = 2 : arbol(1, dcha) = 3
    arbol(2, raiz) = 2
    arbol(2, izda) = 4 : arbol(2, dcha) = 5
    arbol(3, raiz) = 3
    arbol(3, izda) = 6 : arbol(3, dcha) = NULL
    arbol(4, raiz) = 4
    arbol(4, izda) = 7 : arbol(4, dcha) = NULL
    arbol(5, raiz) = 5
    arbol(5, izda) = NULL : arbol(5, dcha) = NULL
    arbol(6, raiz) = 6
    arbol(6, izda) = 8 : arbol(6, dcha) = 9
    arbol(7, raiz) = 7
    arbol(7, izda) = NULL : arbol(7, dcha) = NULL
    arbol(8, raiz) = 8
    arbol(8, izda) = NULL : arbol(8, dcha) = NULL
    arbol(9, raiz) = 9
    arbol(9, izda) = NULL : arbol(9, dcha) = NULL
End Sub
 
Sub recorrido_preorder(nodo As Byte) 
    If nodo <> NULL Then             
        Print arbol(nodo, raiz);
        recorrido_preorder(arbol(nodo, izda))
        recorrido_preorder(arbol(nodo, dcha))
    End If
End Sub
 
Sub recorrido_postorder(nodo As Byte)
    If nodo <> NULL Then             
        recorrido_postorder(arbol(nodo, izda))
        recorrido_postorder(arbol(nodo, dcha))
        Print arbol(nodo, raiz);
    End If
End Sub
 
Sub recorrido_inorden(nodo As Byte)  
    If nodo <> NULL Then              
        recorrido_inorden(arbol(nodo, izda))
        Print arbol(nodo, raiz);
        recorrido_inorden(arbol(nodo, dcha))
    End If
End Sub
 
Sub recorrido_ordenXnivel(nodo As Byte)
    Dim As Byte actual = 1
    Dim As Byte primero_libre = actual + 1
    Dim As Byte cola(maxnodos) 
    cola(actual) = nodo
 
    While cola(actual) <> NULL
        If arbol(cola(actual), izda) <> NULL Then
            cola(primero_libre) = arbol(cola(actual), izda)
            primero_libre += 1
        End If
        If arbol(cola(actual), dcha) <> NULL Then
            cola(primero_libre) = arbol(cola(actual), dcha)
            primero_libre += 1
        End If
        Print arbol(cola(actual), raiz);
        actual += 1
    Wend
End Sub
 