Chemin le plus court au chemin de la feuille

Question

Quel est le moyen le plus simple, en utilisant de préférence la récursivité, de rechercher le chemin racine-feuille le plus court dans un BST (arbre de recherche binaire). Java préféré, pseudo-code correct.

Merci!

Answer 1

Description générale:

Utilisez une recherche par la largeur d'abord (BFS) par opposition à un Recherche en profondeur d'abord (DFS) . Recherchez le premier nœud sans enfants.

En utilisant un DFS, vous pourriez avoir de la chance avec certaines arborescences d’entrée (mais il n’ya aucun moyen de savoir si vous avez eu de la chance, vous devez toujours effectuer une recherche dans tout l’arbre), mais l’utilisation de la méthode BFS est beaucoup plus rapide et vous pouvez trouver une solution. sans toucher tous les nœuds.

Pour trouver le chemin d'accès racine à feuille, vous pouvez suivre le premier nœud sans enfant trouvé jusqu'à la racine à l'aide de la référence parent. Si vous n'avez pas de référence parent stockée dans chaque nœud, vous pouvez garder trace des nœuds parents au fur et à mesure que vous redressez. Si vous avez votre liste en ordre inverse, vous pouvez tout placer sur une pile, puis la supprimer.

Pseudo-code:

Le problème est très simple. voici un pseudo-code pour trouver la plus petite longueur:

1. Placez le noeud racine dans la file d'attente.

Répétez l'opération tant que la file d'attente n'est pas vide et qu'aucun résultat n'a été trouvé:

2. Extrait un noeud du début de la file d'attente et vérifie s'il n'a pas d'enfants. S'il n'a pas d'enfants vous avez-vous trouvé le chemin le plus court?
3. Sinon, placez tous les enfants (gauche, droite) dans la file d'attente.

Recherche de tous les chemins les plus courts:

Pour 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 poursuivriez l’algorithme pour tous les nœuds de la file avec la même profondeur.

Alternative:

Si vous préférez utiliser un système de fichiers DFS, vous devez effectuer une recherche dans l’arbre entier pour trouver le chemin le plus court. Mais ceci pourrait être optimisé en conservant une valeur pour le plus court jusqu'à présent et en ne vérifiant que la profondeur des futurs nœuds jusqu'à ce que vous trouviez un nouveau plus court ou jusqu'à ce que vous atteigniez le plus court jusqu'à présent. Le BFS est une bien meilleure solution cependant.

Answer 2

C’est en C ++, mais c’est tellement simple que vous pouvez le convertir facilement. Il suffit de changer min en max pour obtenir la profondeur maximale de l’arbre.

int TreeDepth(Node* p)
{
    return (p == NULL) ? 0 : min(TreeDepth(p->LeftChild), TreeDepth(p->RightChild)) + 1;
}

Juste pour expliquer ce que cela fait, il compte à partir du nœud feuille (il renvoie 0 lorsqu'il trouve une feuille) et compte jusqu'à la racine. Faire cela pour les côtés gauche et droit de l'arbre et prendre le minimum vous donnera le chemin le plus court.

Answer 3

La première recherche en largeur est exactement optimale en termes de nombre de sommets visités. Vous devez visiter chacun des sommets que vous visiteriez de manière approfondie afin de prouver que vous avez la feuille la plus proche!

Toutefois, si vous êtes mandaté pour utiliser la récursivité, l'approche de Mike Thompson est presque celle qu'il convient d'utiliser - et elle est légèrement plus simple.

TD(p) is
  0 if p is NULL (empty tree special case)
  1 if p is a leaf (p->left == NULL and p->right == NULL)
  min(TD(p->left), TD(p->right)) if p is not a leaf 

Answer 4

static int findCheapestPathSimple (racine TreeNode) {

if(root==null){
    return 0; 
}

return root.data+Math.min(findCheapestPathSimple(root.left), findCheapestPathSimple(root.right));

}