La representación visual de los conceptos discutidos se muestra en la siguiente figura:
Esta guía explica el proceso de impresión de todos los nodos hoja de un árbol binario cubriendo las secciones mencionadas a continuación:
- ¿Cómo identificar los nodos de las hojas?
- ¿Cómo imprimir todos los nodos hoja de un árbol binario de izquierda a derecha en JavaScript?
- Consejo adicional: imprimir nodos de hoja de un árbol binario de derecha a izquierda
- Conclusión
¿Cómo identificar los nodos de las hojas?
El ' hoja 'Los nodos son los que no tienen nodos secundarios, o para ser específicos, los que tienen el ' altura ' de ' 0 ”. Si el nodo tiene un “ altura ' mas grande que ' 0 ”entonces ese nodo puede ser el nodo interno o el nodo raíz. El ' hoja Los nodos generalmente se rastrean hacia atrás para identificar la fuente original desde donde se genera este nodo. Se utiliza principalmente en algoritmos de búsqueda o búsqueda de errores para encontrar la causa de un error o problema.
¿Cómo imprimir todos los nodos hoja de un árbol binario de izquierda a derecha en JavaScript?
Hay dos enfoques” recursivo ' y ' iterativo 'para seleccionar todos los nodos hoja disponibles en el árbol binario proporcionado en el' deseado izquierda ' a ' bien ' dirección. La implementación práctica de estos enfoques se demuestra en las secciones que se indican a continuación:
- Imprima todos los nodos de hoja de un árbol binario de izquierda a derecha de forma recursiva
- Imprima todos los nodos de hoja de un árbol binario utilizando el enfoque iterativo
Método 1: imprimir todos los nodos hoja de un árbol binario de izquierda a derecha de forma recursiva
El enfoque recursivo selecciona todos los nodos en un algoritmo de búsqueda en profundidad manera que primero atraviesa todos los nodos del lado izquierdo, luego el nodo del medio y los nodos del lado derecho al final. Esta operación se realiza de forma recursiva para cada nodo y cuando ya no se puede atravesar el ' hoja ”Los nodos se identifican. Para comprender mejor este concepto, visite el siguiente fragmento de código:
clase Nodo{
constructor ( )
{
este . contenido = 0 ;
este . izquierda = nulo ;
este . bien = nulo ;
}
} ;
donde mostrarLeafNodes = ( nodoraíz ) =>
{
si ( nodoraíz == nulo )
devolver ;
si ( raízNodo. izquierda == nulo && raízNodo. bien == nulo )
{
documento. escribir ( raízNodo. contenido + ' ' ) ;
devolver ;
}
si ( raízNodo. izquierda != nulo )
mostrarNodos de hoja ( raízNodo. izquierda ) ;
si ( raízNodo. bien != nulo )
mostrarNodos de hoja ( raízNodo. bien ) ;
}
era nodo de muestra = ( vale ) =>
{
era nodo temporal = nuevo Nodo ( ) ;
nodotemp. contenido = vale ;
nodotemp. izquierda = nulo ;
nodotemp. bien = nulo ;
devolver nodo temporal ;
}
era rootNode = provNodo ( 3 ) ;
raízNodo. izquierda = provNodo ( 6 ) ;
raízNodo. bien = provNodo ( 9 ) ;
raízNodo. izquierda . izquierda = provNodo ( 12 ) ;
raízNodo. izquierda . bien = provNodo ( 15 ) ;
raízNodo. izquierda . bien . bien = provNodo ( 24 ) ;
raízNodo. bien . izquierda = provNodo ( 18 ) ;
raízNodo. bien . bien = provNodo ( 21 ) ;
mostrarNodos de hoja ( nodoraíz ) ;
La explicación del bloque de código anterior se indica a continuación:
- Primero, crea una clase llamada ' nodo ”, que crea un nuevo nodo y establece su valor en “ 0 ”. Lo adjuntado ' izquierda ' y ' bien 'Los nodos laterales están configurados en ' nulo ”de forma predeterminada utilizando el constructor de clases.
- A continuación, defina un “ mostrarNodosHoja() 'Función que acepta un solo parámetro de' nodoraíz ”. Este valor paramétrico se considera como el nodo actualmente seleccionado de un árbol binario.
- Dentro de la función, el “ si 'La declaración se utiliza para comprobar si el' nodoraíz ”es nulo o no. En el caso de ' nulo ”La ejecución adicional se detuvo para ese nodo. En el otro caso, el rootNode “ izquierda ' y ' bien 'Se comprueban los nodos laterales para ver si hay' nulo ”. Si ambos son nulos, el valor de ese ' nodo ”se imprime.
- Si el ' izquierda ' o ' bien 'El nodo no es 'nulo', luego pase ese lado del nodo al ' mostrarNodosHoja() ”Función para la operación recursiva.
- Defina una nueva función llamada “ provNodo() ”que acepta el parámetro único de “ vale ”. Dentro de la función crea una nueva instancia del ' Nodo 'clase llamada' nodo temporal ”. Asigne el parámetro “ vale 'como valor de la propiedad de clase' contenido ' y establezca el ' izquierda ' y ' bien ” nodos laterales a “ nulo ' por defecto.
- Finalmente, crea un objeto llamado ' nodoraíz ' Para el ' provNodo() ”Función y pase el valor del nodo como este parámetro de función. Cree los nodos del lado izquierdo y derecho agregando ' izquierda ' y ' bien 'Palabras clave con el' rootNode 'y asignarles valor usando la misma función' provNodo() ”.
- El ' izquierda ' significa la posición izquierda del nodo raíz y el ' izquierda izquierda 'La posición significa a la izquierda de la izquierda. Se aplica el mismo enfoque en el caso de' bien ' y ' bien ”
- Después de definir el árbol, pase el 'rootNode' como argumento para ' mostrarNodosLead() Función ”para seleccionar e imprimir todos los nodos de hoja del árbol creado.
El resultado generado después de la compilación confirma que el nodo hoja del árbol proporcionado se recuperó e imprimió en la consola:
Método 2: imprimir todos los nodos de hoja de un árbol binario utilizando el enfoque iterativo
El ' iterativo 'El enfoque es el más eficiente, utiliza el concepto de ' empujar ' y ' estallido ”para seleccionar el “ hoja ”nodos. Los puntos clave o el funcionamiento de este enfoque se detallan a continuación:
clase Nodo{
constructor ( valor )
{
este . datos = valor ;
este . izquierda = nulo ;
este . bien = nulo ;
}
} ;
donde mostrarLeafNodes = ( nodoraíz ) =>
{
si ( ! nodoraíz )
devolver ;
dejar lista = [ ] ;
lista. empujar ( nodoraíz ) ;
mientras ( lista. longitud > 0 ) {
nodoraíz = lista [ lista. longitud - 1 ] ;
lista. estallido ( ) ;
si ( ! raízNodo. izquierda && ! raízNodo. bien )
documento. escribir ( raízNodo. datos + ' ' ) ;
si ( raízNodo. bien )
lista. empujar ( raízNodo. bien ) ;
si ( raízNodo. izquierda )
lista. empujar ( raízNodo. izquierda ) ;
}
}
era rootNode = nuevo Nodo ( 3 ) ;
raízNodo. izquierda = nuevo Nodo ( 6 ) ;
raízNodo. bien = nuevo Nodo ( 9 ) ;
raízNodo. izquierda . izquierda = nuevo Nodo ( 12 ) ;
raízNodo. izquierda . bien = nuevo Nodo ( 15 ) ;
raízNodo. izquierda . bien . bien = nuevo Nodo ( 24 ) ;
raízNodo. bien . izquierda = nuevo Nodo ( 18 ) ;
raízNodo. bien . bien = nuevo Nodo ( 21 ) ;
mostrarNodos de hoja ( nodoraíz ) ;
La explicación del código anterior está escrita a continuación:
- Primero, cree un ' Nodo “clase que recibe un solo parámetro” valor ”que se establece como el valor del nodo recién creado, y los lados izquierdo y derecho se establecen en nulo. Tal como se hizo en el ejemplo anterior.
- A continuación, cree una función “ mostrarNodosHoja() ” que acepta un solo parámetro de “ nodoraíz ”. Este 'nodo raíz' se considera como el árbol binario y primero se verifica su vacío.
- Si el nodo no está vacío, entonces aparece una lista vacía llamada ' lista 'Se crea y el' nodoraíz El parámetro ' se inserta en él usando el botón ' empujar() ' método.
- Entonces el ' mientras() 'Se utiliza que se ejecuta hasta la duración de un' lista ”. Dentro del bucle, el elemento que reside en la parte inferior de un árbol o ' lista 'se elimina usando el' estallido() ' método.
- Ahora bien, la existencia del “ izquierda ' y ' bien Se marcan los lados de “rootNode”, y si ambos lados no existen, significa que no tiene ningún nodo secundario. Luego, este nodo se muestra en la pantalla y se identifica como un nodo hoja.
- Si hay un nodo en el lado izquierdo o derecho significa que tiene hijos. Entonces eso ' izquierda ' y ' bien 'El nodo es empujado hacia el' lista ”para continuar con la operación de encontrar el nodo hoja.
- Al final, cree un árbol binario personalizado pasando los valores de los nodos como parámetros para el ' Nodo ”Constructor de clases. Después de la creación, pase el árbol 'rootNode' como argumento para ' mostrarNodosHoja() ' función.
El resultado generado después de la compilación muestra que se imprimen los nodos de hoja del árbol proporcionado:
Consejo adicional: imprimir nodos de hoja de un árbol binario de derecha a izquierda
Para recuperar todos los nodos hoja que no tienen nodos secundarios en el ' bien ' a ' izquierda ” dirección, el enfoque recursivo es el más recomendado debido a su facilidad. Por ejemplo, se utilizará el mismo árbol analizado en las secciones anteriores para recuperar el nodo hoja, pero en el formato ' bien ' hacia ' izquierda ”Dirección, como se muestra a continuación:
clase Nodo{
constructor ( valor )
{
este . datos = valor ;
este . izquierda = nulo ;
este . bien = nulo ;
}
} ;
visualización de funcionesLeafNodes ( raíz )
{
si ( raíz == nulo )
{
devolver ;
}
si ( raíz. izquierda == nulo && raíz. bien == nulo )
{
documento. escribir ( raíz. datos + ' ' ) ;
devolver ;
}
si ( raíz. bien != nulo )
{
mostrarNodos de hoja ( raíz. bien ) ;
}
si ( raíz. izquierda != nulo )
{
mostrarNodos de hoja ( raíz. izquierda ) ;
}
}
era rootNode = nuevo Nodo ( 3 ) ;
raízNodo. izquierda = nuevo Nodo ( 6 ) ;
raízNodo. bien = nuevo Nodo ( 9 ) ;
raízNodo. izquierda . izquierda = nuevo Nodo ( 12 ) ;
raízNodo. izquierda . bien = nuevo Nodo ( 15 ) ;
raízNodo. izquierda . bien . bien = nuevo Nodo ( 24 ) ;
raízNodo. bien . izquierda = nuevo Nodo ( 18 ) ;
raízNodo. bien . bien = nuevo Nodo ( 21 ) ;
mostrarNodos de hoja ( nodoraíz ) ;
El código indicado anteriormente funciona así:
- Primero, la clase “ Nodo 'Se crea que utiliza el constructor predeterminado para agregar un nuevo nodo en el árbol, solo el enlace realizado en los ejemplos anteriores.
- A continuación, el “ mostrarNodosLead() Se crea una función que acepta un solo parámetro de “ nodoraíz ”. Este parámetro se verifica para el ' nulo 'condición a través del' si ' declaración.
- Si el nodo proporcionado no es verdadero, entonces es ' izquierda ' y ' bien 'Se comprueban los nodos laterales para ver si hay' nulo ' condición. Si ambos son nulos, entonces el nodo se identificará como ' hoja ”nodo e impreso en la página web.
- Después de eso, pase el ' bien ' y ' izquierda ” nodos del “ nodoraíz ' hacia ' mostrarNodosHoja() ' función.
- Asigne la posición de cada nodo creando las instancias usando el botón ' nuevo 'palabra clave y la' Nodo() ”constructor y especificando la posición como parámetro del constructor.
- El ' izquierda ' significa la posición izquierda del nodo raíz y el ' izquierda izquierda “Posición significa izquierda o izquierda. El mismo enfoque se aplica en el caso de “ bien ' y ' bien ”.
- Finalmente, pase el “ nodoraíz ' como argumento a favor del ' mostrarNodoHoja() ' función.
El resultado generado muestra que los nodos de hoja se imprimen en dirección de derecha a izquierda.
Se trata de imprimir todos los nodos hoja de un árbol binario en cualquier dirección deseada.
Conclusión
Para imprimir todos los nodos hoja de un árbol binario, cree una clase aleatoria que cree y asigne valores a los nodos del árbol. A continuación, cree una función aleatoria que acepte un único nodo del árbol en una jerarquía de arriba a abajo. Esta función contiene múltiples “ si ” condiciones que comprueban si el “ nodo 'no está vacío y no tiene nodos en el' izquierda ' y ' bien ' dirección, entonces ese nodo se considera como un ' hoja ”nodo y se muestra en la consola. Esta guía ha explicado el procedimiento para imprimir todos los nodos de hoja de un árbol binario de izquierda a derecha o de derecha a izquierda.