La representació visual dels conceptes tractats es mostra a la figura següent:
Aquesta guia explica el procés d'impressió de tots els nodes de fulla d'un arbre binari cobrint les seccions esmentades a continuació:
- Com identificar els nodes de fulla?
- Com imprimir tots els nodes de fulla d'un arbre binari d'esquerra a dreta en JavaScript?
- Consell addicional: impressió de nodes de fulla d'un arbre binari de dreta a esquerra
- Conclusió
Com identificar els nodes de fulla?
El ' full ' els nodes són els que no tenen nodes fills, o per ser específics que tenen el ' alçada ' de ' 0 ”. Si el node té un ' alçada ' més gran que ' 0 ” llavors aquest node pot ser el node intern o el node arrel. El ' full ” els nodes solen retrocedir per identificar la font original des d'on es genera aquest node. S'utilitza principalment en algorismes de cerca o de cerca d'errors per trobar la causa d'un error o problema.
Com imprimir tots els nodes de fulla d'un arbre binari d'esquerra a dreta en JavaScript?
Hi ha dos enfocaments' recursiu ' i ' iteratiu ' per seleccionar tots els nodes de fulla disponibles a l'arbre binari proporcionat a l'opció desitjada ' esquerra ' a ' dret ' direcció. La implementació pràctica d'aquests enfocaments es demostra a les seccions següents:
- Imprimeix tots els nodes de fulla d'un arbre binari d'esquerra a dreta de manera recursiva
- Imprimeix tots els nodes de fulla d'un arbre binari mitjançant l'enfocament iteratiu
Mètode 1: imprimiu tots els nodes de fulla d'un arbre binari d'esquerra a dreta de manera recursiva
L'enfocament recursiu selecciona tots els nodes en a algorisme de cerca en profunditat manera que primer travessa tots els nodes del costat esquerre, després el node central i els nodes del costat dret al final. Aquesta operació es realitza de forma recursiva per a cada node i quan no hi ha més travessa per la ' full ” s'identifiquen els nodes. Per entendre millor aquest concepte, visiteu el fragment de codi següent:
classe Node{
constructor ( )
{
això . contingut = 0 ;
això . esquerra = nul ;
això . dret = nul ;
}
} ;
on displayLeafNodes = ( rootNode ) =>
{
si ( rootNode == nul )
tornar ;
si ( rootNode. esquerra == nul && rootNode. dret == nul )
{
document. escriure ( rootNode. contingut + ' ' ) ;
tornar ;
}
si ( rootNode. esquerra != nul )
displayLeafNodes ( rootNode. esquerra ) ;
si ( rootNode. dret != nul )
displayLeafNodes ( rootNode. dret ) ;
}
era sampleNode = ( val ) =>
{
era tempNode = nou Node ( ) ;
tempNode. contingut = val ;
tempNode. esquerra = nul ;
tempNode. dret = nul ;
tornar tempNode ;
}
era rootNode = provNode ( 3 ) ;
rootNode. esquerra = provNode ( 6 ) ;
rootNode. dret = provNode ( 9 ) ;
rootNode. esquerra . esquerra = provNode ( 12 ) ;
rootNode. esquerra . dret = provNode ( 15 ) ;
rootNode. esquerra . dret . dret = provNode ( 24 ) ;
rootNode. dret . esquerra = provNode ( 18 ) ;
rootNode. dret . dret = provNode ( 21 ) ;
displayLeafNodes ( rootNode ) ;
A continuació s'explica l'explicació del bloc de codi anterior:
- Primer, creeu una classe anomenada ' node ”, que crea un nou node i estableix el seu valor a “ 0 ”. L'adjunt ' esquerra ' i ' dret ' els nodes laterals s'estableixen a ' nul ” per defecte utilitzant el constructor de classes.
- A continuació, definiu un ' displayLeafNodes() ” funció que accepta un únic paràmetre de “ rootNode ”. Aquest valor paramètric es considera com el node seleccionat actualment d'un arbre binari.
- Dins de la funció, el ' si ' s'utilitza per comprovar si el ' rootNode ” és nul o no. En el cas que ' nul ” l'execució posterior es va aturar per a aquest node. En l'altre cas, el rootNode ' esquerra ' i ' dret ' els nodes laterals estan comprovats per ' nul ”. Si tots dos són nuls, el valor d'aquest ' node ” s'imprimeix.
- Si el ' esquerra ' o ' dret ” el node no és “nul”, després passeu aquest costat del node al “ displayLeafNodes() ” funció per a l'operació recursiva.
- Definiu una nova funció anomenada ' provNode() ” que accepta el paràmetre únic de “ val ”. Dins de la funció, creeu una nova instància del ' Node 'classe anomenada' tempNode ”. Assigna el paramètric ' val ' com el valor de la propietat de la classe ' contingut ' i configureu el ' esquerra ' i ' dret 'nodes laterals a' nul ' per defecte.
- Finalment, creeu un objecte anomenat ' rootNode 'per al' provNode() ” i passa el valor del node com a paràmetre d'aquesta funció. Creeu els nodes laterals esquerre i dret afegint el ' esquerra ' i ' dret ” paraules clau amb el “rootNode” i assigneu-los un valor amb la mateixa funció “ provNode() ”.
- El ' esquerra ” significa la posició esquerra del node arrel i el “ esquerra.esquerra ” La posició significa que l'esquerra de l'esquerra s'aplica el mateix enfocament en el cas de “ dret ' i ' dret ”
- Després de definir l'arbre, passeu el 'rootNode' com a argument per al ' displayLeadNodes() ” funció per seleccionar i imprimir tots els nodes fulla de l'arbre creat.
La sortida generada després de la compilació confirma que el node fulla de l'arbre proporcionat s'ha recuperat i imprès a la consola:
Mètode 2: imprimiu tots els nodes de fulla d'un arbre binari mitjançant l'enfocament iteratiu
El ' iteratiu 'L'enfocament és l'enfocament més eficient, utilitza el concepte de ' empènyer ' i ' pop ' per seleccionar ' full ” nodes. Els punts clau o el funcionament d'aquest enfocament s'indiquen a continuació:
classe Node{
constructor ( valor )
{
això . dades = valor ;
això . esquerra = nul ;
això . dret = nul ;
}
} ;
on displayLeafNodes = ( rootNode ) =>
{
si ( ! rootNode )
tornar ;
deixar llista = [ ] ;
llista. empènyer ( rootNode ) ;
mentre ( llista. llargada > 0 ) {
rootNode = llista [ llista. llargada - 1 ] ;
llista. pop ( ) ;
si ( ! rootNode. esquerra && ! rootNode. dret )
document. escriure ( rootNode. dades + ' ' ) ;
si ( rootNode. dret )
llista. empènyer ( rootNode. dret ) ;
si ( rootNode. esquerra )
llista. empènyer ( rootNode. esquerra ) ;
}
}
era rootNode = nou Node ( 3 ) ;
rootNode. esquerra = nou Node ( 6 ) ;
rootNode. dret = nou Node ( 9 ) ;
rootNode. esquerra . esquerra = nou Node ( 12 ) ;
rootNode. esquerra . dret = nou Node ( 15 ) ;
rootNode. esquerra . dret . dret = nou Node ( 24 ) ;
rootNode. dret . esquerra = nou Node ( 18 ) ;
rootNode. dret . dret = nou Node ( 21 ) ;
displayLeafNodes ( rootNode ) ;
L'explicació del codi anterior està escrita a continuació:
- Primer, creeu un ' Node 'classe que rep un sol paràmetre' valor ” que s'estableix com el valor del node acabat de crear, i els costats esquerre i dret es defineixen com a nul. Tal com es fa a l'exemple anterior.
- A continuació, creeu una funció ' displayLeafNodes() ” que accepta un únic paràmetre de “ rootNode ”. Aquest 'rootNode' es considera com l'arbre binari i primer es comprova el seu buit.
- Si el node no està buit, una llista buida anomenada ' llista ' es crea i el ' rootNode ' s'insereix el paràmetre amb el ' empènyer () ” mètode.
- Aleshores el ' mentre() S'utilitza ' que s'executa fins a la durada d'un ' llista ”. Dins del bucle, l'element que resideix a la part inferior d'un arbre o ' llista ' s'elimina mitjançant el ' pop() ” mètode.
- Ara, l'existència de la ' esquerra ' i ' dret ” de “rootNode” està marcat, i si els dos costats no existeixen vol dir que no té cap node fill. Aleshores, aquest node es mostra a la pantalla i s'identifica com a node fulla.
- Si hi ha un node al costat esquerre o dret vol dir que té fills. Llavors això ' esquerra ' i ' dret El node ' s'empeny al ' llista ” per a més operacions de cerca del node fulla.
- Al final, creeu un arbre binari personalitzat passant els valors del node com a paràmetres per al ' Node ” constructor de classes. Després de la creació, passeu l'arbre 'rootNode' com a argument per al ' displayLeafNodes() ” funció.
La sortida generada després de la compilació mostra que s'imprimeixen els nodes fulla de l'arbre proporcionat:
Consell addicional: impressió de nodes de fulla d'un arbre binari de dreta a esquerra
Per recuperar tots els nodes fulla que no tinguin nodes fills al ' dret ' a ' esquerra ” direcció, l'enfocament recursiu és el més recomanable per la seva facilitat. Per exemple, el mateix arbre comentat a les seccions anteriors s'utilitzarà per recuperar el node fulla, però en el ' dret ' fins al ' esquerra ” direcció, tal com es mostra a continuació:
classe Node{
constructor ( valor )
{
això . dades = valor ;
això . esquerra = nul ;
això . dret = nul ;
}
} ;
funció displayLeafNodes ( arrel )
{
si ( arrel == nul )
{
tornar ;
}
si ( arrel. esquerra == nul && arrel. dret == nul )
{
document. escriure ( arrel. dades + ' ' ) ;
tornar ;
}
si ( arrel. dret != nul )
{
displayLeafNodes ( arrel. dret ) ;
}
si ( arrel. esquerra != nul )
{
displayLeafNodes ( arrel. esquerra ) ;
}
}
era rootNode = nou Node ( 3 ) ;
rootNode. esquerra = nou Node ( 6 ) ;
rootNode. dret = nou Node ( 9 ) ;
rootNode. esquerra . esquerra = nou Node ( 12 ) ;
rootNode. esquerra . dret = nou Node ( 15 ) ;
rootNode. esquerra . dret . dret = nou Node ( 24 ) ;
rootNode. dret . esquerra = nou Node ( 18 ) ;
rootNode. dret . dret = nou Node ( 21 ) ;
displayLeafNodes ( rootNode ) ;
El codi anterior funciona així:
- En primer lloc, la classe ' Node ” es crea que utilitza el constructor predeterminat per afegir un nou node a l'arbre només l'enllaç fet als exemples anteriors.
- A continuació, el ' displayLeadNodes() Es crea la funció que accepta un únic paràmetre de rootNode ”. Aquest paràmetre està verificat per a ' nul 'condició mitjançant el ' si ” declaració.
- Si el node proporcionat no és cert, llavors és ' esquerra ' i ' dret ' els nodes laterals estan comprovats per ' nul ” condició. Si tots dos són nuls, el node s'identificarà com a ' full ” node i imprès a la pàgina web.
- Després d'això, passa el ' dret ' i ' esquerra 'nodes de la' rootNode ' fins al ' displayLeafNodes() ” funció.
- Assigna la posició de cada node creant les instàncies utilitzant el ' nou ' i la paraula clau ' Node() ” constructor i especificant la posició com a paràmetre del constructor.
- El ' esquerra ” significa la posició esquerra del node arrel i el “ esquerra.esquerra ” posició significa esquerra o esquerra. El mateix enfocament s'aplica en el cas de ' dret ' i ' dret ”.
- Finalment, passa el ' rootNode ' com a argument per a ' displayLeafNode() ” funció.
La sortida generada mostra que els nodes de fulla s'imprimeixen en direcció de dreta a esquerra.
Es tracta d'imprimir tots els nodes de fulla d'un arbre binari en qualsevol direcció desitjada.
Conclusió
Per imprimir tots els nodes de fulla d'un arbre binari, creeu una classe aleatòria que creï i assigni valors als nodes de l'arbre. A continuació, creeu una funció aleatòria que accepti un sol node de l'arbre en una jerarquia de dalt a baix. Aquesta funció conté múltiples ' si ” condicions que comproven si el “ node ' no està buit i no té nodes a la ' esquerra ' i ' dret ”, llavors aquest node es considera com un “ full ” i es mostra a la consola. Aquesta guia ha explicat el procediment per imprimir tots els nodes de fulla d'un arbre binari d'esquerra a dreta o de dreta a esquerra.