Come stampare una BST in C ++

Question

Il mio programma C ++ crea un albero binario di ricerca. So come stampare i valori in pre-ordine, post-ordine, e in ordine.

Tuttavia, voglio fare qualcosa di un po 'più difficile. Voglio stampare i valori nel modo in cui sarebbero se qualcuno ha disegnato l'albero su carta. Avrebbe la radice al centro in alto, è figlio sinistro proprio sotto ed a sinistra di esso, ed è figlio destro proprio sotto ea destra di esso. Il resto dei nodi sarebbe stato redatto di conseguenza.

Come posso fare questo?

Answer 1

questo articolo contiene il codice per quello che ti serve, a quanto pare:

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

Modifica: quel sito è andato offline

Ecco un altro esplorare alcune altre opzioni.

Answer 2

Ecco approssimativo pseudo-codice per farlo. L'idea di base è a piedi l'albero layer-by-layer, la stampa tutto il nodo in ogni strato su una riga. Ogni nodo è separato da doppio dello spazio a tutti i nodi sotto di esso. Dal momento che l'albero non è tutto di profondità uniforme, è artificialmente imbottito con nodi virtuali a prendere gli spazi vuoti in cui non esistono nodi.

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
}

Ogni spazio che viene stampato è la larghezza di un campo numerico. Supponiamo che l'albero ha una profondità D = 4. Quindi la stampa va in questo modo:

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

Un modo è quello di utilizzare graphviz. In particolare, utilizzare il suo programma "punto", ma ottenere l'output a guardare esattamente come lei potrebbe non essere possibile.

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

bene, in un terminale è difficile ... dato che non può andare bene. Ma ci sono le librerie di disegno grafico là fuori che possono fare belle foto per voi. C'è GraphVis che è uno dei più popolari.

modifica: se davvero solo wan per stampare il testo, ha GraphVis un linguaggio di markup che un utente può passare a GraphVis questo a sua volta rende le belle foto.