A link list based binary tree in java

Discussion in 'Java' started by Andrew Marcus, Mar 19, 2008.

  1. I don't know how far it would help me.
    I tried to make a link list based binary tree following the book "data
    structures and algorithms in java" By Michael T GoodRich and
    Tamassia.I did all
    but I wanted to implement a function to determine whether a particular
    node exists or not.All I want to implement a function boolean
    exists(node n).Can anyone help??My program is as follows:-

    import java.io.*;

    interface Node {
    Object getData();
    int getID();
    }

    class TreeEmptyException extends Exception {
    TreeEmptyException(String message) {
    super(message);
    }

    }

    class LinkBinTree {
    BinNode root;
    int size;
    LinkBinTree(Object O) {
    root = new BinNode(0);
    }

    class BinNode implements Node {
    int id;
    BinNode left;
    BinNode right;
    Object data;
    BinNode(int iden) {
    id = iden;
    left = null;
    right = null;
    data = null;
    }
    BinNode(Object O) {
    id = 0;
    left = null;
    right = null;
    data = null;
    }
    public Object getData() {return data;}
    public int getID() { return id;}

    void addLeft(Object obj) {
    BinNode b = new BinNode(obj);
    left = b;
    }

    void addRight(Object obj) {
    BinNode r = new BinNode(obj);
    right = r;
    }

    BinNode addLeft(Node n,Object O) throws TreeEmptyException
    {
    if(!exists(n)) throw new TreeEmptyException("Tree doesn't
    exists");
    return n.addLeft(O);

    }

    BinNode addRight(Node n,Object O) throws TreeEmptyException{
    if(!exists(n)) throw new TreeEmptyException("Tree doesn't
    exists");
    return n.addRight(O);

    }

    void preOrder(Node n) {
    LinkQueueApp<Integer> q =new LinkQueueApp<Integer>();
    int p=n.getID();
    q.enqueue(p);
    while(!q.isEmpty()) {
    p =q.dequeue();
    System.out.println("The pre-order is : "
    +n.getData());
    for(int i=p;(i==p+1) || (i==p+2)&&i<=size;i++)
    q.enqueue(i);
    }

    }

    void boolean exists(Node n) {
    if(Node == root) return;
    else {
    if(Node
    Andrew Marcus, Mar 19, 2008
    #1
    1. Advertising

  2. Andrew Marcus

    Lord Zoltar Guest

    Andrew Marcus wrote:
    > I don't know how far it would help me.
    > I tried to make a link list based binary tree following the book "data
    > structures and algorithms in java" By Michael T GoodRich and
    > Tamassia.I did all
    > but I wanted to implement a function to determine whether a particular
    > node exists or not.All I want to implement a function boolean
    > exists(node n).Can anyone help??My program is as follows:-
    >


    You'd have to implement a find method, and wrap it in the exists
    method:
    exists(node n)
    {
    return (null==find(n));
    }

    I am not familiar with this book. Does it not cover how to search the
    tree after it's been created?
    Lord Zoltar, Mar 19, 2008
    #2
    1. Advertising

  3. On Wed, 19 Mar 2008 06:17:58 -0700 (PDT), Andrew Marcus wrote:
    > I wanted to implement a function to determine whether a particular
    > node exists or not.All I want to implement a function boolean
    > exists(node n).Can anyone help?


    Noting that each subtree is itself a tree, a recursive solution works
    like this:

    n is in the tree iff:
    n is the root node of the tree,
    or n is in the left subtree,
    or n is in the right subtree.

    /gordon

    --
    Gordon Beaton, Mar 19, 2008
    #3
  4. Andrew Marcus writes:

    > I don't know how far it would help me.


    Depends on what "it" is. If it is what I think it is, it would remove
    a totally unnecessary hurdle from your way.

    > I tried to make a link list based binary tree following the book "data
    > structures and algorithms in java" By Michael T GoodRich and
    > Tamassia.I did all
    > but I wanted to implement a function to determine whether a particular
    > node exists or not.All I want to implement a function boolean
    > exists(node n).Can anyone help??My program is as follows:-


    I suggest this working order:
    (1) Make up your mind about the constructors: if they are _meant_ to
    ignore their arguments, at _least_ rename the arguments so that
    this intention is absolutely clear to the reader, or better,
    remove the arguments altogether. Are nodes meant to contain both
    "id" and "data"? (Does a tree of zero nodes make sense to you?
    Is the tree meant to be ordered somehow? Binary trees often are.)
    (2) Make the program complete and compilable, compile it and study
    the error messages and act accordingly until the program compiles.
    You may want to remove parts like the preorder method for now;
    put them back when you can cope with the simpler parts.
    (3) Add a _short_ and _simple_ main method to test it. Make it build
    a tree with a single node. Compile and run. Make it build a tree
    with _two_ nodes. Compile and run. Write a method that counts the
    nodes and make the main method print its value. Compile and run.

    > import java.io.*;


    Not used.

    > interface Node {
    > Object getData();
    > int getID();
    > }


    > class TreeEmptyException extends Exception {
    > TreeEmptyException(String message) {
    > super(message);
    > }
    >
    > }


    > class LinkBinTree {
    > BinNode root;
    > int size;
    > LinkBinTree(Object O) {
    > root = new BinNode(0);
    > }


    This constructor ignores its argument. If that is intentional, at
    _least_ rename to argument; it could be "obj", it could be "_", it
    could be "ignored", it could be _anything_ _except_ "O"; even "o"
    might be tolerable. Preferably make it just LinkBinTree(), if you
    don't use the argument at all.

    If that 0 (zero) is meant to be O (oh), replace _both_ with something
    sensible. And change the font you use when you write code so that you
    can see the difference.

    (You should indent the all following to make it clearer that it is
    inside the LinkBinTree class.)

    > class BinNode implements Node {
    > int id;
    > BinNode left;
    > BinNode right;
    > Object data;
    > BinNode(int iden) {
    > id = iden;
    > left = null;
    > right = null;
    > data = null;
    > }
    > BinNode(Object O) {
    > id = 0;
    > left = null;
    > right = null;
    > data = null;
    > }


    I wonder if you really want two different constructors, however.
    Maybe you want one that takes two arguments, id and data? Just
    wondering. In the code you show, data is always null.

    > public Object getData() {return data;}
    > public int getID() { return id;}
    >
    > void addLeft(Object obj) {
    > BinNode b = new BinNode(obj);
    > left = b;
    > }
    >
    > void addRight(Object obj) {
    > BinNode r = new BinNode(obj);
    > right = r;
    > }


    These don't really _add_ to this node, they _replace_ whatever is
    there. Might consider checking that the left or right node is missing
    before the assignment, or rename the methods. At the moment, this is
    minor. Your tree, however, has a field named "size" that is nowhere
    maintained. I would remove that field for now.

    > BinNode addLeft(Node n,Object O) throws TreeEmptyException
    > {
    > if(!exists(n)) throw new TreeEmptyException("Tree doesn't
    > exists");
    > return n.addLeft(O);
    >
    > }
    >
    > BinNode addRight(Node n,Object O) throws TreeEmptyException{
    > if(!exists(n)) throw new TreeEmptyException("Tree doesn't
    > exists");
    > return n.addRight(O);
    >
    > }


    I'm not sure what the existence check is for. The methods have the
    Node right there, so in that sense it certainly exists. Zoltar's
    advice of implementing a "find" method is sound. Maybe you want here a
    method that finds a Node with a given "id"?

    (Those O's get ignored; see above.)

    When you make this code to compile, you will find out that there is no
    addLeft(Object) or addRight(Object) in the interface Node. Do you see
    the two obvious ways to fix this? Your choice.

    > void preOrder(Node n) {
    > LinkQueueApp<Integer> q =new LinkQueueApp<Integer>();
    > int p=n.getID();
    > q.enqueue(p);
    > while(!q.isEmpty()) {
    > p =q.dequeue();
    > System.out.println("The pre-order is : "
    > +n.getData());
    > for(int i=p;(i==p+1) || (i==p+2)&&i<=size;i++)
    > q.enqueue(i);
    > }
    >
    > }


    I would remove this until simpler stuff works. And then I would use
    this as an opportunity to learn recursive programming: count nodes,
    print nodes in different orders without any auxiliary data structure.
    Binary trees are great for that.

    > void boolean exists(Node n) {
    > if(Node == root) return;
    > else {
    > if(Node


    Your code ends here. This last piece is very wrong -- there is no such
    type as "void boolean", and other code expects this to return a
    boolean, not just to return, and comparing a type, Node, to an object
    is just nonsense -- but it may be best to simply throw it away and
    write that "find" instead.

    First make it complete and compilable. Then write a simple main
    method, and do make it simple at first. Compile and run. Add pieces
    and keep it compilable and runnable and comprehensible. You will
    learn, and you may find that you enjoy the experience.
    Jussi Piitulainen, Mar 19, 2008
    #4
    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,110
  2. sharan
    Replies:
    4
    Views:
    689
    CBFalconer
    Oct 30, 2007
  3. sharan
    Replies:
    2
    Views:
    830
    SM Ryan
    Oct 31, 2007
  4. sharan
    Replies:
    1
    Views:
    689
    CBFalconer
    Oct 30, 2007
  5. Bogdan

    Binary tree search vs Binary search

    Bogdan, Oct 18, 2010, in forum: C Programming
    Replies:
    22
    Views:
    3,068
    Michael Angelo Ravera
    Oct 21, 2010
Loading...

Share This Page