Como imprimir um BST em C ++

Question

Meu programa C ++ cria uma árvore de pesquisa binária. Eu sei como imprimir os valores em pré-encomenda, pós-ordem e em ordem.

No entanto, quero fazer algo um pouco mais difícil. Quero imprimir os valores da maneira que eles pareceriam se alguém desenhasse a árvore no papel. Ele teria a raiz no centro no topo, fica à direita à direita e à esquerda, e é o filho certo para baixo e à direita. O restante dos nós seria desenhado de acordo.

Como eu posso fazer isso?

Answer 1

Este artigo Contém código para o que você precisa, ao que parece:

TEXTO DE ALT HTTP://www.cpp-programming.net/wp-content/uploads/2007/12/ascii_tree.jpg

Editar: esse site ficou offline

Aqui está outro explorando algumas outras opções.

Answer 2

Aqui está o pseudo-código aproximado para fazê-lo. A idéia básica é andar na camada de árvore, imprimindo todo o nó em cada camada em uma linha. Cada nó é separado por duas vezes mais espaço do que os nós abaixo dele. Como a árvore não é toda de profundidade uniforme, ela é artificialmente acolchoada com nós virtuais para pegar os espaços em branco onde os nós não existem.

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
}

Cada espaço impresso é a largura de um campo numérico. Suponha que a árvore tenha profundidade d = 4. Então a impressão é assim:

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

Uma maneira é usar o GraphViz. Especificamente, use seu programa "Dot", mas obter a saída para parecer exatamente como você descreve pode não ser possível.

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

Bem, em um terminal, é difícil ... já que pode não se encaixar. Mas existem bibliotecas de desenho de gráficos por aí que podem fazer boas fotos para você. Há graphvis que é um dos mais populares.

EDIT: Se você realmente acabou de imprimir o texto, o Graphvis possui um idioma de marcação que um usuário pode passar para o Graphvis que, por sua vez, faz as fotos agradáveis.