Trouver tous les nœuds d'un arbre binaire à un niveau spécifique (Interview de Requête)
Je veux dire à un niveau spécifique, PAS jusqu'à ce niveau spécifique. Quelqu'un pourrait-veuillez vérifier mes modifié algorithme BFS? (la plupart de ce qui est tirée de Wikipedia)
Queue levelorder(root, levelRequested){
int currentLevel = 0;
q = empty queue
q.enqueue(root)
while not q.empty do{
if(currentLevel==levelRequested)
return q;
node := q.dequeue()
visit(node)
if(node.left!=null || node.right!=null){
currentLevel++;
if node.left ≠ null
q.enqueue(node.left)
if node.right ≠ null
q.enqueue(node.right)
}
}
}
OriginalL'auteur John Roberts | 2012-11-12
Vous devez vous connecter pour publier un commentaire.
Je pense qu'une solution récursive serait beaucoup plus concis:
Initiale invocation ressemblerait à:
drill (root, 0, n, rqueue);
Oui, mais (clevel + 1), on obtient la même valeur (je ne vais pas changer clevel). D'autre part, si je n'ai clevel++, il serait faux...
Ah, je vois. Très bon.
OriginalL'auteur Asiri Rathnayake
Le problème avec votre algorithme est que les nœuds qui sont tous au même niveau, sont, à tort, l'augmentation du niveau de les compter.
Explication :
Niveau de l'ensemble de la racine à 0
Que vous ajouter des nœuds à tout niveau, de l'ensemble de leur niveau soit 1 de plus que le niveau de leur parent.
Une fois que vous obtenez tout nœud qui a le numéro de niveau égal au niveau du nombre que vous avez besoin, simple sortir de BFS, et de vidage de tous les nœuds dans la file d'attente derrière le nœud courant qui ont le même numéro de niveau.
Veuillez voir les commentaires pour plus de détails.
Voici une solution :
Voici un exemple de sortie :
Si vous êtes intéressé, j'ai ajouté la fonction de mon générique des arbres de la mise en œuvre ici. Vous trouverez un grand nombre d'arbres opérations de référence (miroir, la hauteur, la jolie impression, etc).
OriginalL'auteur axiom