Re: Binary Tree in java(Generic)

From:

"Jeff Higgins" <oohiggins@yahoo.com>

Newsgroups:

comp.lang.java.programmer

Date:

Wed, 20 Feb 2008 21:52:12 -0500

Message-ID:

<BH5vj.47$x72.9@newsfe05.lga>

Jeff Higgins wrote:

HelpMe wrote:

Please help me.I want to make a binary tree in java.I started but
couldnot accomplish.Can anyone help me to complete .Reply soon
please.My Program is:-

not a program, as it's posted.

Start here:

public class BinaryTree {

Object root;
BinaryTree right;
BinaryTree left;

}

Forget about interfaces, polymorphism, and generics
until you can produce a plain old data structure, you
can add the fancy stuff later.

Here's a link that was helpful to me.
<http://www.brpreiss.com/books/opus5/html/book.html>

import java.io.Serializable;

@SuppressWarnings("unchecked")
public class Node
implements Cloneable, Serializable, Comparable {

  private static final long serialVersionUID = 1L;

  private final Comparable data;

  public Node(Comparable data) {
    this.data = data; }

  public int height() {
    // TODO
    return -1; }

  public int depth() {
    // TODO
    return -1; }

  public Object getData() {
    return data; }

  public int compareTo(Object that) {
    if(that instanceof Node) {
      return this.data.compareTo(((Node)that).data);
    } throw new ClassCastException(); }

  @Override
  protected Object clone()
  throws CloneNotSupportedException {
    return super.clone(); }

  @Override
  public String toString() {
    return data.toString(); }
}

import java.io.Serializable;
import java.util.Iterator;

@SuppressWarnings("unused")
public class BinaryTree
implements Cloneable, Serializable {

  private static final long serialVersionUID = 1L;

  private Node root;
  private BinaryTree right;
  private BinaryTree left;

  public BinaryTree(){};

  public BinaryTree (Node root) {
    this.root = root; }

  public Node getRoot() {
    return root; }

  public int height() {
    // TODO
    return -1; }

  private class PreOrderIterator
  implements Iterator<Node> {

    @Override
    public boolean hasNext() {
      // TODO
      return false; }

    @Override
    public Node next() {
      // TODO
      return null; }

    @Override
    public void remove() {
      // TODO
    }
  }
}

public class TestTree {

  public static void main(String[] args) {

    Node root = new Node("root");
    BinaryTree tree = new BinaryTree(root);
    System.out.println(tree.getRoot()); }

}

import java.io.*;

interface Node {
         T getData();
         int getId();
  }

interface BinTree<T> {
         Node getLeft (Node n);
         Node getRight (Node n);
         Node[] leaves();
         Node parent(Node n);
         int numOfChildren(Node n);
}

class ArrayBinTree<T> implements BinTree<T> {
         class ArrayBinTreeNode<T> implements Node {
               T data;
               int id;
               T getData {return data;}
               int getId {return id;}

}

       ArrayBinTreeNode () { //default constructor
              id = 0;
              data = null;
         }
ArrayBinTree (int s){ //copy constructor
              id = s;
              data = null;
          }

Node[] tree;
int numOfNodes;
BinTree(int size) {
tree = new Node[size];
numOfNodes = 0;
}

Node getLeft(Node n) {
return tree [2*n.getId()+1];
}

Node getRight(Node n) {
return tree [2*n.getId()+2];
}