Cómo imprimir un BST en C ++

Question

Mi programa C ++ crea un árbol de búsqueda binario. Sé cómo imprimir los valores en pedidos anticipados, posteriores al pedido y en el pedido.

Sin embargo, quiero hacer algo un poco más difícil. Quiero imprimir los valores como se verían si alguien dibujara el árbol en papel. Tendría la raíz en el centro en la parte superior, es un niño izquierdo justo debajo y hacia la izquierda, y es un niño derecho justo debajo y hacia la derecha. El resto de los nodos serían dibujados en consecuencia.

¿Cómo puedo hacer eso?

Answer 1

Este artículo Contiene código para lo que necesita, parece:

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

Editar: ese sitio se desconectó

Aquí es otro Explorando otras opciones.

Answer 2

Aquí hay pseudocódigo aproximado para hacerlo. La idea básica es caminar por la capa de árbol por capa, imprimir todo el nodo en cada capa en una línea. Cada nodo se separa en el doble de espacio que los nodos debajo de él. Dado que el árbol no es todo de profundidad uniforme, está acolchado artificialmente con nodos virtuales para ocupar los espacios en blanco donde los nodos no existen.

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 espacio impreso es el ancho de un campo numérico. Supongamos que el árbol tiene profundidad d = 4. Entonces la impresión es así:

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

Una forma es usar GraphViz. Específicamente, use su programa "DOT", pero puede que la salida se vea exactamente como usted describe puede no ser posible.

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

Bueno, en una terminal es difícil ... ya que puede no encajar. Pero hay bibliotecas de dibujo gráfico que pueden hacer buenas fotos para usted. Hay Graphvis que es uno de los más populares.

EDITAR: Si realmente solo se reduce para imprimir texto, Graphvis tiene un lenguaje de marcado que un usuario puede pasar a Graphvis que a su vez hace las buenas imágenes.