Binary Tree Visualization

TreePlot.java

import com.trolltech.qt.core.QPoint;
import com.trolltech.qt.gui.QApplication;
import com.trolltech.qt.gui.QBrush;
import com.trolltech.qt.gui.QColor;
import com.trolltech.qt.gui.QFont;
import com.trolltech.qt.gui.QPaintEvent;
import com.trolltech.qt.gui.QPainter;
import com.trolltech.qt.gui.QWidget;

/**
 * A Node class representing each drawn node on the canvas. 
 */
class Node{
  Node left;
  Node right;
  Object data;
  //Positions of the node on the canvas.
  double x;
  double y;
  int depth;
}


class TreeBuilder{  
  public Node buildTree(String[] preOrder, String[] inOrder){
    assert(preOrder.length == inOrder.length);
    if(preOrder.length == 0){
      return null;
    }
    String rootData = preOrder[0];
    Node root       = new Node();
    root.data       = rootData;
    int rootIndex   = Array.<String>search(inOrder, rootData);
    
    String[] inLeft   = (String[]) Array.<String>splice(inOrder,0,rootIndex-1);
    String[] inRight  = (String[]) Array.<String>splice(inOrder, rootIndex+1, inOrder.length-1);
    String[] preLeft  = (String[]) Array.<String>splice(preOrder,1, inLeft.length);
    String[] preRight = (String[]) Array.<String>splice(preOrder,inLeft.length+1,preOrder.length-1);
    
    root.left = buildTree(preLeft, inLeft);
    root.right = buildTree(preRight, inRight);
    return root;
  }
}

/**
 * A simple visualizer for binary trees.
 */
public class TreePlot {

  private final static int WIDTH  = 600;
  private final static int HEIGHT = 450;
  private final static int VSPACE = 50;  
  
  
  private class MathCanvas extends QWidget {
    
    private Node root;
    
    public MathCanvas(Node root) {
      this.root = root;
      setWindowTitle("TreePlot");
      resize(WIDTH, HEIGHT);
      move(300, 100);
      show();
    }

    @Override
    protected void paintEvent(QPaintEvent event) {
      QPainter painter = new QPainter(this);
      painter.setBrush(QBrush.NoBrush);
      painter.setBrush(new QColor(25, 25, 25));
      painter.setFont(new QFont("Purisa", 15));      

      root.y = VSPACE;
      root.x = WIDTH/2.0;
      root.depth = 1;
      if(root != null){
        drawGraph(root, painter);
      }
    }
    
    private void drawGraph(Node node, QPainter painter){
      painter.drawText(new QPoint((int)node.x, (int)node.y), node.data.toString());      
      if(node.left != null){
        node.left.y = node.y + VSPACE;
        node.left.x = node.x - WIDTH/(1<<(node.depth+1));
        node.left.depth = node.depth + 1;
        drawGraph(node.left, painter);
      }
      
      if(node.right != null){
        node.right.y = node.y + VSPACE;
        node.right.x = node.x + WIDTH/(1<<(node.depth+1));
        node.right.depth = node.depth + 1;
        drawGraph(node.right, painter);
      }
      
    }
  }
  
  
  public void plot(String[] preOrder, String[] inOrder){
    QApplication.initialize(new String[0]);
    new MathCanvas(new TreeBuilder().buildTree(preOrder, inOrder));
    QApplication.exec();    
  }
    
  public static void main(String[] args) {
    TreePlot plotter = new TreePlot();
    String[] inOrder  = new String[]{"2","3","4","5","6","7","8"};
    String[] preOrder = new String[]{"5","3","2","4","7","6","8"};
    plotter.plot(preOrder, inOrder);
  }
}

 

  /**
   * Splices an array from begin_index to end_index, both inclusive. 
   */
  @SuppressWarnings("unchecked")
  public static<T> T[] splice(T[] array, int begin_index, int end_index){
    T[] sA = (T[]) java.lang.reflect.Array.newInstance(
        array.getClass().getComponentType(), end_index-begin_index+1);   
    for(int i = begin_index; i<= end_index; i++){
      sA[i-begin_index] = array[i];
    }    
    return sA;
  }