Las listas enlazadas, las pilas y las colas son estructuras lineales de datos. Un árbol es una estructura no lineal y de dos dimensiones de datos, con propiedades especiales. Los nodos de los árboles contienen dos o más enlaces. Veremos, los árboles binarios, cuyos nodos contienen dos enlaces (ninguno, uno, o ambos de los cuales pudieran ser NULL). El nodo raiz es el primer nodo de un árbol. El hijo izquierdo es el primer nodo en el subárbol izquierdo y el hijo derecho en el subárbol derecho. Los hijos de un nodo se conocen como sus descendientes. Un nodo sin hijos se conoce como un nodo hoja.

En este tema estudiaremos el árbol de búsqueda binario, el cual tiene la característica de que los valores en cualquier subárbol izquierdo son menores que el valor en sus nodos padre, y los valores en cualquier subárbol derecho son mayores que el valor en sus nodos padre. Además, la forma del árbol de búsqueda binario puede variar, dependien do del orden en el cual los valores están insertos dentro del árbol.

Las funciones utilizadas para crear y recorrer un árbol binario de búsqueda son recursivas. La función insertNode recibe como argumentos la dirección del árbol y un entero para almacenarse en el árbol. En un árbol de búsqueda binario un nodo puede ser únicamente inserto como nodo de hoja. Los pasos para hacer la inserción de un nodo son:

1. Si *treePtr es NULL, crea un nuevo nodo. Llame a malloc, asigna la memoria asignada a *treePtr, asigna a (*treePtr)->data el entero a almacenarse, asigna a (*treePtr)->leftPtr y (*treePtr)->rightPtr el valor NULL y devuelve o regresa el control al llamador (main o insertNode).
2. Si el valor de *treePtr no es NULL, y el valor a insertarse es menor que (*treePtr)->data, se llama a la función insertNode con la dirección de (*treePtr)->leftPtr. De no ser así, se llama a la función insertNode con la dirección de (*treePtr)->rightPtr. Se continuan los pasos recursivos hasta que se encuentre un apuntador NULL, entonces se ejecutará el paso 1 para insertar el nuevo nodo.

Para recorrer un árbol, hay tres formas: enorden, preorden y postorden.

El árbol binario de búsqueda facilita la eleiminación de duplicados, ya que conforme se crea el árbol, cualquier intentento para insertar un valor duplicado será detectado porque en cada una de las comparaciones un duplicado seguirá las mismas decisiones (ir a izquierda o ir a dercha) que utilizó el valor original, con el que será comparado y podrá ser descartado.También es rápido buscar en un árbol binario un valor que coincida con un valor clave.