package ch.fhnw.claudemartin.algd2;

public class Baum {

  public static void main(String[] args) {
    int[] arr = new int[16];
    
    for (int x = 0; x<arr.length; x++)
      arr[x] = x+1;
    
    Node root = buildTree(arr, 0, arr.length-1);
    System.out.println("root="+root);
    System.out.println("trav:");
    traverse(root);
    
  }
  
  static Node buildTree(int[] values, int start, int end) {
    final int median = (start+end)/2;
    final Node newRoot = new Node(values[median]);
    if(median > start) 
      newRoot.left = buildTree(values, start, median-1);
    if(median < end) 
      newRoot.right = buildTree(values, median+1, end);
    return newRoot;
  }
  
  static class Node {
    public Node(Node n) {
      this.key = n.key;
      this.left = n.left;
      this.right = n.right;
    }
    public Node(int key) {
      this.key = key;
    }
    public Node(int key, Node left, Node right) {
      super();
      this.key = key;
      this.left = left;
      this.right = right;
    }
    public final int key;
    public Node left;
    public Node right;
    @Override
    public String toString() {
      return "k="+key+" l="+(left!=null?left.key:"null")+" r="+(right!=null?right.key:"null");
    }
  }
  
  static void traverse(Node node) {
    if(node != null) {
      traverse(node.left);
      visit(node);
      traverse(node.right);
    }
  }
  
  static void visit(Node node) {
    System.out.println(node.toString());
  }
}