binarysearchtree.html

学习JAVA的很好的JAVA包和文档包

<TABLE BORDER="1" CELLPADDING="3" CELLSPACING="0" WIDTH="100%">
<TR BGCOLOR="#CCCCFF" CLASS="TableHeadingColor">
<TD COLSPAN=1><FONT SIZE="+2">
<B>Field Detail</B></FONT></TD>
</TR>
</TABLE>

<A NAME="root"><!-- --></A><H3>
root</H3>
<PRE>
protected <A HREF="../structure/BinaryTree.html">BinaryTree</A> <B>root</B></PRE>
<DL>
<DD>A reference to the root of the tree</DL>
<HR>

<A NAME="count"><!-- --></A><H3>
count</H3>
<PRE>
protected int <B>count</B></PRE>
<DL>
<DD>The number of nodes in the tree</DL>
<HR>

<A NAME="ordering"><!-- --></A><H3>
ordering</H3>
<PRE>
protected <A HREF="http://java.sun.com/j2se/1.3/docs/api/java/util/Comparator.html">Comparator</A> <B>ordering</B></PRE>
<DL>
<DD>The ordering used on this search tree.</DL>

<!-- ========= CONSTRUCTOR DETAIL ======== -->

<A NAME="constructor_detail"><!-- --></A>
<TABLE BORDER="1" CELLPADDING="3" CELLSPACING="0" WIDTH="100%">
<TR BGCOLOR="#CCCCFF" CLASS="TableHeadingColor">
<TD COLSPAN=1><FONT SIZE="+2">
<B>Constructor Detail</B></FONT></TD>
</TR>
</TABLE>

<A NAME="BinarySearchTree()"><!-- --></A><H3>
BinarySearchTree</H3>
<PRE>
public <B>BinarySearchTree</B>()</PRE>
<DL>
<DD>Constructs a binary search tree with no data</DL>
<HR>

<A NAME="BinarySearchTree(java.util.Comparator)"><!-- --></A><H3>
BinarySearchTree</H3>
<PRE>
public <B>BinarySearchTree</B>(<A HREF="http://java.sun.com/j2se/1.3/docs/api/java/util/Comparator.html">Comparator</A>&nbsp;alternateOrder)</PRE>
<DL>
<DD>Constructs a binary search tree with no data</DL>

<!-- ============ METHOD DETAIL ========== -->

<A NAME="method_detail"><!-- --></A>
<TABLE BORDER="1" CELLPADDING="3" CELLSPACING="0" WIDTH="100%">
<TR BGCOLOR="#CCCCFF" CLASS="TableHeadingColor">
<TD COLSPAN=1><FONT SIZE="+2">
<B>Method Detail</B></FONT></TD>
</TR>
</TABLE>

<A NAME="isEmpty()"><!-- --></A><H3>
isEmpty</H3>
<PRE>
public boolean <B>isEmpty</B>()</PRE>
<DL>
<DD>Checks for an empty binary search tree<DD><DL>
<DT><B>Specified by: </B><DD><CODE><A HREF="../structure/Structure.html#isEmpty()">isEmpty</A></CODE> in interface <CODE><A HREF="../structure/Structure.html">Structure</A></CODE><DT><B>Overrides:</B><DD><CODE><A HREF="../structure/AbstractStructure.html#isEmpty()">isEmpty</A></CODE> in class <CODE><A HREF="../structure/AbstractStructure.html">AbstractStructure</A></CODE></DL>
</DD>
<DD><DL>
<DT><B>Postcondition:</B><DD>Returns true iff the binary search tree is empty<DT><B>Returns:</B><DD>True iff the tree contains no data</DL>
</DD>
</DL>
<HR>

<A NAME="clear()"><!-- --></A><H3>
clear</H3>
<PRE>
public void <B>clear</B>()</PRE>
<DL>
<DD>Removes all data from the binary search tree<DD><DL>
<DT><B>Specified by: </B><DD><CODE><A HREF="../structure/Structure.html#clear()">clear</A></CODE> in interface <CODE><A HREF="../structure/Structure.html">Structure</A></CODE></DL>
</DD>
<DD><DL>
<DT><B>Postcondition:</B><DD>Removes all elements from binary search tree</DL>
</DD>
</DL>
<HR>

<A NAME="size()"><!-- --></A><H3>
size</H3>
<PRE>
public int <B>size</B>()</PRE>
<DL>
<DD>Determines the number of data values within the tree<DD><DL>
<DT><B>Specified by: </B><DD><CODE><A HREF="../structure/Structure.html#size()">size</A></CODE> in interface <CODE><A HREF="../structure/Structure.html">Structure</A></CODE></DL>
</DD>
<DD><DL>
<DT><B>Postcondition:</B><DD>Returns the number of elements in binary search tree<DT><B>Returns:</B><DD>The number of nodes in the binary search tree</DL>
</DD>
</DL>
<HR>

<A NAME="locate(structure.BinaryTree, java.lang.Object)"><!-- --></A><H3>
locate</H3>
<PRE>
protected <A HREF="../structure/BinaryTree.html">BinaryTree</A> <B>locate</B>(<A HREF="../structure/BinaryTree.html">BinaryTree</A>&nbsp;root,
                            <A HREF="http://java.sun.com/j2se/1.3/docs/api/java/lang/Object.html">Object</A>&nbsp;value)</PRE>
<DL>
<DD><DL>
</DL>
</DD>
<DD><DL>
<DT><B>Precondition:</B><DD>root and value are non-null<DT><B>Postcondition:</B><DD>returned: 1 - existing tree node with the desired value, or
                 2 - the node to which value should be added</DL>
</DD>
</DL>
<HR>

<A NAME="predecessor(structure.BinaryTree)"><!-- --></A><H3>
predecessor</H3>
<PRE>
protected <A HREF="../structure/BinaryTree.html">BinaryTree</A> <B>predecessor</B>(<A HREF="../structure/BinaryTree.html">BinaryTree</A>&nbsp;root)</PRE>
<DL>
<DD><DL>
</DL>
</DD>
</DL>
<HR>

<A NAME="successor(structure.BinaryTree)"><!-- --></A><H3>
successor</H3>
<PRE>
protected <A HREF="../structure/BinaryTree.html">BinaryTree</A> <B>successor</B>(<A HREF="../structure/BinaryTree.html">BinaryTree</A>&nbsp;root)</PRE>
<DL>
<DD><DL>
</DL>
</DD>
</DL>
<HR>

<A NAME="add(java.lang.Object)"><!-- --></A><H3>
add</H3>
<PRE>
public void <B>add</B>(<A HREF="http://java.sun.com/j2se/1.3/docs/api/java/lang/Object.html">Object</A>&nbsp;value)</PRE>
<DL>
<DD>Add a (possibly duplicate) value to binary search tree<DD><DL>
<DT><B>Specified by: </B><DD><CODE><A HREF="../structure/Structure.html#add(java.lang.Object)">add</A></CODE> in interface <CODE><A HREF="../structure/Structure.html">Structure</A></CODE></DL>
</DD>
<DD><DL>
<DT><B>Parameters:</B><DD><CODE>val</CODE> - A reference to non-null object<DT><B>Postcondition:</B><DD>Adds a value to binary search tree</DL>
</DD>
</DL>
<HR>

<A NAME="contains(java.lang.Object)"><!-- --></A><H3>
contains</H3>
<PRE>
public boolean <B>contains</B>(<A HREF="http://java.sun.com/j2se/1.3/docs/api/java/lang/Object.html">Object</A>&nbsp;value)</PRE>
<DL>
<DD>Determines if the binary search tree contains a value<DD><DL>
<DT><B>Specified by: </B><DD><CODE><A HREF="../structure/Structure.html#contains(java.lang.Object)">contains</A></CODE> in interface <CODE><A HREF="../structure/Structure.html">Structure</A></CODE><DT><B>Overrides:</B><DD><CODE><A HREF="../structure/AbstractStructure.html#contains(java.lang.Object)">contains</A></CODE> in class <CODE><A HREF="../structure/AbstractStructure.html">AbstractStructure</A></CODE></DL>
</DD>
<DD><DL>
<DT><B>Parameters:</B><DD><CODE>val</CODE> - The value sought.  Should be non-null<DT><B>Postcondition:</B><DD>Returns true iff val is a value found within the tree<DT><B>Returns:</B><DD>True iff the tree contains a value "equals to" sought value</DL>
</DD>
</DL>
<HR>

<A NAME="get(java.lang.Object)"><!-- --></A><H3>
get</H3>
<PRE>
public <A HREF="http://java.sun.com/j2se/1.3/docs/api/java/lang/Object.html">Object</A> <B>get</B>(<A HREF="http://java.sun.com/j2se/1.3/docs/api/java/lang/Object.html">Object</A>&nbsp;value)</PRE>
<DL>
<DD>Returns reference to value found within three.  This method can
 be potentially dangerous if returned value is modified: if 
 modification would change the relation of value to others within
 the tree, the consistency of the structure is lost
 <b>Don't modify returned value</b><DD><DL>
</DL>
</DD>
<DD><DL>
<DT><B>Parameters:</B><DD><CODE>val</CODE> - Value sought from within tree<DT><B>Postcondition:</B><DD>Returns object found in tree, or null<DT><B>Returns:</B><DD>A value "equals to" value sought; otherwise null</DL>
</DD>
</DL>
<HR>

<A NAME="remove(java.lang.Object)"><!-- --></A><H3>
remove</H3>
<PRE>
public <A HREF="http://java.sun.com/j2se/1.3/docs/api/java/lang/Object.html">Object</A> <B>remove</B>(<A HREF="http://java.sun.com/j2se/1.3/docs/api/java/lang/Object.html">Object</A>&nbsp;value)</PRE>
<DL>
<DD>Remove an value "equals to" the indicated value.  Only one value
 is removed, and no guarantee is made concerning which of duplicate
 values are removed.  Value returned is no longer part of the
 structure<DD><DL>
<DT><B>Specified by: </B><DD><CODE><A HREF="../structure/Structure.html#remove(java.lang.Object)">remove</A></CODE> in interface <CODE><A HREF="../structure/Structure.html">Structure</A></CODE></DL>
</DD>
<DD><DL>
<DT><B>Parameters:</B><DD><CODE>val</CODE> - Value sought to be removed from tree<DT><B>Postcondition:</B><DD>Removes one instance of val, if found<DT><B>Returns:</B><DD>Actual value removed from tree</DL>
</DD>
</DL>
<HR>

<A NAME="removeTop(structure.BinaryTree)"><!-- --></A><H3>
removeTop</H3>
<PRE>
protected <A HREF="../structure/BinaryTree.html">BinaryTree</A> <B>removeTop</B>(<A HREF="../structure/BinaryTree.html">BinaryTree</A>&nbsp;topNode)</PRE>
<DL>
<DD>Removes the top node of the tree rooted, performs the necissary
 rotations to reconnect the tree.<DD><DL>
</DL>
</DD>
<DD><DL>
<DT><B>Parameters:</B><DD><CODE>topNode</CODE> - Contains the value we want to remove<DT><B>Precondition:</B><DD>topNode contains the value we want to remove<DT><B>Postcondition:</B><DD>We return an binary tree rooted with the predecessor of topnode.<DT><B>Returns:</B><DD>The root of a new binary tree containing all of topNodes 
 descendents and rooted at topNode's predecessor</DL>
</DD>
</DL>
<HR>

<A NAME="iterator()"><!-- --></A><H3>
iterator</H3>
<PRE>
public <A HREF="http://java.sun.com/j2se/1.3/docs/api/java/util/Iterator.html">Iterator</A> <B>iterator</B>()</PRE>
<DL>
<DD>Returns an iterator over the binary search tree.  Iterator should
 not be used if tree is modified, as behavior may be unpredicatable
 Traverses elements using in-order traversal order<DD><DL>
<DT><B>Specified by: </B><DD><CODE><A HREF="../structure/Structure.html#iterator()">iterator</A></CODE> in interface <CODE><A HREF="../structure/Structure.html">Structure</A></CODE></DL>
</DD>
<DD><DL>
<DT><B>Postcondition:</B><DD>Returns iterator to traverse BST<DT><B>Returns:</B><DD>An iterator over binary search tree</DL>
</DD>
</DL>
<HR>

<A NAME="hashCode()"><!-- --></A><H3>
hashCode</H3>
<PRE>
public int <B>hashCode</B>()</PRE>
<DL>
<DD>Returns the hashCode of the value stored by this object.<DD><DL>
<DT><B>Overrides:</B><DD><CODE><A HREF="../structure/AbstractStructure.html#hashCode()">hashCode</A></CODE> in class <CODE><A HREF="../structure/AbstractStructure.html">AbstractStructure</A></CODE></DL>
</DD>
<DD><DL>
<DT><B>Returns:</B><DD>The hashCode of the value stored by this object.</DL>
</DD>
</DL>
<HR>

<A NAME="treeString()"><!-- --></A><H3>
treeString</H3>
<PRE>
public <A HREF="http://java.sun.com/j2se/1.3/docs/api/java/lang/String.html">String</A> <B>treeString</B>()</PRE>
<DL>
<DD>Returns a (possibly long) string representing tree.  Differs
 from <A HREF="../structure/BinarySearchTree.html#toString()"><CODE>toString()</CODE></A> in that <A HREF="../structure/BinarySearchTree.html#toString()"><CODE>toString()</CODE></A> outputs 
 a single line representation of the contents of the tree.
 <code>treeString</code>, however, prints out a graphical 
 representations of the tree's <i>structure</i>.<DD><DL>
</DL>
</DD>
<DD><DL>
<DT><B>Postcondition:</B><DD>Generates a string representation of the AVLST<DT><B>Returns:</B><DD>String representation of tree</DL>
</DD>
</DL>
<HR>

<A NAME="toString()"><!-- --></A><H3>
toString</H3>
<PRE>
public <A HREF="http://java.sun.com/j2se/1.3/docs/api/java/lang/String.html">String</A> <B>toString</B>()</PRE>
<DL>
<DD>Returns a string representing tree<DD><DL>
<DT><B>Overrides:</B><DD><CODE><A HREF="http://java.sun.com/j2se/1.3/docs/api/java/lang/Object.html#toString()">toString</A></CODE> in class <CODE><A HREF="http://java.sun.com/j2se/1.3/docs/api/java/lang/Object.html">Object</A></CODE></DL>
</DD>
<DD><DL>
<DT><B>Postcondition:</B><DD>Generates a string representation of the BST<DT><B>Returns:</B><DD>String representation of tree</DL>
</DD>
</DL>
<!-- ========= END OF CLASS DATA ========= -->
<HR>

<!-- ========== START OF NAVBAR ========== -->
<A NAME="navbar_bottom"><!-- --></A>
<TABLE BORDER="0" WIDTH="100%" CELLPADDING="1" CELLSPACING="0">
<TR>
<TD COLSPAN=2 BGCOLOR="#EEEEFF" CLASS="NavBarCell1">
<A NAME="navbar_bottom_firstrow"><!-- --></A>
<TABLE BORDER="0" CELLPADDING="0" CELLSPACING="3">
  <TR ALIGN="center" VALIGN="top">
  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="package-summary.html"><FONT CLASS="NavBarFont1"><B>Package</B></FONT></A>&nbsp;</TD>
  <TD BGCOLOR="#FFFFFF" CLASS="NavBarCell1Rev"> &nbsp;<FONT CLASS="NavBarFont1Rev"><B>Class</B></FONT>&nbsp;</TD>
  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="package-tree.html"><FONT CLASS="NavBarFont1"><B>Tree</B></FONT></A>&nbsp;</TD>
  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="../deprecated-list.html"><FONT CLASS="NavBarFont1"><B>Deprecated</B></FONT></A>&nbsp;</TD>
  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="../index-all.html"><FONT CLASS="NavBarFont1"><B>Index</B></FONT></A>&nbsp;</TD>
  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="../help-doc.html"><FONT CLASS="NavBarFont1"><B>Help</B></FONT></A>&nbsp;</TD>
  </TR>
</TABLE>
</TD>
<TD ALIGN="right" VALIGN="top" ROWSPAN=3><EM>
<a href=../copyright.html target=_top>&copy; 1998-2002 McGraw-Hill</a></EM>
</TD>
</TR>

<TR>
<TD BGCOLOR="white" CLASS="NavBarCell2"><FONT SIZE="-2">
&nbsp;<A HREF="../structure/Association.html"><B>PREV CLASS</B></A>&nbsp;
&nbsp;<A HREF="../structure/BinaryTree.html"><B>NEXT CLASS</B></A></FONT></TD>
<TD BGCOLOR="white" CLASS="NavBarCell2"><FONT SIZE="-2">
  <A HREF="../index.html" TARGET="_top"><B>FRAMES</B></A>  &nbsp;
&nbsp;<A HREF="BinarySearchTree.html" TARGET="_top"><B>NO FRAMES</B></A></FONT></TD>
</TR>
<TR>
<TD VALIGN="top" CLASS="NavBarCell3"><FONT SIZE="-2">
  SUMMARY: &nbsp;INNER&nbsp;|&nbsp;<A HREF="#field_summary">FIELD</A>&nbsp;|&nbsp;<A HREF="#constructor_summary">CONSTR</A>&nbsp;|&nbsp;<A HREF="#method_summary">METHOD</A></FONT></TD>
<TD VALIGN="top" CLASS="NavBarCell3"><FONT SIZE="-2">
DETAIL: &nbsp;<A HREF="#field_detail">FIELD</A>&nbsp;|&nbsp;<A HREF="#constructor_detail">CONSTR</A>&nbsp;|&nbsp;<A HREF="#method_detail">METHOD</A></FONT></TD>
</TR>
</TABLE>
<!-- =========== END OF NAVBAR =========== -->

<HR>

</BODY>
</HTML>