Racine la plus courte au chemin de la feuille
Quel est le moyen le plus facile, de préférence en utilisant la récursivité, pour trouver le plus court chemin de la racine à la feuille de chemin d'accès dans un BST (Binaire un Arbre de Recherche). Java préférées, des pseudo-code correct.
Merci!
source d'informationauteur Sev
Vous devez vous connecter pour publier un commentaire.
Description générale:
Utiliser un En largeur d'abord de recherche (BFS) par opposition à un Depth-first search (DFS). Trouver le premier nœud sans enfants.
L'aide d'un DFS vous pourriez avoir de la chance sur certains arbres (mais il n'y a aucun moyen de savoir tu as de la chance si vous avez encore besoin de rechercher dans l'ensemble de l'arbre), mais à l'aide de la BFS méthode est beaucoup plus rapide et vous pouvez trouver une solution sans toucher à tous les nœuds.
Pour trouver la racine à la feuille de chemin d'accès, vous pouvez suivre le premier trouvé sans enfant nœud de tout le chemin du retour jusqu'à la racine, en utilisant le parent de référence. Si vous n'avez pas le parent de référence stockées dans chaque nœud, vous pouvez garder une trace de nœuds parents comme vous recurse vers le bas. Si vous avez votre liste dans l'ordre inverse de pousser le tout sur une pile puis de la pop.
Pseudo-code:
Le problème est très simple, voici le pseudo-code pour trouver la plus petite longueur:
Répéter alors que la file d'attente n'est pas vide, et aucun résultat n'a été trouvé:
sont fait, vous avez trouvé le chemin le plus court.
La recherche de tous les plus courts chemins:
De trouver tous les chemins les plus courts vous pouvez stocker la profondeur du nœud avec le nœud à l'intérieur de la file d'attente. Ensuite, vous continuez l'algorithme pour tous les nœuds dans la file d'attente avec la même profondeur.
Alternative:
Si, au contraire, vous avez décidé d'utiliser un DFS, vous devez rechercher l'ensemble de l'arborescence pour trouver le chemin le plus court. Mais cela pourrait être optimisé en gardant une valeur pour le plus court jusqu'à présent, et la seule vérification de la profondeur de l'avenir des nœuds jusqu'à ce que vous trouver un nouveau plus court, ou jusqu'à ce que vous atteignez le plus court jusqu'à présent. Le BFS est une bien meilleure solution.
C'est en C++, mais il est si simple, vous pouvez convertir facilement. Il suffit de changer de min à max pour obtenir le maximum de profondeur de l'arbre.
Juste pour expliquer ce que c'est, ce faisant, il est à compter à partir de la feuille de nœud (elle renvoie 0 quand il trouve une feuille) et compte jusqu'à la racine. Faire cela pour les côtés droit et gauche de l'arbre et en prenant le minimum de vous donner le chemin le plus court.
Largeur de recherche est exactement optimal en termes de nombre de sommets visités. Vous avez à visiter tous les sommets que vous auriez une visite dans une largeur de recherche juste pour prouver que vous avez le plus proche de la feuille!
Toutefois, si vous disposez d'un mandat d'utiliser la récursivité, Mike Thompson approche est presque le droit d'utiliser-et qui est un peu plus simple.
static int findCheapestPathSimple(TreeNode racine){
}