Récursion et recherche d'arbre dans C?

Question

Type de nouveaux arbres et fonctions récursives ....

Je connais les bases de la création d'une pile et de la création de fonctions récursives.

Je fais une recherche de traversée précommandée qui devrait renvoyer l'adresse d'un noeud dans une arborescence lorsque la valeur recherchée correspond à la valeur de ce noeud.

J'ai des problèmes avec la partie retour ... J'ai essayé de lire certaines choses sur les piles d'appels ... mais je ne comprends pas comment l'implémenter. Est-ce déjà là ou dois-je faire cette pile? Comment puis-je faire cette pile si je dois le faire? Je l'ai lu doit être proportionnelle à la hauteur de l'arbre ... Est-ce le meilleur moyen de trouver la hauteur de l'arbre pour faire une autre fonction qui fait cela?

Voici un code que j'ai écrit jusqu'à présent: Arbre et NodePtr est un pointeur vers un nœud ...

NodePtr SearchTree(int v, Tree T) 
{ 
    //printf(" %i \n", T->value); 

    if(T->value == v) 
    { 
     return T; 
    } 
    else 
    { 
     if(T->Left != NULL) SearchTree(value, T->Left); 
     if(T->Right != NULL) SearchTree(value, T->Right); 
    } 

    return NULL; 
} 

Answer 1

Tout d'abord, seerecursion. Retour, vous voulez retourner ce que les appels récursifs à SearchTree() retournent, parce que vous utilisez la récursivité pour déléguer le problème dans deux instances de vous-même, donc si vous n'obtenez pas votre valeur de retour en amont, rien ne peut pas peut-être travailler:

NodePtr SearchTree(int v, Tree t) 
{ 
    printf(" %i \n", t->value); 
    if (t->value == v) { 
     return t; 
    } else { 
     if (t->Left != NULL) { 
      NodePtr left = SearchTree(v, t->Left); 
      if (left != NULL) { 
       return left; 
      } 
     } 
     if (t->Right != NULL) { 
      return SearchTree(v, t->Right); 
     } 
    } 

    return NULL; 
} 

Answer 2

Vous n'avez pas à vous soucier de la pile d'appels; comment cela fonctionne est caché par le compilateur C, et à moins que vous ne cherchiez des arbres incroyablement profonds, cela ne vous dérangera pas.

Votre algorithme est plus ou moins correct, mais vous devez vérifier la valeur renvoyée à partir d'un appel récursif pour voir s'il est nul avant de visiter l'autre sous-arbre. Quelque chose comme:

if(T->Left != NULL) { NodePtr temp=SearchTree(value, T->Left); 
          if (temp !=NULL) return temp; 
         } 
    if(T->Right != NULL) return SearchTree(value, T->Right); 

Answer 3

Vous n'avez pas besoin de créer la pile d'appels vous-même. Il s'agit d'une structure de données gérée par l'environnement d'exécution dans lequel votre programme est exécuté, tel que votre système d'exploitation ou la machine virtuelle Java, si vous utilisez Java. Chaque fois qu'une fonction est appelée ses arguments et ses variables locales sont poussées sur la pile. Lorsque la fonction existe, ils sont désactivés.

En tant que programmeur, vous n'avez généralement pas à vous en soucier. Il est utile de savoir quelle est la pile d'appels pour comprendre exactement ce qui se passe pendant les appels de fonction récursifs (ou tout appel de fonction), ou pour comprendre d'où viennent les variables locales ou ce qui leur arrive après la sortie de votre fonction.

Answer 4

Tout le boîtier spécial dans la réponse de Ira Baxter et la réponse de Frédéric Hamidi suggère la conception n'est pas tout à fait raison:

NodePtr SearchTree(int v, NodePtr T) 
{ 
    if (T == NULL || T->value == v) 
     return T; 
    NodePtr R = SearchTree(v, T->Left); 
    if (R == NULL) 
     R = SearchTree(v, T->Right); 
    return R; 
} 

Ceci est, je vous soumets respectueusement, plus simple. Accordé, il fait un appel de plus de fonction en traitant avec un nœud de feuille NULL, mais il y a moins de tests 'if null' dispersés.

Aussi, je pense que l'argument de la fonction (nominalement un arbre dans l'original) est du même type qu'un NodePtr, donc j'ai choisi d'utiliser juste NodePtr et pas aussi Tree. Un arbre est représenté par le NodePtr qui est le nœud racine de l'arbre.