La représentation visuelle des concepts discutés est présentée dans la figure ci-dessous :
Ce guide explique le processus d'impression de tous les nœuds feuilles d'un arbre binaire en couvrant les sections mentionnées ci-dessous :
- Comment identifier les nœuds feuilles ?
- Comment imprimer tous les nœuds feuilles d’un arbre binaire de gauche à droite en JavaScript ?
- Astuce bonus : impression des nœuds feuilles d'un arbre binaire de droite à gauche
- Conclusion
Comment identifier les nœuds feuilles ?
Le ' feuille ' Les nœuds sont ceux qui n'ont pas de nœuds enfants, ou pour être plus précis qui ont le ' hauteur ' de ' 0 ». Si le nœud a un « hauteur ' plus grand que ' 0 ' alors ce nœud peut être le nœud interne ou le nœud racine. Le ' feuille ' Les nœuds sont généralement retracés pour identifier la source d'origine à partir de laquelle ce nœud est généré. Il est principalement utilisé dans les algorithmes de recherche ou de recherche d’erreurs pour trouver la cause d’une erreur ou d’un problème.
Comment imprimer tous les nœuds feuilles d’un arbre binaire de gauche à droite en JavaScript ?
Il y a deux approches » récursif ' et ' itératif ' pour sélectionner tous les nœuds feuilles disponibles dans l'arborescence binaire fournie dans le ' souhaité gauche ' à ' droite ' direction. La mise en œuvre pratique de ces approches est démontrée dans les sections ci-dessous :
- Imprimer tous les nœuds feuilles d'un arbre binaire de gauche à droite de manière récursive
- Imprimer tous les nœuds feuilles d'un arbre binaire à l'aide de l'approche itérative
Méthode 1 : imprimer de manière récursive tous les nœuds feuilles d’un arbre binaire de gauche à droite
L'approche récursive sélectionne tous les nœuds d'un algorithme de recherche en profondeur d'abord manière qui traverse d'abord tous les nœuds du côté gauche, puis le nœud du milieu et les nœuds du côté droit à la fin. Cette opération est effectuée de manière récursive pour chaque nœud et lorsqu'il n'y a plus de parcours du ' feuille ' Les nœuds sont identifiés. Pour mieux comprendre ce concept, visitez l'extrait de code ci-dessous :
classe Nœud{
constructeur ( )
{
ce . contenu = 0 ;
ce . gauche = nul ;
ce . droite = nul ;
}
} ;
où displayLeafNodes = ( Noeud principal ) =>
{
si ( Noeud principal == nul )
retour ;
si ( Noeud principal. gauche == nul && Noeud principal. droite == nul )
{
document. écrire ( Noeud principal. contenu + ' ' ) ;
retour ;
}
si ( Noeud principal. gauche != nul )
displayLeafNodes ( Noeud principal. gauche ) ;
si ( Noeud principal. droite != nul )
displayLeafNodes ( Noeud principal. droite ) ;
}
était un nœud d'échantillon = ( Val ) =>
{
était tempNode = nouveau Nœud ( ) ;
tempNode. contenu = Val ;
tempNode. gauche = nul ;
tempNode. droite = nul ;
retour nœud temp ;
}
était le nœud racine = nœudprov ( 3 ) ;
Noeud principal. gauche = nœudprov ( 6 ) ;
Noeud principal. droite = nœudprov ( 9 ) ;
Noeud principal. gauche . gauche = nœudprov ( 12 ) ;
Noeud principal. gauche . droite = nœudprov ( quinze ) ;
Noeud principal. gauche . droite . droite = nœudprov ( 24 ) ;
Noeud principal. droite . gauche = nœudprov ( 18 ) ;
Noeud principal. droite . droite = nœudprov ( vingt-et-un ) ;
displayLeafNodes ( Noeud principal ) ;
L'explication du bloc de code ci-dessus est indiquée ci-dessous :
- Tout d’abord, créez une classe nommée « nœud », qui crée un nouveau nœud et définit sa valeur sur « 0 ». Le ci-joint « gauche ' et ' droite ' Les nœuds latéraux sont définis sur ' nul » par défaut en utilisant le constructeur de classe.
- Ensuite, définissez un « displayLeafNodes() ' Fonction qui accepte un seul paramètre de ' Noeud principal ». Cette valeur paramétrique est considérée comme le nœud actuellement sélectionné d'un arbre binaire.
- À l’intérieur de la fonction, le « si ' L'instruction est utilisée pour vérifier si le ' Noeud principal » est nul ou non. Dans le cas d ' nul ' La poursuite de l'exécution s'est arrêtée pour ce nœud. Dans l’autre cas, le rootNode « gauche ' et ' droite « les nœuds latéraux sont vérifiés » nul ». Si les deux sont nuls, la valeur de cela ' nœud » est imprimé.
- Si la ' gauche ' ou ' droite ' Le nœud n'est pas ' nul ', puis transmettez ce côté du nœud au ' displayLeafNodes() 'fonction pour l'opération récursive.
- Définir une nouvelle fonction nommée « nœudprov() ' qui accepte le seul paramètre de ' Val ». À l’intérieur de la fonction, créez une nouvelle instance du « Nœud 'classe nommée' nœud temp ». Attribuez le paramétrique ' Val ' comme valeur de la propriété de classe ' contenu » et définissez le « gauche ' et ' droite « nœuds latéraux vers » nul ' par défaut.
- Enfin, créez un objet nommé « Noeud principal ' pour le ' nœudprov() ' et transmettez la valeur du nœud comme paramètre de fonction. Créez les nœuds latéraux gauche et droit en ajoutant le « gauche ' et ' droite ' mots-clés avec le ' rootNode ' et attribuez-leur une valeur en utilisant la même fonction ' nœudprov() ».
- Le ' gauche ' désigne la position gauche du nœud racine et le ' gauche.gauche La position ' signifie à gauche de la même approche est appliquée dans le cas de ' droite ' et ' droite »
- Après avoir défini l'arborescence, transmettez le « rootNode » comme argument pour le « displayLeadNodes() ' Fonction pour sélectionner et imprimer tous les nœuds feuilles de l'arborescence créée.
La sortie générée après la compilation confirme que le nœud feuille de l'arborescence fournie a été récupéré et imprimé sur la console :
Méthode 2 : imprimer tous les nœuds feuilles d'un arbre binaire à l'aide de l'approche itérative
Le ' itératif ' L'approche ' est l'approche la plus efficace, elle utilise le concept de ' pousser ' et ' populaire » pour sélectionner le « feuille ' nœuds. Les points clés ou le fonctionnement de cette approche sont indiqués ci-dessous :
classe Nœud{
constructeur ( valeur )
{
ce . données = valeur ;
ce . gauche = nul ;
ce . droite = nul ;
}
} ;
où displayLeafNodes = ( Noeud principal ) =>
{
si ( ! Noeud principal )
retour ;
laissez la liste = [ ] ;
liste. pousser ( Noeud principal ) ;
alors que ( liste. longueur > 0 ) {
Noeud principal = liste [ liste. longueur - 1 ] ;
liste. populaire ( ) ;
si ( ! Noeud principal. gauche && ! Noeud principal. droite )
document. écrire ( Noeud principal. données + ' ' ) ;
si ( Noeud principal. droite )
liste. pousser ( Noeud principal. droite ) ;
si ( Noeud principal. gauche )
liste. pousser ( Noeud principal. gauche ) ;
}
}
était le nœud racine = nouveau Nœud ( 3 ) ;
Noeud principal. gauche = nouveau Nœud ( 6 ) ;
Noeud principal. droite = nouveau Nœud ( 9 ) ;
Noeud principal. gauche . gauche = nouveau Nœud ( 12 ) ;
Noeud principal. gauche . droite = nouveau Nœud ( quinze ) ;
Noeud principal. gauche . droite . droite = nouveau Nœud ( 24 ) ;
Noeud principal. droite . gauche = nouveau Nœud ( 18 ) ;
Noeud principal. droite . droite = nouveau Nœud ( vingt-et-un ) ;
displayLeafNodes ( Noeud principal ) ;
L'explication du code ci-dessus est écrite ci-dessous :
- Tout d’abord, créez un « Nœud « classe qui reçoit un seul paramètre » valeur ' qui est défini comme valeur du nœud nouvellement créé, et les côtés gauche et droit sont définis sur null. Tout comme dans l'exemple ci-dessus.
- Ensuite, créez une fonction ' displayLeafNodes() ' qui accepte un seul paramètre de ' Noeud principal ». Ce « rootNode » est considéré comme l’arbre binaire et sa vacuité est d’abord vérifiée.
- Si le nœud n'est pas vide, alors une liste vide nommée « liste ' est créé et le ' Noeud principal ' est inséré dedans à l'aide du paramètre ' pousser() ' méthode.
- Puis le ' alors que() ' est utilisé et s'exécute jusqu'à la durée d'un ' liste ». A l’intérieur de la boucle, l’élément résidant en bas d’un arbre ou « liste ' est supprimé à l'aide du ' populaire() ' méthode.
- Or, l’existence du « gauche ' et ' droite ' Les côtés de 'rootNode' sont cochés, et si les deux côtés n'existent pas, cela signifie qu'il n'a pas de nœud enfant. Ensuite, ce nœud est affiché sur l'écran et identifié comme nœud feuille.
- S'il y a un nœud sur le côté gauche ou droit, cela signifie qu'il a des enfants. Alors que « gauche ' et ' droite ' Le nœud est poussé dans le ' liste » pour une opération ultérieure de recherche du nœud feuille.
- En fin de compte, créez un arbre binaire personnalisé en passant les valeurs de nœud comme paramètres pour le « Nœud ' Constructeur de classe. Après la création, passez l'arborescence « rootNode » comme argument pour le « displayLeafNodes() ' fonction.
La sortie générée après la compilation montre que les nœuds feuilles de l'arborescence fournie sont imprimés :
Astuce bonus : impression des nœuds feuilles d'un arbre binaire de droite à gauche
Pour récupérer tous les nœuds feuilles qui n’ont pas de nœuds enfants dans le « droite ' à ' gauche », l’approche récursive est la plus recommandée en raison de sa facilité. Par exemple, le même arbre discuté dans les sections ci-dessus va être utilisé pour récupérer le nœud feuille mais dans le « droite ' au ' gauche ', comme indiqué ci-dessous :
classe Nœud{
constructeur ( valeur )
{
ce . données = valeur ;
ce . gauche = nul ;
ce . droite = nul ;
}
} ;
affichage de la fonctionLeafNodes ( racine )
{
si ( racine == nul )
{
retour ;
}
si ( racine. gauche == nul && racine. droite == nul )
{
document. écrire ( racine. données + ' ' ) ;
retour ;
}
si ( racine. droite != nul )
{
displayLeafNodes ( racine. droite ) ;
}
si ( racine. gauche != nul )
{
displayLeafNodes ( racine. gauche ) ;
}
}
était le nœud racine = nouveau Nœud ( 3 ) ;
Noeud principal. gauche = nouveau Nœud ( 6 ) ;
Noeud principal. droite = nouveau Nœud ( 9 ) ;
Noeud principal. gauche . gauche = nouveau Nœud ( 12 ) ;
Noeud principal. gauche . droite = nouveau Nœud ( quinze ) ;
Noeud principal. gauche . droite . droite = nouveau Nœud ( 24 ) ;
Noeud principal. droite . gauche = nouveau Nœud ( 18 ) ;
Noeud principal. droite . droite = nouveau Nœud ( vingt-et-un ) ;
displayLeafNodes ( Noeud principal ) ;
Le code indiqué ci-dessus fonctionne comme ceci :
- D’abord, la classe « Nœud ' est créé et utilise le constructeur par défaut pour ajouter un nouveau nœud dans l'arborescence uniquement le lien effectué dans les exemples ci-dessus.
- Ensuite, le « displayLeadNodes() ' La fonction est créée qui accepte un seul paramètre de ' Noeud principal ». Ce paramètre est vérifié pour le « nul » condition via le « si ' déclaration.
- Si le nœud fourni n'est pas vrai, alors c'est ' gauche ' et ' droite « les nœuds latéraux sont vérifiés » nul ' condition. Si les deux sont nuls, alors le nœud sera identifié comme un « feuille » et imprimé sur la page Web.
- Après cela, passez le ' droite ' et ' gauche « nœuds du » Noeud principal ' au ' displayLeafNodes() ' fonction.
- Attribuez la position de chaque nœud en créant les instances à l'aide du ' nouveau ' mot-clé et le ' Nœud() ' constructeur et en spécifiant la position comme paramètre constructeur.
- Le ' gauche ' désigne la position gauche du nœud racine et le ' gauche.gauche ' La position signifie gauche ou gauche. La même approche est appliquée dans le cas de « droite ' et ' droite ».
- Enfin, passez le « Noeud principal » comme argument pour le « displayLeafNode() ' fonction.
La sortie générée montre que les nœuds feuilles sont imprimés dans le sens de droite à gauche.
Il s’agit d’imprimer tous les nœuds feuilles d’un arbre binaire dans n’importe quelle direction souhaitée.
Concluasion
Pour imprimer tous les nœuds feuilles d'un arbre binaire, créez une classe aléatoire qui crée et attribue des valeurs aux nœuds de l'arbre. Ensuite, créez une fonction aléatoire qui accepte un seul nœud de l'arborescence dans une hiérarchie de haut en bas. Cette fonction contient plusieurs « si » conditions qui vérifient si le « nœud ' n'est pas vide et il n'a aucun nœud dans le ' gauche ' et ' droite ', alors ce nœud est considéré comme un ' feuille ' et s'affiche sur la console. Ce guide a expliqué la procédure d'impression de tous les nœuds feuilles d'un arbre binaire de gauche à droite ou de droite à gauche.