BinaryTree

Discussion in 'Java' started by HelpMe, Mar 9, 2008.

  1. HelpMe

    HelpMe Guest

    I want to implement a link-list based binary tree.Can anyone give me
    some sorts of idea??I shall be very grateful to him.
    HelpMe, Mar 9, 2008
    #1
    1. Advertising

  2. HelpMe

    HelpMe Guest

    On Mar 9, 10:55 pm, HelpMe <> wrote:
    > I want to implement a link-list based binary tree.Can anyone give me
    > some sorts of idea??I shall be very grateful to him.

    You can assume the binary tree to be a proper one.
    HelpMe, Mar 9, 2008
    #2
    1. Advertising

  3. HelpMe

    Jeff Higgins Guest

    HelpMe wrote:
    > On Mar 9, 10:55 pm, HelpMe <> wrote:
    >> I want to implement a link-list based binary tree.Can anyone give me
    >> some sorts of idea??I shall be very grateful to him.

    > You can assume the binary tree to be a proper one.


    Ok.
    Go ahead.
    You're welcome.
    You can assume this idea is the proper one.
    Jeff Higgins, Mar 9, 2008
    #3
  4. HelpMe

    Mark Space Guest

    HelpMe wrote:
    > On Mar 9, 10:55 pm, HelpMe <> wrote:
    >> I want to implement a link-list based binary tree.Can anyone give me
    >> some sorts of idea??I shall be very grateful to him.

    > You can assume the binary tree to be a proper one.


    I only know about improper trees. Sorry.
    Mark Space, Mar 9, 2008
    #4
  5. HelpMe

    Jeff Higgins Guest

    Mark Space wrote:
    > HelpMe wrote:
    >> On Mar 9, 10:55 pm, HelpMe <> wrote:
    >>> I want to implement a link-list based binary tree.Can anyone give me
    >>> some sorts of idea??I shall be very grateful to him.

    >> You can assume the binary tree to be a proper one.

    >
    > I only know about improper trees. Sorry.


    <http://www.nist.gov/dads/HTML/properBinaryTree.html>
    Jeff Higgins, Mar 9, 2008
    #5
  6. HelpMe

    Lew Guest

    Jeff Higgins wrote:
    > HelpMe wrote:
    >> On Mar 9, 10:55 pm, HelpMe <> wrote:
    >>> I want to implement a link-list based binary tree.Can anyone give me
    >>> some sorts of idea??I shall be very grateful to him.

    >> You can assume the binary tree to be a proper one.

    >
    > Ok.
    > Go ahead.
    > You're welcome.
    > You can assume this idea is the proper one.


    <http://en.wikipedia.org/wiki/Binary_tree>
    <http://en.wikipedia.org/wiki/Binary_search_tree>

    Within the tree, each node has a value and a link set, since you say you want
    to be link-based. I don't really think "linked list" applies; you are talking
    about a "linked tree".

    Here's an example implementation that permits only one node with a given value
    in a tree:

    <sscce>
    package testit;
    public class Node <T extends Comparable <? super T>>
    implements Comparable <Node <T>>
    {
    private final T value;
    private Node <T> left, right; // the links

    public Node( final T v )
    {
    this.value = v;
    }

    public final T getValue()
    { return value; }

    public final Node <T> getLeft()
    { return left; }
    public final void setLeft( Node <T> v )
    { left = v; }

    public final Node <T> getRight()
    { return right; }
    public final void setRight( Node <T> v )
    { right = v; }

    public int compareTo( Node <T> o )
    {
    return (this == o? 0
    : o == null? 1
    : value == null? (o.value == null? 0 : -1)
    : o.value == null? 1 /* guarantee symmetry */
    : value.compareTo( o.value ));
    }

    @Override public boolean equals( Object o )
    {
    try
    {
    return equals( getClass().cast(o) );
    }
    catch ( ClassCastException exc )
    {
    return false;
    }
    }

    public boolean equals( Node <T> o )
    {
    return (this == o || (o != null
    && (value == null? o.value == null : value.equals( o.value ))
    ));
    }

    @Override public int hashCode()
    {
    return (value == null? 0 : value.hashCode());
    }

    @Override public String toString()
    {
    return value.toString();
    }
    }
    </sscce>

    --
    Lew
    Lew, Mar 9, 2008
    #6
  7. HelpMe

    Mark Space Guest

    Jeff Higgins wrote:
    > Mark Space wrote:
    >> HelpMe wrote:
    >>> On Mar 9, 10:55 pm, HelpMe <> wrote:
    >>>> I want to implement a link-list based binary tree.Can anyone give me
    >>>> some sorts of idea??I shall be very grateful to him.
    >>> You can assume the binary tree to be a proper one.

    >> I only know about improper trees. Sorry.

    >
    > <http://www.nist.gov/dads/HTML/properBinaryTree.html>
    >
    >


    Ah, so it's an actual thing. I guess I did only know about improper
    trees.... ;)
    Mark Space, Mar 10, 2008
    #7
  8. HelpMe

    Roedy Green Guest

    On Sun, 9 Mar 2008 10:55:02 -0700 (PDT), HelpMe
    <> wrote, quoted or indirectly quoted someone
    who said :

    >I want to implement a link-list based binary tree.Can anyone give me
    >some sorts of idea??I shall be very grateful to him.


    have a look at the source code for LinkedList either Sun's or mine to
    get the basic idea.

    See http://mindprod.com/products2.html#LINKEDLIST
    --

    Roedy Green Canadian Mind Products
    The Java Glossary
    http://mindprod.com
    Roedy Green, Mar 10, 2008
    #8
  9. "HelpMe" <> wrote in message
    news:...
    >I want to implement a link-list based binary tree.Can anyone give me
    > some sorts of idea??I shall be very grateful to him.


    Data Structures and Algorithms in Java, Robert Lafore, SAMS Publishing,
    2002.

    AHS
    Arved Sandstrom, Mar 10, 2008
    #9
    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. neapolisratio

    binarytree

    neapolisratio, Dec 21, 2006, in forum: Java
    Replies:
    3
    Views:
    432
    Patricia Shanahan
    Dec 22, 2006
Loading...

Share This Page