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 - 09 Mar 2008 18:56 GMT
> 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.
Jeff Higgins - 09 Mar 2008 20:28 GMT
>> 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.
Lew - 09 Mar 2008 21:55 GMT
>>> 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.
[quoted text clipped - 4 lines]
> 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>

Signature
Lew
Mark Space - 09 Mar 2008 21:04 GMT
>> 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.
Jeff Higgins - 09 Mar 2008 21:13 GMT
>>> 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>
Mark Space - 10 Mar 2008 01:52 GMT
>>>> 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.... ;)
Roedy Green - 10 Mar 2008 04:51 GMT
On Sun, 9 Mar 2008 10:55:02 -0700 (PDT), HelpMe
<ShahilAkhtar@gmail.com> 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
Arved Sandstrom - 10 Mar 2008 06:39 GMT
>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