Anuncios

Árbol representa los nodos conectados por aristas. Discutiremos árbol binario o árbol de búsqueda binario específicamente.

El árbol binario es una estructura de datos especial utilizada para fines de almacenamiento de datos. Un árbol binario tiene una condición especial que cada nodo puede tener un máximo de dos hijos., Un árbol binario tiene los beneficios de una matriz ordenada y 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 la lista vinculada.

Términos Importantes

los Siguientes son los términos importantes con respecto al árbol.

  • Path-Path 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 root. 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 a un nodo llamado Padre.

  • hijo-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 a los descendientes de un nodo.

  • Visiting-Visiting se refiere a comprobar el valor de un nodo cuando control está en el nodo.

  • Traversing-Traversing significa pasar a través de 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.

  • keys-Key representa un valor de un nodo basado en el cual se va a llevar a cabo 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 tree usando node object 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 hijos 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.

BST operaciones básicas

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 de una manera de pre-orden.

  • Inorder Traversal-atraviesa un árbol en orden.

  • Postorder Traversal-atraviesa un árbol de una manera post-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 de atravesar árboles en el próximo capítulo.

insertar operación

la primera inserción crea el árbol., Después, cada vez que se va a insertar un elemento, primero localice su ubicación adecuada. Comience a buscar desde el nodo raíz, luego si los datos son menores que el valor de la 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 nodereturnIf 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 dataend If

implementación

la implementación de la función insert debería tener este aspecto −

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 de la clave, busque el elemento en el subárbol izquierdo. De lo contrario, busque el elemento en el subárbol correcto. Siga el mismo algoritmo para cada nodo.

Algorithm

If root.data is equal to search.data return rootelse 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 tener este aspecto.,

para saber sobre la implementación de la estructura de datos de árbol de búsqueda binaria, haga clic aquí.

Anuncios