Comment imprimer un BST en C++

Question

Mon programme C++ crée un arbre de recherche binaire. Je sais imprimer les valeurs en pré-commande, en post-commande et en ordre.

Cependant, je veux faire quelque chose d'un peu plus difficile. Je veux imprimer les valeurs telles qu'elles apparaîtraient si quelqu'un dessinait l'arbre sur papier. Il aurait la racine au centre en haut, c'est l'enfant gauche juste en dessous et à gauche de celui-ci, et c'est l'enfant juste en dessous et à droite de celui-ci. Le reste des nœuds serait dessiné en conséquence.

Comment puis-je faire cela?

Answer 1

This article contient un code pour ce dont vous avez besoin, il semble:

alt text http://www.cpp-programming.net/wp-content/uploads/2007/12/ascii_tree.jpg

Edit: ce site a été mis hors ligne

Voici another one explorer d'autres options.

Answer 2

Eh bien, dans un terminal, c'est dur ... car il peut ne pas s'adapter. Mais il existe des bibliothèques de dessin graphique qui peuvent faire de belles images pour vous. Il y a graphvis qui est l'un des plus populaires.

éditer: Si vous voulez vraiment juste imprimer du texte, graphvis a un langage de balisage qu'un utilisateur peut passer à graphvis qui à son tour fait les belles images.

Answer 3

Une façon est d'utiliser graphviz. Spécifiquement, utilisez son programme "point", mais obtenir la sortie pour ressembler exactement à ce que vous décrivez peut ne pas être possible.

Answer 4

Voici un pseudo-code approximatif pour le faire. L'idée de base est de parcourir l'arbre couche par couche, en imprimant tous les nœuds de chaque couche sur une ligne. Chaque nœud est séparé par deux fois plus d'espace que les nœuds situés en dessous. Puisque l'arbre n'a pas toute la profondeur uniforme, il est artificiellement rembourré avec des nœuds virtuels pour occuper les espaces vides où les nœuds n'existent pas.

measure the depth of the tree, call that D 
have two queues, called Q1 and Q2 
enque the top node of the tree in Q1 
for (i = D; --i>=0;){ 
    foreach node in Q1 { 

    on first iteration of this inner loop, print 2^i - 1 spaces, 
    else print 2^(i+1) - 1 spaces. 

    if node == null print blank 
    else print node.value 

    if node.left exists enque node.left in Q2 
    else enque null in Q2 

    if node.right exists enque node.right in Q2 
    else enque null in Q2 
    } 
    copy Q2 to Q1 
    clear Q2 
    print end-of-line 
} 

Chaque espace imprimé est la largeur d'un champ numérique. Supposons que l'arbre a une profondeur D = 4. Ensuite, l'impression se présente comme suit:

// it looks like this, and the space sequences are 
i = 3: -------n 7 
i = 2: ---n-------n 3 7 
i = 1: -n---n---n---n 1 3 3 3 
i = 0: n-n-n-n-n-n-n-n 0 1 1 1 1 1 1 1 

Answer 5

void print(node *p,int start) 
    { 
     start++; 
     if (p->right != NULL) 
     { 
      print(p->right,start); 
     } 
     for (int i = 0; i <= start; i++) 
     { 
      cout<<" "; 
     } 
     cout << p->value<<endl; 
     if (p->left != NULL) 
     { 
      print(p->left, start); 
     } 
    }