C++ imprimer un arbre de recherche binaire

Question

Rien de mieux pour faire les vacances 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 devrait fonctionner la logique derrière cela? Puisque l'arbre l'insère déjà dans un ordre quelque peu trié, et je veux imprimer l'arbre des plus petites valeurs au plus grand. J'ai donc besoin de voyager jusqu'à la branche la plus à gauche de l'arbre pour imprimer la première valeur. Bon, alors après, comment est-ce que je me souviens du chemin de retour, ai-je besoin de sauvegarder le nœud précédent? Une recherche dans wikipedia m'a donné une solution qu'ils utilisaient pile. Et d'autres solutions que je n'arrivais pas à comprendre comment ils l'ont fait, alors je demande ici plutôt que quelqu'un puisse m'éclairer.

Je me demande également si ma fonction d'insertion est OK. J'ai vu la solution d'un autre être plus petite.

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; 
    } 

} 

Answer 1

Vous pouvez utiliser récursion (pseudo-code):

prin-tree(node): 
    print-tree(left-subnode) if exists 
    print(node-value) 
    print-tree(right-subnode) if exists 
... 
print(root-of-tree) 

Answer 2

La façon traditionnelle CS101 pour traverser un arbre binaire à faire quoi que ce soit (impression, recherche, insertion, etc.) est d'utiliser la récursivité. Demandez à la routine (quelquechose) de vérifier son nœud actuel, et si ce n'est pas celui qu'elle recherche, appelez-la avec la sous-arborescence gauche et/ou droite (s'il y en a une).

Pour une discussion agréable, avec psedocode, consultez the Wikipedia article on tree traversal. Il montre même comment le faire sans récursion, ce qui correspondrait à la façon dont vous avez fait l'insertion.

Answer 3

Tout dépend de la définition de l'arbre. Si les nœuds ne contiennent pas de pointeurs vers le parent, vous devez utiliser une pile pour imprimer le transversal dans l'ordre. Le plus simple serait d'écrire une fonction récursive pour utiliser la pile de l'application. L'algorithme a déjà été montré avant, mais essentiellement:

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 tiennent des pointeurs au parent, alors vous pourriez écrire une version itérative, mais il ne vaut probablement pas l'effort (pour quoi que ce soit, mais la nourriture pour la pensée