net.cscott.jutil
public class BinaryTree extends Object
All elements of a given BinaryTree t must be mutually comparable, either inherently or through an external Comparator.
Unlike a java.util.TreeSet, duplicate elements are allowed in a BinaryTree.
FSK: We should probably have a Tree interface by now... Sometimes you want to expose the fact that you're working with a Tree, instead of abstract it into a Set or what-have-you. Have to think about adding that.
See Also: "CLR section 13, (page 244)."
Nested Class Summary | |
---|---|
class | BinaryTree.Node A Node is an element of this tree. |
Field Summary | |
---|---|
protected Comparator | comp |
protected BinaryTree.Node | NIL |
Constructor Summary | |
---|---|
BinaryTree() Creates an empty tree which accepts only mutually
comparable elements. | |
BinaryTree(Comparator c) Creates an empty tree which uses c to determine
element ordering. |
Method Summary | |
---|---|
BinaryTree.Node | add(Object k) Constructs a node for k and inserts it into this.
|
boolean | contains(Object k) Returns true if k is present in this . |
protected void | deleteNode(BinaryTree.Node z) Splices z out from this.
|
String | dump() |
String | dump(BinaryTree.Node x) |
protected void | insertNode(BinaryTree.Node z) Inserts z into some appropriate position in this .
requires: (z.left == z.right == NIL)
modifies: this, z
From CLR, pg 251. |
static void | main(String[] args) |
protected BinaryTree.Node | makeNode(Object key) Creates a Node n for this such that n.key == k.
|
Object | maximum() Returns the maximum element of this .
|
protected BinaryTree.Node | maximum(BinaryTree.Node x) Finds the maximum Node n (in the subtree rooted at x).
|
Object | minimum() Returns the minimum element of this .
|
protected BinaryTree.Node | minimum(BinaryTree.Node x) Finds the minimum Node n (in the subtree rooted at x).
|
void | remove(Object k) |
protected BinaryTree.Node | root() |
protected BinaryTree.Node | search(BinaryTree.Node x, Object k) Finds the Node n (in the subtree rooted at x)
such that n.key = k.
|
protected BinaryTree.Node | setLeft(BinaryTree.Node p, BinaryTree.Node l) Sets the left child of p.
|
protected BinaryTree.Node | setParent(BinaryTree.Node c, BinaryTree.Node p) Sets the parent of p.
|
protected BinaryTree.Node | setRight(BinaryTree.Node p, BinaryTree.Node r) Sets the right child of p.
|
protected BinaryTree.Node | setRoot(BinaryTree.Node r) |
protected BinaryTree.Node | successor(BinaryTree.Node x) Returns the successor of x in the sorted order determined by
an inorder tree walk.
|
protected void | swapPositions(BinaryTree.Node a, BinaryTree.Node b) Switches the positions of a and b
within this . |
void | test() |
See Also: java.lang.Comparable
c
to determine
element ordering.k
and inserts it into this.
Uses nodes' own methods to dispatchk
is present in this
.z
out from this.
Based on CLR, pg 253.
modifies: this, zthis
.
requires: (z.left == z.right == NIL)
modifies: this, z
From CLR, pg 251. Note that makeNode must deal with the case when key
is null
, regardless of whether the tree itself
allows null elements, because the NIL sentinel node has
null
as its key.
this
.
Requires: this is non-empty.this
.
Requires: this is non-empty.a
and b
within this
. Subclasses are expected to swap any
data derived from the positions as well.