Binary Tree in java(Generic)

Discussion in 'Java' started by HelpMe, Feb 20, 2008.

  1. HelpMe

    HelpMe Guest

    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:-

    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];
    }
    HelpMe, Feb 20, 2008
    #1
    1. Advertising

  2. HelpMe

    Jeff Higgins Guest

    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.*;
    >
    > 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];
    > }
    Jeff Higgins, Feb 20, 2008
    #2
    1. Advertising

  3. HelpMe

    Jeff Higgins Guest

    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];
    >> }

    >
    >
    Jeff Higgins, Feb 21, 2008
    #3
  4. HelpMe

    Lew Guest

    Jeff Higgins wrote:
    > @SuppressWarnings("unchecked")
    > public class Node
    > implements Cloneable, Serializable, Comparable {


    It would be fun to genericize this such that the "unchecked" warnings need not
    be suppressed.

    --
    Lew
    The wolf ate the moon tonight.
    Lew, Feb 21, 2008
    #4
  5. HelpMe

    Jeff Higgins Guest

    Lew wrote:
    > Jeff Higgins wrote:
    >> @SuppressWarnings("unchecked")
    >> public class Node
    >> implements Cloneable, Serializable, Comparable {

    >
    > It would be fun to genericize this such that the "unchecked" warnings need
    > not be suppressed.
    >


    How do you do that?

    JH
    Jeff Higgins, Feb 21, 2008
    #5
  6. HelpMe

    Lord Zoltar Guest

    On Feb 20, 1:33 pm, 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:-


    The Java API has a TreeMap class. Would that suffice?
    Lord Zoltar, Feb 21, 2008
    #6
  7. HelpMe

    Lew Guest

    Jeff Higgins wrote:
    > Lew wrote:
    >> Jeff Higgins wrote:
    >>> @SuppressWarnings("unchecked")
    >>> public class Node
    >>> implements Cloneable, Serializable, Comparable {

    >> It would be fun to genericize this such that the "unchecked" warnings need
    >> not be suppressed.
    >>

    >
    > How do you do that?


    public class Node implements Cloneable, Serializable,
    Comparable <Node>
    {
    ....

    --
    Lew
    Lew, Feb 21, 2008
    #7
  8. HelpMe

    voorth Guest

    On Feb 21, 3:25 pm, Lord Zoltar <> wrote:
    > On Feb 20, 1:33 pm, 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:-

    >
    > The Java API has a TreeMap class. Would that suffice?


    I'm afraid not. The TreeMap is an implementation of SortedMap that
    stores its keys in a Red-Black tree. It is not a tree implementation.
    voorth, Feb 21, 2008
    #8
  9. HelpMe

    Lord Zoltar Guest


    > > The Java API has a TreeMap class. Would that suffice?

    >
    > I'm afraid not. The TreeMap is an implementation of SortedMap that
    > stores its keys in a Red-Black tree. It is not a tree implementation.


    I'm pretty sure TreeMap is a tree implementation, as it implements a
    Red-Black tree (and Red-Black trees are a form of binary search tree).
    Do you need the actual source code for an implementation of a tree and
    not just an API to use a tree implementation?
    Lord Zoltar, Feb 21, 2008
    #9
  10. HelpMe

    Jeff Higgins Guest

    Lew wrote:
    > Jeff Higgins wrote:
    >> Lew wrote:
    >>> Jeff Higgins wrote:
    >>>> @SuppressWarnings("unchecked")
    >>>> public class Node
    >>>> implements Cloneable, Serializable, Comparable {
    >>> It would be fun to genericize this such that the "unchecked" warnings
    >>> need not be suppressed.
    >>>

    >>
    >> How do you do that?

    >
    > public class Node implements Cloneable, Serializable,
    > Comparable <Node>
    > {
    > ...


    Oh! OK that's kinda neat, thanks.

    import java.io.Serializable;

    public class Node<T extends Comparable<T>>
    implements Cloneable, Serializable, Comparable<Node<T>> {

    private static final long serialVersionUID = 1L;

    private final T data;

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

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

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

    public T getData() {
    return data; }

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

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

    @Override
    public int compareTo(Node<T> that) {
    return this.data.compareTo(that.data); }
    }


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

    @SuppressWarnings("unused")
    public class BinaryTree<T extends Comparable<T>>
    implements Cloneable, Serializable {

    private static final long serialVersionUID = 1L;

    private Node<T> root;
    private BinaryTree<T> right;
    private BinaryTree<T> left;

    public BinaryTree() {};

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

    public Node<T> getRoot() {
    return root; }

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

    private class PreOrderIterator
    implements Iterator<Node<T>> {

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

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

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


    public class TestTree {

    @SuppressWarnings("boxing")
    public static void main(String[] args) {

    Node<Integer> root =
    new Node<Integer>(Integer.MAX_VALUE);
    BinaryTree<Integer> tree =
    new BinaryTree<Integer>(root);
    System.out.println(tree.getRoot());
    }
    }
    Jeff Higgins, Feb 21, 2008
    #10
  11. HelpMe

    Jeff Higgins Guest

    Jeff Higgins wrote:
    >
    >
    > @SuppressWarnings("unused")
    > public class BinaryTree<T extends Comparable<T>>
    > implements Cloneable, Serializable {
    >
    > private static final long serialVersionUID = 1L;
    >
    > private Node<T> root;


    Oops!

    > private BinaryTree<T> right;
    > private BinaryTree<T> left;
    >

    Should be:
    private BinaryTree<Node<T>> right;
    private BinaryTree<Node<T>> left;

    Oops!

    > public BinaryTree() {};
    >
    > public BinaryTree(Node<T> root) {
    > this.root = root; }
    >
    > public Node<T> getRoot() {
    > return root; }
    >
    > public int height() {
    > // TODO
    > return -1; }
    >
    > private class PreOrderIterator
    > implements Iterator<Node<T>> {
    >
    > @Override
    > public boolean hasNext() {
    > // TODO
    > return false; }
    >
    > @Override
    > public Node<T> next() {
    > // TODO
    > return null; }
    >
    > @Override
    > public void remove() {
    > // TODO
    > }
    > }
    > }
    >
    >
    Jeff Higgins, Feb 21, 2008
    #11
  12. HelpMe

    Jeff Higgins Guest

    Jeff Higgins wrote:
    > Jeff Higgins wrote:
    >>
    >>

    >
    > Oops!
    >
    >> private BinaryTree<T> right;
    >> private BinaryTree<T> left;
    >>

    > Should be:


    No it shouldn't. Should be just as I first put.

    HelpMe, in response to your email request:

    Hey! what is the output.It gives like 2147483647.What output is this?
    Where is 5 and zero.

    There seems to be a 9 missing also. You'll have to blame that on the
    powers of 2, and who ever defined Integer.MAX_VALUE.
    See class TreeTest. Oops!

    > private BinaryTree<Node<T>> right;
    > private BinaryTree<Node<T>> left;
    >
    > Oops!
    >
    Jeff Higgins, Feb 21, 2008
    #12
  13. HelpMe

    HelpMe Guest

    On Feb 22, 3:18 am, "Jeff Higgins" <> wrote:
    > Jeff Higgins wrote:
    > > Jeff Higgins wrote:

    >
    > > Oops!

    >
    > >> private BinaryTree<T> right;
    > >> private BinaryTree<T> left;

    >
    > > Should be:

    >
    > No it shouldn't. Should be just as I first put.
    >
    > HelpMe, in response to your email request:
    >
    > Hey! what is the output.It gives like 2147483647.What output is this?
    > Where is 5 and zero.
    >
    > There seems to be a 9 missing also. You'll have to blame that on the
    > powers of 2, and who ever defined Integer.MAX_VALUE.
    > See class TreeTest. Oops!
    >
    > > private BinaryTree<Node<T>> right;
    > > private BinaryTree<Node<T>> left;

    >
    > > Oops!


    Sir,I want to implement it using Array or Link,I mean either a array
    based binary tree or link based.How should I proceed.
    HelpMe, Feb 22, 2008
    #13
  14. HelpMe

    Lew Guest

    HelpMe wrote:
    > On Feb 22, 3:18 am, "Jeff Higgins" <> wrote:
    >> Jeff Higgins wrote:
    >>> Jeff Higgins wrote:
    >>> Oops!
    >>>> private BinaryTree<T> right;
    >>>> private BinaryTree<T> left;
    >>> Should be:

    >> No it shouldn't. Should be just as I first put.
    >>
    >> HelpMe, in response to your email request:
    >>
    >> Hey! what is the output.It gives like 2147483647.What output is this?
    >> Where is 5 and zero.
    >>
    >> There seems to be a 9 missing also. You'll have to blame that on the
    >> powers of 2, and who ever defined Integer.MAX_VALUE.
    >> See class TreeTest. Oops!
    >>
    >>> private BinaryTree<Node<T>> right;
    >>> private BinaryTree<Node<T>> left;
    >>> Oops!

    >
    > Sir,I want to implement it using Array or Link,I mean either a array
    > based binary tree or link based.How should I proceed.


    Jeff Higgins's approach is the link-based one. Those instance variables
    'right' and 'left' are the links.

    --
    Lew
    Lew, Feb 22, 2008
    #14
  15. HelpMe

    Jeff Higgins Guest

    Lew wrote:
    >>
    >> Sir,I want to implement it using Array or Link,I mean either a array
    >> based binary tree or link based.How should I proceed.

    >
    > Jeff Higgins's approach is the link-based one. Those instance variables
    > 'right' and 'left' are the links.
    >


    Just to expand a little on Lew's response.
    (And to also note that the preliminary outline I've proposed
    upthread hasn't yet any provisions for persistance of the tree.)
    BTW, Lew. Thanks for the help with the generics angle.

    According to the Wikipedia article:
    Binary tree
    <http://en.wikipedia.org/wiki/Binary_tree>

    Binary trees can also be stored as an implicit data structure in arrays,
    and if the tree is a complete binary tree, this method wastes no space.
    In this compact arrangement, if a node has an index i, its children are
    found at indices 2i + 1 and 2i + 2, while its parent (if any) is found at
    index [(i - 1)/2] (assuming the root has index zero).

    So, if you wish to use an array based storage mechanism you could
    add an integer field called index to the Node class,
    and an ArrayList field to the Binary tree class
    and change the compareTo method to compare index.
    Jeff Higgins, Feb 22, 2008
    #15
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,094
  2. Bonj

    high-end generic binary tree

    Bonj, Mar 17, 2005, in forum: C Programming
    Replies:
    0
    Views:
    377
  3. sharan
    Replies:
    4
    Views:
    675
    CBFalconer
    Oct 30, 2007
  4. sharan
    Replies:
    2
    Views:
    822
    SM Ryan
    Oct 31, 2007
  5. sharan
    Replies:
    1
    Views:
    679
    CBFalconer
    Oct 30, 2007
Loading...

Share This Page