H
HelpMe
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.
some sorts of idea??I shall be very grateful to him.
H
HelpMe
You can assume the binary tree to be a proper one.
J
Jeff Higgins
HelpMe said:
Ok.
Go ahead.
You're welcome.
You can assume this idea is the proper one.
M
Mark Space
HelpMe said:
I only know about improper trees. Sorry.
J
Jeff Higgins
L
Lew
Jeff said:
<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>
M
Mark Space
Jeff said:
Ah, so it's an actual thing. I guess I did only know about improper
trees....
R
Roedy Green
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
A
Arved Sandstrom
HelpMe said:
Data Structures and Algorithms in Java, Robert Lafore, SAMS Publishing,
2002.
AHS