Estructuras de Datos - Arbol Binario de Ordenamiento

Arbol binario.

Un arbol es una estructura de datos que emula una estructura de un arbol real. Los arboles tienen los siguientes elementos:

Nodo Raiz: El nodo raiz es aquel que no tiene nodo padre.
Nodos Hoja: Es un nodo que no tiene nodos hijos.
Nodos Internos: Son nodos que tienen al menos un hijo y tienen padre.

Un Arbol Binario de ordenamiento es una estructura de datos que permite almacenar informacion que siempre estara ordenada, por lo que la busqueda de un elemento si el arbol esta bien balanceado (Tiene el mismo peso del lado izquiero que del derecho) tendra un orden (Big-O) de O(log n) .

A continuación puede ver un ejemplo de un arbol binario simple en Java, no tiene balanceo, si necesita implementar uno, este le puede servir.





public class BinaryTree {

private Node root;

class Node {

int element;
Node leftNode;
Node rightNode;
Node parentNode;

public Node() {
super();
}
public Node(int element) {
this();
this.element = element;
}


/**
* Add an element to this tree
* @param element
*/
void addElement(int element) {
if (element > this.element) {
if (rightNode == null) {
rightNode = new Node(element);
rightNode.parentNode = this;
} else {
rightNode.addElement(element);
}
}else {
if (leftNode == null) {
leftNode = new Node(element);
leftNode.parentNode = this;
} else {
leftNode.addElement(element);
}
}
}
}

/**
* Add an element to the tree
* @param element
*/
public void addElement(int element) {
if (root == null)
root = new Node(element);
else
root.addElement(element);
}

public void printInOrder() {
printInOrder(root);
}

private void printInOrder(Node node) {
if (node == null) return;
printInOrder(node.leftNode);
System.out.print(" " + node.element);
printInOrder(node.rightNode);
}

public void printPreOrder() {
printPreOrder(root);
}

private void printPreOrder(Node node) {
if (node == null) return;
System.out.print(" " + node.element);
printPreOrder(node.leftNode);
printPreOrder(node.rightNode);
}

public void printPostOrder() {
printPostOrder(root);
}

private void printPostOrder(Node node) {
if (node == null) return;
printPostOrder(node.leftNode);
printPostOrder(node.rightNode);
System.out.print(" " + node.element);
}


public static void main (String []args) {
int []list = new int [] { 5, 3, 7, 1, 9, 2, 8, 4, 6};
BinaryTree tree = new BinaryTree();

for (int element : list)
tree.addElement(element);

System.out.println("In order: ");
tree.printInOrder();

}
}