C++ imprimer un arbre de recherche binaire

Rien de mieux à faire que cette fête de Noël, j'ai donc décidé d'essayer de faire un arbre de recherche binaire. Je suis coincé avec la fonction d'impression. Comment la logique qui sous-tend-il? Depuis l'arbre est déjà de l'insérer dans un peu de l'ordre de tri, et je veux imprimer l'arbre de la plus petite des valeurs aux plus grands.

Donc j'ai besoin de voyager à l'extrême gauche de la branche de l'arbre pour imprimer la première valeur. Bon, alors après comment dois-je rappeler le chemin du retour, j'ai besoin d'enregistrer le nœud précédent? Une recherche dans wikipédia m'a donné une solution qui ils ont utilisé de la pile. Et les autres solutions que je ne comprenais pas comment ils ont fait, donc je pose la question ici en espérant que quelqu'un pourra m'éclairer.

Je me demande aussi mon insérer une fonction est OK. J'ai vu de l'autre solution étant plus petit.

void treenode::insert(int i)
{

   if(root == 0)
   {
      cout << "root" << endl;
      root = new node(i,root);
   }
   else
   {
      node* travel = root;
      node* prev;
      while(travel)
      {
         if(travel->value > i)
         {
            cout << "travel left" << endl;
            prev = travel;
            travel = travel->left;
         }
         else
         {
            cout << "travel right" << endl;
            prev = travel;
            travel = travel->right;
         }
      }
      //insert
      if(prev->value > i)
      {
         cout << "left" << endl;
         prev->left = new node(i);
      }
      else
      {
         cout << "right" << endl;
         prev->right = new node(i);
      }
   }

}

void treenode::print()
{

   node* travel = root;
   while(travel)
   {
      cout << travel->value << endl;
      travel = travel->left;
   }

}

InformationsquelleAutor starcorn | 2010-12-27

binary-tree c++traversal

1

Vous pouvez utiliser la récursivité (pseudo-code):
```
prin-tree(node):
   print-tree(left-subnode) if exists
   print(node-value)
   print-tree(right-subnode) if exists
...
print(root-of-tree)
```
- drôle de chose, il fonctionne. Pas si drôle, c'est que je ne la comprends pas... je déteste la récursivité...
- Si vous vous sentez de cette façon sur la récursivité, ma suggestion serait de déposer ce projet et jusqu'à l'écriture de programmes en Lisp pour un certain temps jusqu'à ce que vous êtes à l'aise avec elle. Il y a des raisons pour l'éviter, à l'occasion, mais pour être un véritable expert dans le développement de la récursivité doit être dans votre boîte à outils.
- pour les non initiés, la récursivité peut être un défi de taille à la plupart d'entre nous passer par là! Voici un moyen facile de comprendre la récursivité - le "crux" de un appel récursif n'est pas dans la récursivité lui-même, c'est plutôt dans la "fin des cas", viz., les parties du code à exécuter lorsque vous ne comptez pas faire un appel récursif. Commencez par essayer de comprendre les fonctions d'impression, à la différence de la version postorder, précommande et afinde. Une recherche rapide a montré jusqu'à cette page web cs.umd.edu/class/spring2002/cmsc214/Tutorial/recursion.html
InformationsquelleAutor crazylammer
0

La traditionnelle CS101 de chemin à parcourir un arbre binaire de faire quoi que ce soit (impression, recherche, insertion, etc.) est d'utiliser la récursivité. Ont l' (quoi que) contrôle de routine de son nœud actuel, puis si ce n'est pas celle qu'il recherche, appel lui-même avec la gauche et/ou droit de la sous-arborescence (si il y en a un).

Pour une belle discussion, avec psedocode, découvrez l'article de Wikipedia sur l'arbre transversal. Il montre même comment le faire sans la récursivité, qui correspondent à la façon dont vous avez l'insertion.

InformationsquelleAutor T.E.D.
0

Tout dépend de la définition de l'arbre. Si les nœuds ne contiennent pas de pointeurs pour le parent, alors vous devez utiliser une pile pour imprimer dans l'ordre transversal. La façon la plus simple serait d'écrire une fonction récursive pour utiliser la pile d'application. L'algorithme a déjà été montré avant, mais en gros:
```
in-order(node):
   in-order(node.left) if node.left not null
   process(node)
   in-order(node.right) if node.right not null
```
Si les nœuds de tenir des pointeurs pour le parent, alors vous pourriez écrire une version itérative, mais il n'est probablement pas la valeur de l'effort (pour faire autre chose que de la nourriture pour la pensée)

InformationsquelleAutor David Rodríguez - dribeas

Vous devez vous connecter pour publier un commentaire.