|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--asd_library.tree.bstree.BSTree
The class BSTree implements a binary tree with the following property: for each node n, every left-subtree value is less then the key value v stored in n and every right-subtree value is greater then v.
Field Summary | |
protected BSTNode |
root
|
protected int |
size
|
Constructor Summary | |
BSTree()
Creates an empty BSTree |
Method Summary | |
void |
balance(java.lang.Comparable[] data,
int first,
int last)
Inserts the element from the specified array into this tree. |
void |
breadthFirst()
Implements a breadth-first traversal from the root towards the leafs and from left towards right. |
void |
clear()
Removes all of the elements from this BSTree |
java.lang.Comparable |
element(BSTNode v)
Method to get element field. |
java.lang.Object |
find(java.lang.Comparable el)
Finds the specified element el. |
int |
getSize()
Returns the number of nodes in this BSTree. |
void |
inorder()
Implements a inorder traversal of this BSTree, beginning from the root. |
void |
inorder(BSTNode p)
Recorsive method to implement the inorder traversal, beginning from the specified node p. |
void |
insert(BSTNode node)
Inserts the specified node in this BSTree. |
void |
insert(java.lang.Comparable el)
Inserts the specified element in this BSTree. |
boolean |
isEmpty()
Tests if this BSTree has no components. |
boolean |
isInTree(java.lang.Comparable el)
Tests if the specified object is in this BSTree. |
boolean |
isLeaf(BSTNode v)
Verifies if the node v is a leaf. |
boolean |
isRoot(BSTNode v)
Verifies if the node v is the root of this tree |
void |
iterativeInorder()
Iterative method to implement the inorder traversal. |
void |
iterativePostorder()
Iterative method to implement the postorder traversal. |
void |
iterativePreorder()
Iterative method to implement the preorder traversal. |
BSTNode |
iterativeSearch(BSTNode p,
java.lang.Comparable el)
Iterative method to find the element el, starting from the specified node p |
BSTNode |
iterativeSearch(java.lang.Comparable el)
Searches for the element el in this BSTree. |
BSTNode |
leftChild(BSTNode v)
Returns the left child node of v |
void |
postorder()
Implements a postorder traversal of this BSTree, beginning from the root. |
void |
postorder(BSTNode p)
Recorsive method to implement the postorder traversal, beginning from the specified node p. |
BSTNode |
predecessor(BSTNode p,
java.lang.Comparable el)
Searches the predecessor of the node with key equals to el, starting from the node p |
BSTNode |
predecessor(java.lang.Comparable el)
Searches the predecessor of the node with key equals to el. |
void |
preorder()
Implements a preorder traversal of this BSTree, beginning from the root. |
void |
preorder(BSTNode p)
Recorsive method to implement the preorder traversal, beginning from the specified node p. |
void |
remove(java.lang.Comparable el)
Removes the element el from this tree |
BSTNode |
rightChild(BSTNode v)
Returns the right child node of v |
BSTNode |
root()
Return the BSTree root node |
BSTNode |
search(BSTNode p,
java.lang.Comparable el)
Recorsive method to find the element el, starting from the specified node p |
BSTNode |
search(java.lang.Comparable el)
Searches for the element el in this BSTree. |
BSTNode |
successor(BSTNode p,
java.lang.Comparable el)
Searches the successor of the node with key equals to el, starting from the node p |
BSTNode |
successor(java.lang.Comparable el)
Searches the successor of the node with key equals to el. |
int |
treeHeight()
Returns the height of this BSTree. |
int |
treeHeight(BSTNode node)
Returns the height of the subtree with root in node. |
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
protected BSTNode root
protected int size
Constructor Detail |
public BSTree()
Method Detail |
public BSTNode root()
root
in interface BSTree_adt
public java.lang.Comparable element(BSTNode v)
element
in interface BSTree_adt
v
- the node.
public boolean isLeaf(BSTNode v)
isLeaf
in interface BSTree_adt
v
- the node
public boolean isRoot(BSTNode v)
isRoot
in interface BSTree_adt
v
- the node
public void insert(java.lang.Comparable el)
insert
in interface Dictionary_adt
el
- element to insert.public void remove(java.lang.Comparable el)
remove
in interface Dictionary_adt
el
- the elment to removepublic java.lang.Object find(java.lang.Comparable el)
find
in interface Dictionary_adt
el
- the element to search.
public BSTNode leftChild(BSTNode v)
v
- the parent node
public BSTNode rightChild(BSTNode v)
v
- the parent node
public void clear()
public boolean isEmpty()
public BSTNode search(java.lang.Comparable el)
el
- the element to search for.
public BSTNode search(BSTNode p, java.lang.Comparable el)
p
- the node to start searching from.el
- the element.
public BSTNode iterativeSearch(java.lang.Comparable el)
el
- the element to search for.
public BSTNode iterativeSearch(BSTNode p, java.lang.Comparable el)
p
- the node to start searching from.el
- the element.
public void insert(BSTNode node)
node
- node to insert.public boolean isInTree(java.lang.Comparable el)
el
- the object to test.
public int getSize()
public void preorder()
public void inorder()
public void postorder()
public void inorder(BSTNode p)
p
- a node.public void preorder(BSTNode p)
p
- a node.public void postorder(BSTNode p)
p
- a node.public void iterativePreorder()
public void iterativeInorder()
public void iterativePostorder()
public void breadthFirst()
public int treeHeight()
public int treeHeight(BSTNode node)
node
-
public BSTNode predecessor(java.lang.Comparable el)
el
- the specified element.
public BSTNode predecessor(BSTNode p, java.lang.Comparable el)
p
- the specified nodeel
- key of the specified node.
public BSTNode successor(java.lang.Comparable el)
el
- the specified element.
public BSTNode successor(BSTNode p, java.lang.Comparable el)
p
- the specified nodeel
- key of the specified node.
public void balance(java.lang.Comparable[] data, int first, int last)
data
- array of elements.first
- first index in the array.last
- index in the array.
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |