La rappresentazione visiva dei concetti discussi è mostrata nella figura seguente:
Questa guida spiega il processo di stampa di tutti i nodi foglia di un albero binario coprendo le sezioni menzionate di seguito:
- Come identificare i nodi fogliari?
- Come stampare tutti i nodi foglia di un albero binario da sinistra a destra in JavaScript?
- Suggerimento bonus: stampa dei nodi foglia di un albero binario dalla direzione da destra a sinistra
- Conclusione
Come identificare i nodi fogliari?
IL ' foglia I nodi ' sono quelli che non hanno nodi figli o, per essere specifici, che hanno il ' altezza ' Di ' 0 ”. Se il nodo ha un ' altezza ' più grande di ' 0 ' allora quel nodo può essere il nodo interno o il nodo radice. IL ' foglia ' I nodi vengono solitamente riportati indietro per identificare la fonte originale da cui viene generato questo nodo. Viene utilizzato principalmente negli algoritmi di ricerca o di ricerca degli errori per trovare la causa di un errore o di un problema.
Come stampare tutti i nodi foglia di un albero binario da sinistra a destra in JavaScript?
Ci sono due approcci” ricorsivo ' E ' iterativo ' per selezionare tutti i nodi foglia disponibili nell'albero binario fornito nella ' Sinistra ' A ' Giusto 'direzione. L'implementazione pratica di questi approcci è dimostrata nelle sezioni seguenti:
- Stampa ricorsivamente tutti i nodi foglia di un albero binario da sinistra a destra
- Stampa tutti i nodi foglia di un albero binario utilizzando l'approccio iterativo
Metodo 1: stampa ricorsivamente tutti i nodi foglia di un albero binario da sinistra a destra
L'approccio ricorsivo seleziona tutti i nodi in a algoritmo di ricerca in profondità modo che attraversa prima tutti i nodi del lato sinistro, poi il nodo centrale e infine i nodi del lato destro. Questa operazione viene eseguita ricorsivamente per ogni nodo e quando non è più necessario attraversare il “ foglia 'i nodi vengono identificati. Per comprendere meglio questo concetto, visitare lo snippet di codice seguente:
classe Nodo{
costruttore ( )
{
Questo . contenuto = 0 ;
Questo . Sinistra = nullo ;
Questo . Giusto = nullo ;
}
} ;
dove displayLeafNodes = ( rootNode ) =>
{
Se ( rootNode == nullo )
ritorno ;
Se ( rootNode. Sinistra == nullo && rootNode. Giusto == nullo )
{
documento. scrivere ( rootNode. contenuto + ' ' ) ;
ritorno ;
}
Se ( rootNode. Sinistra != nullo )
displayLeafNodes ( rootNode. Sinistra ) ;
Se ( rootNode. Giusto != nullo )
displayLeafNodes ( rootNode. Giusto ) ;
}
era sampleNode = ( val ) =>
{
era tempNode = nuovo Nodo ( ) ;
tempNode. contenuto = val ;
tempNode. Sinistra = nullo ;
tempNode. Giusto = nullo ;
ritorno tempNode ;
}
era rootNode = provNode ( 3 ) ;
rootNode. Sinistra = provNode ( 6 ) ;
rootNode. Giusto = provNode ( 9 ) ;
rootNode. Sinistra . Sinistra = provNode ( 12 ) ;
rootNode. Sinistra . Giusto = provNode ( quindici ) ;
rootNode. Sinistra . Giusto . Giusto = provNode ( 24 ) ;
rootNode. Giusto . Sinistra = provNode ( 18 ) ;
rootNode. Giusto . Giusto = provNode ( ventuno ) ;
displayLeafNodes ( rootNode ) ;
La spiegazione del blocco di codice sopra è riportata di seguito:
- Innanzitutto, crea una classe denominata ' nodo ”, che crea un nuovo nodo e imposta il suo valore su “ 0 ”. L'allegato ' Sinistra ' E ' Giusto ' i nodi laterali sono impostati su ' nullo ' per impostazione predefinita utilizzando il costruttore della classe.
- Quindi, definire un ' displayLeafNodes() ' funzione che accetta un singolo parametro di ' rootNode ”. Questo valore parametrico è considerato come il nodo attualmente selezionato di un albero binario.
- All'interno della funzione, il “ Se L'istruzione ' viene utilizzata per verificare se il ' rootNode ' è nullo o no. In caso di ' nullo ” l'ulteriore esecuzione si è interrotta per quel nodo. Nell’altro caso, il rootNode “ Sinistra ' E ' Giusto ' i nodi laterali vengono controllati per ' nullo ”. Se entrambi sono nulli, il valore di quello “ nodo 'viene stampato.
- Se la ' Sinistra ' O ' Giusto ' il nodo non è 'null', quindi passa quel lato del nodo al ' displayLeafNodes() ” per l'operazione ricorsiva.
- Definire una nuova funzione denominata ' provNode() ” che accetta il solo parametro “ val ”. All'interno della funzione crea una nuova istanza del ' Nodo 'classe denominata' tempNode ”. Assegnare il parametrico “ val ' come valore per la proprietà della classe ' contenuto ' e impostare ' Sinistra ' E ' Giusto ' nodi laterali a ' nullo 'per impostazione predefinita.
- Infine, crea un oggetto denominato ' rootNode ' per il ' provNode() ' e passa il valore del nodo come parametro della funzione. Crea i nodi laterali sinistro e destro aggiungendo il ' Sinistra ' E ' Giusto ' parole chiave con 'rootNode' e assegnare loro un valore utilizzando la stessa funzione ' provNode() ”.
- IL ' Sinistra ' indica la posizione sinistra del nodo radice e ' sinistra.sinistra La posizione ' significa che a sinistra di sinistra viene applicato lo stesso approccio nel caso di ' Giusto ' E ' Giusto '
- Dopo aver definito l'albero, passare 'rootNode' come argomento per ' displayLeadNodes() ” per selezionare e stampare tutti i nodi foglia dell'albero creato.
L'output generato dopo la compilazione conferma che il nodo foglia dell'albero fornito è stato recuperato e stampato sulla console:
Metodo 2: stampa tutti i nodi foglia di un albero binario utilizzando l'approccio iterativo
IL ' iterativo L'approccio ' è l'approccio più efficiente, utilizza il concetto di ' spingere ' E ' pop ' per selezionare ' foglia ' nodi. I punti chiave o il funzionamento di questo approccio sono indicati di seguito:
classe Nodo{
costruttore ( valore )
{
Questo . dati = valore ;
Questo . Sinistra = nullo ;
Questo . Giusto = nullo ;
}
} ;
dove displayLeafNodes = ( rootNode ) =>
{
Se ( ! rootNode )
ritorno ;
lasciamo elencare = [ ] ;
elenco. spingere ( rootNode ) ;
Mentre ( elenco. lunghezza > 0 ) {
rootNode = elenco [ elenco. lunghezza - 1 ] ;
elenco. pop ( ) ;
Se ( ! rootNode. Sinistra && ! rootNode. Giusto )
documento. scrivere ( rootNode. dati + ' ' ) ;
Se ( rootNode. Giusto )
elenco. spingere ( rootNode. Giusto ) ;
Se ( rootNode. Sinistra )
elenco. spingere ( rootNode. Sinistra ) ;
}
}
era rootNode = nuovo Nodo ( 3 ) ;
rootNode. Sinistra = nuovo Nodo ( 6 ) ;
rootNode. Giusto = nuovo Nodo ( 9 ) ;
rootNode. Sinistra . Sinistra = nuovo Nodo ( 12 ) ;
rootNode. Sinistra . Giusto = nuovo Nodo ( quindici ) ;
rootNode. Sinistra . Giusto . Giusto = nuovo Nodo ( 24 ) ;
rootNode. Giusto . Sinistra = nuovo Nodo ( 18 ) ;
rootNode. Giusto . Giusto = nuovo Nodo ( ventuno ) ;
displayLeafNodes ( rootNode ) ;
La spiegazione del codice sopra è scritta di seguito:
- Innanzitutto, crea un ' Nodo “classe che riceve un singolo parametro” valore ' che viene impostato come valore del nodo appena creato e i lati sinistro e destro sono impostati su null. Proprio come fatto nell'esempio sopra.
- Successivamente, crea una funzione “ displayLeafNodes() ' che accetta un singolo parametro di ' rootNode ”. Questo “rootNode” è considerato come l'albero binario e la sua vacuità viene prima verificata.
- Se il nodo non è vuoto, verrà visualizzato un elenco vuoto denominato ' elenco ' viene creato e il ' rootNode ' viene inserito al suo interno utilizzando il parametro ' spingere() ' metodo.
- Poi il ' Mentre() ' viene utilizzato che viene eseguito fino alla durata di un ' elenco ”. All'interno del ciclo, l'elemento che risiede alla base di un albero o ' elenco ' viene rimosso utilizzando il comando ' pop() ' metodo.
- Ora, l’esistenza del “ Sinistra ' E ' Giusto ' di 'rootNode' vengono selezionati e se entrambi i lati non esistono significa che non ha un nodo figlio. Quindi, questo nodo viene visualizzato sullo schermo e identificato come nodo foglia.
- Se c'è un nodo sul lato sinistro o destro significa che ha figli. Allora quello” Sinistra ' E ' Giusto 'il nodo viene inserito nel ' elenco ' per ulteriori operazioni di ricerca del nodo foglia.
- Alla fine, crea un albero binario personalizzato passando i valori del nodo come parametri per ' Nodo 'costruttore di classi. Dopo la creazione, passare l'albero 'rootNode' come argomento per ' displayLeafNodes() ' funzione.
L'output generato dopo la compilazione mostra che vengono stampati i nodi foglia dell'albero fornito:
Suggerimento bonus: stampa dei nodi foglia di un albero binario dalla direzione da destra a sinistra
Per recuperare tutti i nodi foglia che non hanno nodi figlio nel ' Giusto ' A ' Sinistra ', l'approccio ricorsivo è il più consigliato per la sua facilità. Ad esempio, lo stesso albero discusso nelle sezioni precedenti verrà utilizzato per recuperare il nodo foglia ma nella sezione ' Giusto ' al ' Sinistra ', come mostrato di seguito:
classe Nodo{
costruttore ( valore )
{
Questo . dati = valore ;
Questo . Sinistra = nullo ;
Questo . Giusto = nullo ;
}
} ;
visualizzazione della funzioneLeafNodes ( radice )
{
Se ( radice == nullo )
{
ritorno ;
}
Se ( radice. Sinistra == nullo && radice. Giusto == nullo )
{
documento. scrivere ( radice. dati + ' ' ) ;
ritorno ;
}
Se ( radice. Giusto != nullo )
{
displayLeafNodes ( radice. Giusto ) ;
}
Se ( radice. Sinistra != nullo )
{
displayLeafNodes ( radice. Sinistra ) ;
}
}
era rootNode = nuovo Nodo ( 3 ) ;
rootNode. Sinistra = nuovo Nodo ( 6 ) ;
rootNode. Giusto = nuovo Nodo ( 9 ) ;
rootNode. Sinistra . Sinistra = nuovo Nodo ( 12 ) ;
rootNode. Sinistra . Giusto = nuovo Nodo ( quindici ) ;
rootNode. Sinistra . Giusto . Giusto = nuovo Nodo ( 24 ) ;
rootNode. Giusto . Sinistra = nuovo Nodo ( 18 ) ;
rootNode. Giusto . Giusto = nuovo Nodo ( ventuno ) ;
displayLeafNodes ( rootNode ) ;
Il codice sopra indicato funziona in questo modo:
- Innanzitutto la classe” Nodo ” che utilizza il costruttore predefinito per aggiungere un nuovo nodo nell'albero proprio il collegamento fatto negli esempi precedenti.
- Successivamente, il “ displayLeadNodes() Viene creata la funzione ' che accetta un singolo parametro di ' rootNode ”. Questo parametro viene controllato per ' nullo ' condizione tramite il ' Se ' dichiarazione.
- Se il nodo fornito non è vero, allora è ' Sinistra ' E ' Giusto ' i nodi laterali vengono controllati per ' nullo ' condizione. Se entrambi sono nulli, il nodo verrà identificato come “ foglia ' nodo e stampato sulla pagina web.
- Successivamente, passa il ' Giusto ' E ' Sinistra ' nodi del ' rootNode ' al ' displayLeafNodes() ' funzione.
- Assegna la posizione di ciascun nodo creando le istanze utilizzando il comando “ nuovo ' e la parola chiave ' Nodo() ” costruttore e specificando la posizione come parametro del costruttore.
- IL ' Sinistra ' indica la posizione sinistra del nodo radice e ' sinistra.sinistra 'posizione significa sinistra o sinistra. Lo stesso approccio viene applicato nel caso di “ Giusto ' E ' Giusto ”.
- Infine, passa il “ rootNode ' come argomento a favore del ' displayNodoFoglia() ' funzione.
L'output generato mostra che i nodi foglia vengono stampati nella direzione da destra a sinistra.
Si tratta di stampare tutti i nodi foglia di un albero binario in qualsiasi direzione desiderata.
Conclusione
Per stampare tutti i nodi foglia di un albero binario, crea una classe casuale che crea e assegna valori ai nodi dell'albero. Successivamente, crea una funzione casuale che accetta un singolo nodo dell'albero in una gerarchia dall'alto verso il basso. Questa funzione contiene più “ Se ' condizioni che controllano se il ' nodo ' non è vuoto e non ha nodi nel ' Sinistra ' E ' Giusto ' direzione, allora quel nodo è considerato come ' foglia ' nodo e viene visualizzato sulla console. Questa guida ha spiegato la procedura per stampare tutti i nodi foglia di un albero binario da sinistra a destra o da destra a sinistra.