Comment imprimer un BST en C ++

Question

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

Cependant, je veux faire quelque chose d'un peu plus difficile. Je veux imprimer les valeurs de la façon dont il ressemblerait si quelqu'un dessinait l'arbre sur papier. Il aurait la racine au centre en haut, il est de gauche à droite en dessous et à gauche, et c'est à droite à droite sous et à droite. Le reste des nœuds serait dessiné en conséquence.

Comment puis je faire ça?

Answer 1

Cet article Contient du code pour ce dont vous avez besoin, semble-t-il:

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

EDIT: Ce site a été hors ligne

Voici un autre Explorer d'autres options.

Answer 2

Voici un pseudo-code approximatif pour le faire. L'idée de base est de promener la couche d'arbre par couche, imprimant tout le nœud de chaque couche sur une seule ligne. Chaque nœud est séparé par deux fois plus d'espace que les nœuds en dessous. Étant donné que l'arbre n'est pas toute la profondeur uniforme, il est artificiellement rembourré de nœuds virtuels pour prendre 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 ait la profondeur d = 4. Ensuite, l'impression va comme ceci:

// 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 3

Une façon consiste à utiliser Graphviz. Plus précisément, utilisez son programme "DOT", mais faire en sorte que la sortie ressemble exactement comme vous le décrivez peut ne pas être possible.

Answer 4

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

Answer 5

well, in a terminal it's hard...since it may not fit. But there are graph drawing libraries out there that can make nice pictures for you. There is graphvis that is one of the most popular.

edit: if you really just wan to print text, graphvis has a markup language that a user can pass to graphvis that in turn makes the nice pictures.