Tree traversal

Implement a binary tree where each node carries an integer, and implement preoder, inorder, postorder 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

C

include <stdlib.h>
include <stdio.h>

typedef struct node_s {

 int value;
 struct node_s* left;
 struct node_s* right;

} *node;

node tree(int v, node l, node r) {

 node n = malloc(sizeof(struct node_s));
 n->value = v;
 n->left  = l;
 n->right = r;
 return n;

}

void destroy_tree(node n) {

 if (n->left)
   destroy_tree(n->left);
 if (n->right)
   destroy_tree(n->right);
 free(n);

}

void preorder(node n, void (*f)(int)) {

 f(n->value);
 if (n->left)
   preorder(n->left, f);
 if (n->right)
   preorder(n->right, f);

}

void inorder(node n, void (*f)(int)) {

 if (n->left)
   inorder(n->left, f);
 f(n->value);
 if (n->right)
   inorder(n->right, f);

}

void postorder(node n, void (*f)(int)) {

 if (n->left)
   postorder(n->left, f);
 if (n->right)
   postorder(n->right, f);
 f(n->value);

}

/* helper queue for levelorder */ typedef struct qnode_s {

 struct qnode_s* next;
 node value;

} *qnode;

typedef struct { qnode begin, end; } queue;

void enqueue(queue* q, node n) {

 qnode node = malloc(sizeof(struct qnode_s));
 node->value = n;
 node->next = 0;
 if (q->end)
   q->end->next = node;
 else
   q->begin = node;
 q->end = node;

}

node dequeue(queue* q) {

 node tmp = q->begin->value;
 qnode second = q->begin->next;
 free(q->begin);
 q->begin = second;
 if (!q->begin)
   q->end = 0;
 return tmp;

}

int queue_empty(queue* q) {

 return !q->begin;

}

void levelorder(node n, void(*f)(int)) {

 queue nodequeue = {};
 enqueue(&nodequeue, n);
 while (!queue_empty(&nodequeue))
 {
   node next = dequeue(&nodequeue);
   f(next->value);
   if (next->left)
     enqueue(&nodequeue, next->left);
   if (next->right)
     enqueue(&nodequeue, next->right);
 }

}

void print(int n) {

 printf("%d ", n);

}

int main() {

 node n = tree(1,
               tree(2,
                    tree(4,
                         tree(7, 0, 0),
                         0),
                    tree(5, 0, 0)),
               tree(3,
                    tree(6,
                         tree(8, 0, 0),
                         tree(9, 0, 0)),
                    0));

 printf("preorder:    ");
 preorder(n, print);
 printf("\n");

 printf("inorder:     ");
 inorder(n, print);
 printf("\n");

 printf("postorder:   ");
 postorder(n, print);
 printf("\n");

 printf("level-order: ");
 levelorder(n, print);
 printf("\n");

 destroy_tree(n);

 return 0;

} </lang>

Java

Works with: Java version 1.5+

<lang java5>import java.util.LinkedList; public class TreeTraverse {

   private static class Node{
       public Node left;
       public Node right;
       public int data;
       
       public Node(int data){
           this.data = data;
       }

       public Node getLeft() {
           return left;
       }

       public void setLeft(Node left) {
           this.left = left;
       }

       public Node getRight() {
           return right;
       }

       public void setRight(Node right) {
           this.right = right;
       }
   }

   public static void preorder(Node n){
       System.out.print(n.data);
       if(n.getLeft()!= null){
           preorder(n.getLeft());
       }
       if(n.getRight()!= null){
           preorder(n.getRight());
       }
   }
   
   public static void inorder(Node n){
       if(n.getLeft()!= null){
           inorder(n.getLeft());
       }
       System.out.print(n.data);
       if(n.getRight()!= null){
           inorder(n.getRight());
       }
   }
   
   public static void postorder(Node n){
       if(n.getLeft()!= null){
           postorder(n.getLeft());
       }
       if(n.getRight()!= null){
           postorder(n.getRight());
       }
       System.out.print(n.data);
   }
   
   public static void levelorder(Node n) {
       LinkedList<Node> nodequeue = new LinkedList<Node>();
       nodequeue.addLast(n);
       while (!nodequeue.isEmpty()) {
           Node next = nodequeue.removeFirst();
           System.out.print(next.data);
           if (next.getLeft() != null) {
               nodequeue.addLast(next.getLeft());
           }
           if (next.getRight() != null) {
               nodequeue.addLast(next.getRight());
           }
       }
   }
   
   public static void main(String[] args){
       Node one = new Node(1);
       Node two = new Node(2);
       Node three = new Node(3);
       Node four = new Node(4);
       Node five = new Node(5);
       Node six = new Node(6);
       Node seven = new Node(7);
       Node eight = new Node(8);
       Node nine = new Node(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(one);
       System.out.println();
       inorder(one);
       System.out.println();
       postorder(one);
       System.out.println();
       levelorder(one);
   }

}</lang> Output: