Estructura de datos y algoritmos: árbol
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 para almacenar 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.
Path - Ruta se refiere a la secuencia de nodos a lo largo de los bordes de un árbol.
Root- 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.
Parent - Cualquier nodo excepto el nodo raíz tiene un borde hacia arriba hasta un nodo llamado padre.
Child - El nodo debajo de un nodo dado conectado por su borde hacia abajo se llama su nodo hijo.
Leaf - El nodo que no tiene ningún nodo hijo se llama nodo hoja.
Subtree - Subárbol representa los descendientes de un nodo.
Visiting - Visitar se refiere a verificar el valor de un nodo cuando el control está en el nodo.
Traversing - Atravesar significa atravesar nodos en un orden específico.
Levels- 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.
keys - 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 presenta 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 da 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:
Insert - Inserta un elemento en un árbol / crea un árbol.
Search - Busca un elemento en un árbol.
Preorder Traversal - Atraviesa un árbol en forma de reserva.
Inorder Traversal - Atraviesa un árbol de manera ordenada.
Postorder Traversal - Atraviesa un árbol de manera posterior a la orden.
Aprenderemos a crear (insertar en) 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 IfImplementació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 busque 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 ifLa 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í .