Effectuer Largeur de Recherche récursive

Question

Disons que vous vouliez mettre en œuvre une vaste première recherche dans un arbre binaire de manière récursive. Comment vous y prendriez-vous?

Est-il possible en utilisant uniquement l'appel de la pile auxiliaire de stockage?

Answer 1

(Je suppose que c'est juste une sorte de pensée de l'exercice, ou même un truc devoirs/question d'entrevue, mais je suppose que je pourrais imaginer une étrange scénario où vous n'êtes pas autorisé un tas d'espace pour une raison quelconque [certains vraiment mauvais personnalisés du gestionnaire de mémoire? certains bizarre runtime/questions sur l'OS?] pendant que vous avez encore accès à la pile...)

Largeur de la première traversée utilise traditionnellement une file d'attente, pas une pile. La nature d'une file d'attente et une pile sont à peu près à l'opposé, donc, essayer d'utiliser la pile d'appel (qui est une pile, d'où le nom) en tant que mémoire auxiliaire (une file d'attente) est quasiment vouée à l'échec, sauf si vous êtes en train de faire quelque chose de ridicule avec la pile d'appel que vous ne devriez pas l'être.

De la même façon, la nature de la non-queue de récursivité vous essayez de mettre en œuvre consiste essentiellement à ajouter une pile à l'algorithme. De ce fait, il n'est plus l'ampleur de recherche est un arbre binaire, et donc le temps d'exécution et autres joyeusetés pour la traditionnelle BFS n'est plus totalement s'appliquer. Bien sûr, vous pouvez toujours trivialement tourner en boucle dans un appel récursif, mais ce n'est pas n'importe quelle sorte de significatif de la récursivité.

Cependant, il existe des moyens, comme l'a démontré par d'autres, pour mettre en œuvre quelque chose qui suit la sémantique de BFS à un certain coût. Si le coût de la comparaison est cher, mais le nœud de la traversée est bon marché, alors que @Simon Buchan , vous pouvez simplement exécuter un processus itératif en profondeur d'abord de recherche, qui ne traite que les feuilles. Cela signifie pas de file d'attente stockées dans le tas, seulement local, de profondeur variable, et les meules construite sur et sur sur la pile des appels de l'arbre est parcouru maintes et maintes fois. Et comme @Patrick noté, un arbre binaire soutenu par un tableau est généralement stocké dans la largeur de la première traversée de l'ordre de toute façon, donc une largeur tout d'abord de recherche sur qui serait trivial, aussi sans avoir besoin d'un auxiliaire de la file d'attente.

Answer 2

Si vous utilisez un tableau à l'arrière de l'arbre binaire, vous pouvez déterminer le prochain nœud algébriquement. si i est un nœud, puis de ses enfants peut être trouvé à l' 2i + 1 (pour le nœud de gauche) et en 2i + 2 (pour le droit de nœud). Un nœud proche voisin est donnée par i + 1, à moins d' i est une puissance de 2

Voici pseudocode pour une très naïve de la mise en œuvre de la largeur de recherche sur un tableau adossés à des binaires un arbre de recherche. Cela suppose un tableau de taille fixe et, par conséquent, une profondeur fixe de l'arbre. Il va regarder orphelins nœuds, et pourrait créer une grande grande pile.

bintree-bfs(bintree, elt, i)
    if (i == LENGTH)
        return false

    else if (bintree[i] == elt)
        return true

    else 
        return bintree-bfs(bintree, elt, i+1)        

Answer 3

Je ne pouvais pas trouver un moyen de le faire complètement récursive (sans auxiliaire de la structure des données). Mais si la file d'attente Q est passé par référence, alors vous pouvez avoir le suivant idiot queue fonction récursive:

BFS(Q)
{
  if (|Q| > 0)
     v <- Dequeue(Q)
     Traverse(v)
     foreach w in children(v)
        Enqueue(Q, w)    

     BFS(Q)
}

Answer 4

La méthode suivante a utilisé un algorithme DFS pour obtenir tous les nœuds de profondeur - qui est la même que faire de BFS pour ce niveau. Si vous trouvez la profondeur de l'arbre et de le faire pour tous les niveaux, les résultats seront même comme un BFS.

public void PrintLevelNodes(Tree root, int level)
        {
            if (root != null)
            {
                if (level == 0)
                {
                    Console.Write(root.Data);
                    return;
                }
                PrintLevelNodes(root.Left, level - 1);
                PrintLevelNodes(root.Right, level - 1);
            }
        }

for(int i =0; i< depth;i++)
   PrintLevelNodes(root,i);

Trouver de la profondeur de l'arbre est un morceau de gâteau.

  public int MaxDepth(Tree root)
            {
                if (root == null)
                    return 0;
                else
                    return Math.Max(MaxDepth(root.Left), MaxDepth(root.Right)) + 1;
            }

Answer 5

Le muet façon:

template<typename T>
struct Node { Node* left; Node* right; T value; };

template<typename T, typename P>
bool searchNodeDepth(Node<T>* node, Node<T>** result, int depth, P pred) {
    if (!node) return false;
    if (!depth) {
        if (pred(node->value)) {
            *result = node;
        }
        return true;
    }
    --depth;
    searchNodeDepth(node->left, result, depth, pred);
    if (!*result)
        searchNodeDepth(node->right, result, depth, pred);
    return true;
}

template<typename T, typename P>
Node<T>* searchNode(Node<T>* node, P pred) {
    Node<T>* result = NULL;
    int depth = 0;
    while (searchNodeDepth(node, &result, depth, pred) && !result)
        ++depth;
    return result;
}

int main()
{
    // a c   f
    //  b   e
    //    d
    Node<char*>
        a = { NULL, NULL, "A" },
        c = { NULL, NULL, "C" },
        b = { &a, &c, "B" },
        f = { NULL, NULL, "F" },
        e = { NULL, &f, "E" },
        d = { &b, &e, "D" };

    Node<char*>* found = searchNode(&d, [](char* value) -> bool {
        printf("%s\n", value);
        return !strcmp((char*)value, "F");
    });

    printf("found: %s\n", found->value);

    return 0;
}