El árbol representa los nodos conectados por bordes. Discutiremos el árbol binario o el árbol de búsqueda binario específicamente.
El árbol binario es una estructura de datos especial que se utiliza con fines de almacenamiento de datos. Un árbol binario tiene la condición especial de que cada nodo puede tener un máximo de dos hijos. Un árbol binario tiene los beneficios tanto de una matriz ordenada como de una lista vinculada, ya que la búsqueda es tan rápida como en una matriz ordenada y la operación de inserción o eliminación es tan rápida como en una lista vinculada.
Términos importantes
Los siguientes son los términos importantes con respecto al árbol.
-
Sendero – Ruta se refiere a la secuencia de nodos a lo largo de los bordes de un árbol.
-
Raíz – El nodo en la parte superior del árbol se llama raíz. Solo hay una raíz por árbol y una ruta desde el nodo raíz a cualquier nodo.
-
Padre – Cualquier nodo excepto el nodo raíz tiene un borde hacia arriba hasta un nodo llamado padre.
-
Niño – El nodo debajo de un nodo dado conectado por su borde hacia abajo se llama su nodo hijo.
-
Hoja – El nodo que no tiene ningún nodo hijo se llama nodo hoja.
-
Subárbol – Subárbol representa los descendientes de un nodo.
-
Visitando – Visitar se refiere a verificar el valor de un nodo cuando el control está en el nodo.
-
Atravesar – Atravesar significa atravesar nodos en un orden específico.
-
Niveles – El nivel de un nodo representa la generación de un nodo. Si el nodo raíz está en el nivel 0, entonces su siguiente nodo hijo está en el nivel 1, su nieto está en el nivel 2, y así sucesivamente.
-
teclas – La clave representa un valor de un nodo en función del cual se realizará una operación de búsqueda para un nodo.
Representación del árbol de búsqueda binaria
El árbol de búsqueda binaria exhibe un comportamiento especial. El hijo izquierdo de un nodo debe tener un valor menor que el valor de su padre y el hijo derecho del nodo debe tener un valor mayor que su valor padre.
Vamos a implementar un árbol usando un objeto de nodo y conectándolos a través de referencias.
Nodo de árbol
El código para escribir un nodo de árbol sería similar al que se muestra a continuación. Tiene una parte de datos y referencias a sus nodos secundarios izquierdo y derecho.
struct node { int data; struct node *leftChild; struct node *rightChild; };
En un árbol, todos los nodos comparten una construcción común.
Operaciones básicas de BST
Las operaciones básicas que se pueden realizar en una estructura de datos de árbol de búsqueda binaria son las siguientes:
-
Insertar – Inserta un elemento en un árbol / crea un árbol.
-
Buscar – Busca un elemento en un árbol.
-
Recorrido de pedidos anticipados – Atraviesa un árbol en forma de reserva.
-
Inorden Traversal – Atraviesa un árbol de manera ordenada.
-
Traslado posterior al pedido – Atraviesa un árbol de manera posterior a la orden.
Aprenderemos a crear (insertar) una estructura de árbol y buscar un elemento de datos en un árbol en este capítulo. Aprenderemos sobre los métodos para atravesar árboles en el próximo capítulo.
Insertar operación
La primera inserción crea el árbol. Luego, siempre que se inserte un elemento, primero ubique su ubicación adecuada. Comience a buscar desde el nodo raíz, luego, si los datos son menores que el valor clave, busque la ubicación vacía en el subárbol izquierdo e inserte los datos. De lo contrario, busque la ubicación vacía en el subárbol derecho e inserte los datos.
Algoritmo
If root is NULL then create root node return If root exists then compare the data with node.data while until insertion position is located If data is greater than node.data goto right subtree else goto left subtree endwhile insert data end If
Implementación
La implementación de la función de inserción debería verse así:
void insert(int data) { struct node *tempNode = (struct node*) malloc(sizeof(struct node)); struct node *current; struct node *parent; tempNode->data = data; tempNode->leftChild = NULL; tempNode->rightChild = NULL; //if tree is empty, create root node if(root == NULL) { root = tempNode; } else { current = root; parent = NULL; while(1) { parent = current; //go to left of the tree if(data < parent->data) { current = current->leftChild; //insert to the left if(current == NULL) { parent->leftChild = tempNode; return; } } //go to right of the tree else { current = current->rightChild; //insert to the right if(current == NULL) { parent->rightChild = tempNode; return; } } } } }
Operación de búsqueda
Siempre que se deba buscar un elemento, comience a buscar desde el nodo raíz, luego, si los datos son menores que el valor clave, busque el elemento en el subárbol izquierdo. De lo contrario, busque el elemento en el subárbol derecho. Siga el mismo algoritmo para cada nodo.
Algoritmo
If root.data is equal to search.data return root else while data not found If data is greater than node.data goto right subtree else goto left subtree If data found return node endwhile return data not found end if
La implementación de este algoritmo debería verse así.
struct node* search(int data) { struct node *current = root; printf("Visiting elements: "); while(current->data != data) { if(current != NULL) printf("%d ",current->data); //go to left tree if(current->data > data) { current = current->leftChild; } //else go to right tree else { current = current->rightChild; } //not found if(current == NULL) { return NULL; } return current; } }
Para conocer la implementación de la estructura de datos de árbol de búsqueda binaria, haga clic aquí.