BinaryTree.java

Go to the documentation of this file.

package aud;
 
 
import aud.util.Graphvizable;
import aud.util.GraphvizDecorable;
import aud.util.GraphvizDecorator;
import aud.util.Sys;
 
public class BinaryTree<T>
  implements Graphvizable, GraphvizDecorable {
  BinaryTree<T>  parent_= null;
  BinaryTree<T>  left_  = null;
  BinaryTree<T>  right_ = null;
  T              data_  = null;
 
  //@<binarytree:ctor
  public BinaryTree(T data) {
    data_=data;
  }
  //@>binarytree:ctor
 
  //@<binarytree:ctor2
  public BinaryTree(T data,
    BinaryTree<T> left,BinaryTree<T> right) {
    this(data);
    left_=left; right_=right;
    if (left!=null)  left_.parent_ =this;
    if (right!=null) right_.parent_=this;
  }
  //@>binarytree:ctor2
 
  //@<binarytree:setleft
  public BinaryTree<T>
    setLeft(BinaryTree<T> tree) {
    BinaryTree<T> old=left_;
    left_=tree;
    if (tree!=null)
      tree.parent_=this;
    if (old!=null)
      old.parent_=null;
    return old;
  }
  //@>binarytree:setleft
  public BinaryTree<T> setRight(BinaryTree<T> tree) {
    BinaryTree<T> old=right_;
    right_=tree;
    if (tree!=null)
      tree.parent_=this;
    if (old!=null)
      old.parent_=null;
    return old;
  }
 
  public void setData(T data) { data_=data; }
  public T getData() { return data_; }
 
  public BinaryTree<T> getParent() { return parent_; }
  public BinaryTree<T> getLeft() { return left_; }
  public BinaryTree<T> getRight() { return right_; }
 
  //@<binarytree:isroot
  public boolean isRoot() { return getParent()==null; }
  //@>binarytree:isroot
  //@<binarytree:isleaf
  public boolean isLeaf() {
    return getLeft()==null && getRight()==null;
  }
  //@>binarytree:isleaf
 
  //@<binarytree:getroot
  public BinaryTree<T> getRoot() {
    BinaryTree<T> node=this;
    while (!node.isRoot())
      node=node.getParent();
    return node;
  }
  //@>binarytree:getroot
 
  public BinaryTreeTraversal<T>.Preorder preorder() {
    return new BinaryTreeTraversal<T>().preorder(this);
  }
  public BinaryTreeTraversal<T>.Inorder inorder() {
    return new BinaryTreeTraversal<T>().inorder(this);
  }
  public BinaryTreeTraversal<T>.Postorder postorder() {
    return new BinaryTreeTraversal<T>().postorder(this);
  }
  public BinaryTreeTraversal<T>.Levelorder levelorder() {
    return new BinaryTreeTraversal<T>().levelorder(this);
  }
 
  @Override public String toString() {
    return getData()!=null ? getData().toString() : "null";
  }
 
  @Override public GraphvizDecorator getDecorator() {
    return null;
  }
 
  @Override public String toDot() {
    String dot="graph BinaryTree {\n";
 
    GraphvizDecorator decorator=getDecorator();
    if (decorator!=null) {
      String d=decorator.getGlobalStyle();
      if (d!=null) dot+=" "+d+";\n";
      d=decorator.getGraphDecoration(this);
      if (d!=null) dot+=" graph ["+d+"];\n";
    }
 
    dot+=treeToDot();
 
    dot+="\n}\n";
    //System.out.println(dot);
    return dot;
  }
 
  private String dotRef() {
    return getData().toString()+"-"+hashCode();
  }
 
  /* get text representation of node for {@link #toDot}
     @return {@code getData().toString()} as default
   */
  protected String dotLabel() { return getData().toString(); }
 
  private String treeToDot() {
    // Currently no "root" or "same rank" tags. Do we require them?
 
    GraphvizDecorator decorator=getDecorator();
    String dot =" \""+dotRef()+"\" [label=\""+dotLabel()+"\",";
    dot+=(decorator!=null) ? decorator.getFullNodeDecoration(this) : "shape=circle";
    dot+="];\n";
 
    if (getLeft()!=null)
      dot+=getLeft().treeToDot();
    else
      dot+=dotLeaf("left");
 
    if (getRight()!=null)
      dot+=getRight().treeToDot();
    else
      dot+=dotLeaf("right");
 
    dot+="\n";
 
    if (!isRoot()) { // edge is identified by "lower" node
      dot+=" \""+getParent().dotRef()+"\" -- \""+
        dotRef()+"\" ["; // no edge labels currently
      dot+=(decorator!=null) ? decorator.getFullEdgeDecoration(this) : "";
      dot+="];\n";
    }
 
    return dot;
  }
 
  private String dotLeaf(String side) {
    String dummy="\""+dotRef()+"-"+side+"\"";
    String dot=" "+dummy+" [shape=point];\n";
    dot+=" \""+dotRef()+"\" -- "+dummy+" [];\n";
    return dot;
  }
 
  public String toText() {
    return toText(0);
  }
 
  private String toText(int level) {
    String text="";
    text+=Sys.indent(level)+"+- "+textLabel()+"\n";
 
    if (getLeft()==null && getRight()==null)
      return text;
 
    if (getLeft()!=null)
      text+=getLeft().toText(level+1);
    else
      text+=Sys.indent(level+1)+"+-\n";
 
    if (getRight()!=null)
      text+=getRight().toText(level+1);
    else
      text+=Sys.indent(level+1)+"+-\n";
 
    return text;
  }
 
  protected String textLabel() { return getData().toString(); }
 
  public String toTikZ() {
    return "\\"+toTikZ(0)+";\n";
  }
  protected String tikzNodeStyle() { return ""; }
  protected String toTikZ(int level) {
    String spaces=Sys.indent(level);
    String tex=spaces+"node "+tikzNodeStyle()+" {"+getData().toString()+"}\n";
    if (getLeft()!=null)
      tex+=spaces+" child[left] {\n"+getLeft().toTikZ(level+1)+spaces+" }\n";
    if (getRight()!=null)
      tex+=spaces+" child[right] {\n"+getRight().toTikZ(level+1)+spaces+" }\n";
 
    return tex;
  }
 
  public static void main(String[] args) {
    BinaryTree<String> a=new BinaryTree<String>("A");
    BinaryTree<String> b=new BinaryTree<String>("B");
    BinaryTree<String> c=new BinaryTree<String>("C");
    BinaryTree<String> d=new BinaryTree<String>("D");
 
    a.setLeft(b);
    a.setRight(c);
    c.setLeft(d);
 
    System.out.println(a);
    System.out.println(a.toText());
    System.out.println(a.toTikZ());
 
    System.out.println("preorder: "+a.preorder().toString());
    System.out.println("inorder: "+a.inorder().toString());
    System.out.println("postorder: "+a.postorder().toString());
    System.out.println("level-order: "+a.levelorder().toString());
 
    //System.out.println(a.toDot());
  }
}