Arbol Binario
Enviado por charly1403 • 18 de Noviembre de 2012 • 3.242 Palabras (13 Páginas) • 746 Visitas
public class BusquedaArbolBinario{
/**
* Root node of the binary search tree.
*/
private Node root;
/**
* Internal static class for storing the nodes.
*/
public static class Node {
Node parent;
Node left;
Node right;
int data;
Node( int data ) {
this.data = data;
}
@Override
public String toString( ) {
return "" + data;
}
public int getContent(){
return data;
}
public Node getLeft(){
return left;
}
public Node getRight(){
return right;
}
}
/**
* Inserts a new node that has the specified data. The insert starts from
* the root of the tree and goes all the way down until it finds a spot to
* place the new node.
*/
public void insert( int data ) {
root = insert( root, data );
}
public Node getRoot(){
return root;
}
/**
* Inserts a new node that has the specified data. The insert starts from
* the specified node of the tree and goes all the way down until it finds
* a spot to place the new node.
*/
public Node insert( Node node, int data ) {
if( node == null ) {
// Found a spot to insert new node.
node = new Node( data );
} else if( data < node.data ) {
// Insert in left subtree
node.left = insert( node.left, data );
node.left.parent = node;
} else {
// Insert right subtree.
node.right = insert( node.right, data );
node.right.parent = node;
}
// Done!
return node;
}
/**
* Helper method for the binary search tree delete operation. It used for
* swapping the nodes, while keeping the structure of the binary search tree.
* Refer to page 296 of Introduction to Algorithms (3rd Edition) by Cormen
* et. al. for further details.
*/
private void swap( Node a, Node b ) {
if( a.parent == null ) {
root = b;
} else if( a == a.parent.left ) {
a.parent.left = b;
} else {
a.parent.right = b;
}
if( b != null ) {
b.parent = a.parent;
}
}
/**
* Deletes the node containing the specified data. The search for the node
* to be deleted starts from the root node.
*/
public void delete( int data ) {
delete( root, data );
}
public void delete( Node node, int data ) {
// Can't find the node we want to delete.
if( node == null ) {
return;
}
// We've found the node we want to delete.
else if ( data == node.data) {
// Check if it has a left subtree. If it deson't then just replace
// the node we want to delete with its right subtree.
if( node.left == null ) {
swap( node, node.right );
}
// Check if it has a right subtree. If it doesn't then just replace
// the node we want to delete with its left subtree.
else if( node.right == null ) {
swap( node, node.left );
}
// Since it has both a left and right subtree, then traverse to the
// left-most child of the right subtree (i.e. the smallest node in the
// right subtree). Once found, exchange the data values between the node
// and the node that we want to delete.
else {
Node minNode = node.right;
while( minNode.left != null ) {
minNode = minNode.left;
}
if( minNode.parent != node ) {
swap( minNode, minNode.right );
minNode.right = node.right;
minNode.right.parent = minNode;
}
swap( node, minNode );
minNode.left = node.left;
minNode.left.parent = minNode;
}
}
// Continue searching in the left subtree.
else if( data < node.data) {
delete( node.left, data );
}
// Continue searching in the right subtree.
else {
delete( node.right, data );
}
}
/**
* Returns a boolean true if it finds the specified data in the tree, or false
* otherwise. The search starts from the root node of the tree.
*/
public boolean lookup( int data ) {
return lookup( root, data );
}
/**
* Returns a boolean true if it finds the specified data in the tree, or false
* otherwise. The search starts from the specified node of the tree. Thus, you
* can either search the whole tree or a subtree.
*/
public boolean lookup( Node node, int data ) {
if( node == null ) {
// Can't find it.
return false;
} else if( data ==
...