TreeArray.java

//Drevo s poljem
 
public class TreeArray extends Tree {
   static final int DEFAULT_MAX_NODES = 100 ;
   private TreeArrayNode nodes[] ;
   private int noNodes ;
  public TreeArray() {
    this(DEFAULT_MAX_NODES) ;
  }
  public TreeArray(int maxNodes) {
    nodes = new TreeArrayNode[maxNodes] ;
    makenull() ;
  }
  public TreeArray(TreeArray ta) {
    copy(ta) ;
  }
  public void makenull() {
    noNodes = 0 ;
  }
  public TreeNode root() {
    return nodes[0] ;
  }
  public TreeNode leftmostChild(TreeNode n) {
     if (((TreeArrayNode)n).noSons==0)
       return null ;
     else return nodes[((TreeArrayNode)n).index+1] ;
  }
  public void create(Object v, ListLinked subTrees) {
    nodes[0] = new TreeArrayNode(v, subTrees.len(), 0, -1) ;
    TreeArray child ;
    noNodes = 1 ;
    int idx = 1, i ;
    for (Object iter = subTrees.first() ; ! subTrees.overEnd(iter) ; iter=subTrees.next(iter)) {
        child = (TreeArray) subTrees.retrieve(iter) ;
        for (i=0 ; i < child.noNodes ; i++) {
          nodes[idx] = child.nodes[i] ;
          nodes[idx].index = idx ;
          if (i==0)
            nodes[idx].parent = 0 ;
          else
            nodes[idx].parent += noNodes ;
          idx++ ;
        }
        noNodes += child.noNodes ;
     }
  }
  private void copy(TreeArray ta) {
    nodes = new TreeArrayNode[ta.nodes.length] ;
    noNodes = ta.noNodes ;
    for (int i=0 ; i < noNodes ; i++) {
      nodes[i] = new TreeArrayNode() ;
      nodes[i].copy(ta.nodes[i]) ;
    }
  }
  private int skip(int nIdx) {
    int rootIdx = nIdx ;
    nIdx++ ;
    for (int i=0 ; i < nodes[rootIdx].noSons ; i++)
      nIdx = skip(nIdx) ;
    return nIdx ;
  }
  public TreeNode rightSibling(TreeNode n) {
    int right = ((TreeArrayNode)n).index ;
    right = skip(right) ;
    if (right >= noNodes)
      return  null ;
    else if (((TreeArrayNode)n).parent == nodes[right].parent)
      return nodes[right] ;
    else return null ;
  }
  public TreeNode parent(TreeNode n) {
    TreeArrayNode node = (TreeArrayNode) n ;
    if (node.parent == -1)
      return null ;
    else return nodes[node.parent] ;
  }
  public void writeTree() {
    if (noNodes > 0)
      indentWrite(0, 0) ;
  }
  public int indentWrite(int indent, int node) {
    int root = node, i ;
    node ++ ;
    for (i=0 ; i<indent; i++)
      System.out.print(" ");
    nodes[root].writeLabel() ;
    System.out.println();
    for (i=0 ; i< nodes[root].noSons ; i++)
      node=indentWrite(indent+1,node) ;
    return node ;
  }
 
  public static void main(String[] args) {
    TreeArray tree = new TreeArray();
    System.out.println("Testing "+tree.getClass() );
    ListLinked list = new ListLinked() ;
    TreeArray t1 = new TreeArray(), t2=new TreeArray();
    t1.create(new Integer(5), list);
    t2.create(new Integer(7), list) ;
    list.insert(t1);
    list.insert(t2);
    tree.create(new Integer(10), list);
    t1.copy(tree) ;
    t2.copy(tree);
    tree.create(new Integer(20), list);
    System.out.println("Preorder");
    tree.preorder(tree.root()) ;
    System.out.println("\nBy level");
    tree.printByLevel();
    System.out.println("\nIndented write");
    tree.writeTree();
  }
}