Arbol Binario
Enviado por charly1403 • 18 de Noviembre de 2012 • 3.242 Palabras (13 Páginas) • 706 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.
...