déplacement le long d'un arbre binaire non en java
J'ai un arbre qui n'est pas un arbre binaire et chaque nœud a plus de 2 enfants, je suis à la recherche d'un algorithme de traversée de l'arbre, je suis vraiment nouveau dans l'apprentissage de structure de données, je sais comment parcourir un arbre binaire, mais je me suis perdu quand il s'agit de traverser un non-arbre binaire .
Pouvait-on me donne un indice ?
viens de parcourir tous les enfants de gauche à droite, le reste est le même
Veuillez vous référer à ma réponse
oui, c'était ce que je voulais dire
Veuillez vous référer à ma réponse
oui, c'était ce que je voulais dire
OriginalL'auteur user2277918 | 2013-10-12
Vous devez vous connecter pour publier un commentaire.
Dans un non-arbre binaire, il y aura un
Vector
ou d'une autre structure qui a des références à tous les enfants. Faire une méthode récursive de la manière suivante:Quelque chose le long de ces lignes.
OriginalL'auteur Little Child
Vous aurez besoin d'utiliser la récursivité puisque vous ne pouvez pas déterminer combien d'enfants sont à chaque nœud (largeur) ou à quelle distance de l'arbre va (profondeur). Selon la façon dont vous souhaitez parcourir, vous pouvez utiliser La largeur de la première recherche ou La profondeur de la première recherche.
Il y a une tonne d'information sur ce sujet, afin de lui donner une tentative pour mettre en œuvre l'une de ces méthodes récursives et s'il vous plaît revenir si vous avez des problèmes le long du chemin!
OriginalL'auteur Joseph
Bien, lors de la traversée d'un arbre binaire, en précommande, vous visitez le nœud parent, puis, de manière récursive parcourir le sous-arbre gauche, puis récursivement parcourir le sous-arbre droit. Avec un arbre avec plus de deux enfants, vous parcourir récursivement les sous-arborescences dirigé par chacun des enfants. Vous devez faire des appels récursifs dans une boucle for.
You would do the recursive calls in a for loop
- de quelle façon pouvons-une boucle pour effectuer ces appels récursifs? Il est itératif, non?Jetez un oeil à mon pseudo-code 🙂
Merci, je comprends ce que Tarik signifiait pas - pas que le
for
boucle récursive, mais que les appels récursifs sont faites à l'intérieur d'une boucle for. Mon erreur, merci!code illustre ce que j'ai décrit. Notez que précommande, afinde et postorder sont parcours en profondeur d'abord traversals. Vous avez besoin d'utiliser une file d'attente pour faire une ampleur première traversée. Vous n'avez pas mentionné ce type de parcours que vous voulez faire.
BF de la traversée est un peu plus impliqué. L'OP ne fait pas mention de ce type de parcours est nécessaire. Si l'OP précise, je vais télécharger un extrait de code pour DF traversée. Ne devrait pas y avoir deux Vecteurs de droite et de gauche des enfants ?
OriginalL'auteur Tarik
L'algorithme de pré-post est la même que celle d'un arbre binaire.
Il n'y a pas une telle chose comme dans l'ordre de la traversée pour un arbre c'est à dire n'a aucun sens (sauf vous définir l'ordre)
OriginalL'auteur Cratylus