Si encuentras algún problema en tu código o proyecto, recuerda probar siempre en un entorno de testing antes aplicar el código al proyecto final.
Solución:
Para imprimir un árbol de forma recursiva, debe pasar dos argumentos a su función de impresión:
- El nodo del árbol que se va a imprimir, y
- El nivel de sangría
Por ejemplo, puedes hacer esto:
void BinarySearchTree::postorder(tree_node* p, int indent=0)
if(p != NULL)
if(p->left) postorder(p->left, indent+4);
if(p->right) postorder(p->right, indent+4);
if (indent)
std::cout << std::setw(indent) << ' ';
cout<< p->data << "n ";
La llamada inicial debe ser postorder(root);
Si desea imprimir el árbol con la raíz en la parte superior, mueva cout a la cima de la if.
void btree::postorder(node* p, int indent)
if(p != NULL)
if(p->right)
postorder(p->right, indent+4);
if (indent)
std::cout << std::setw(indent) << ' ';
if (p->right) std::cout<<" /n" << std::setw(indent) << ' ';
std::cout<< p->key_value << "n ";
if(p->left)
std::cout << std::setw(indent) << ' ' <<" \n";
postorder(p->left, indent+4);
Con este árbol:
btree *mytree = new btree();
mytree->insert(2);
mytree->insert(1);
mytree->insert(3);
mytree->insert(7);
mytree->insert(10);
mytree->insert(2);
mytree->insert(5);
mytree->insert(8);
mytree->insert(6);
mytree->insert(4);
mytree->postorder(mytree->root);
llevaría a este resultado:
Nunca va a ser lo suficientemente bonito, a menos que uno retroceda un poco para volver a calibrar la salida de la pantalla. Pero uno puede emitir árboles binarios lo suficientemente bonitos de manera eficiente usando heurística: Dada la altura de un árbol, uno puede adivinar cuál es el ancho esperado y la disposición de los nodos a diferentes profundidades. Se necesitan algunas piezas para hacer esto, así que comencemos con las funciones de nivel superior primero para proporcionar contexto.
La bonita función de impresión:
// create a pretty vertical tree
void postorder(Node *p)
int height = getHeight(p) * 2;
for (int i = 0 ; i < height; i ++)
printRow(p, height, i);
El código anterior es fácil. La lógica principal está en la función printRow. Profundicemos en eso.
void printRow(const Node *p, const int height, int depth)
vector vec;
getLine(p, depth, vec);
cout << setw((height - depth)*2); // scale setw with depth
bool toggle = true; // start with left
if (vec.size() > 1)
for (int v : vec)
if (v != placeholder)
if (toggle)
cout << "/" << " ";
else
cout << "\" << " ";
toggle = !toggle;
cout << endl;
cout << setw((height - depth)*2);
for (int v : vec)
if (v != placeholder)
cout << v << " ";
cout << endl;
getLine() hace lo que cabría esperar: almacena todos los nodos con una profundidad igual dada en vec. Aquí está el código para eso:
void getLine(const Node *root, int depth, vector& vals)
if (depth <= 0 && root != nullptr)
vals.push_back(root->val);
return;
if (root->left != nullptr)
getLine(root->left, depth-1, vals);
else if (depth-1 <= 0)
vals.push_back(placeholder);
if (root->right != nullptr)
getLine(root->right, depth-1, vals);
else if (depth-1 <= 0)
vals.push_back(placeholder);
Ahora volvamos a printRow(). Para cada línea, establecemos el ancho de transmisión en función de la profundidad del árbol binario. Este formato será bueno porque, por lo general, cuanto más profundiza, más ancho se necesita. Digo típicamente porque en árboles degenerados, esto no se vería tan bonito. Siempre que el árbol esté más o menos equilibrado y sea pequeño (< 20 elementos), debería salir bien. Se necesita un marcador de posición para alinear correctamente los caracteres '/' y ''. Entonces, cuando se obtiene una fila a través de getLine(), insertamos el marcador de posición si no hay ningún nodo presente en la profundidad especificada. El marcador de posición se puede establecer en cualquier cosa como (1<<31) por ejemplo. Obviamente, esto no es sólido porque el marcador de posición podría ser un valor de nodo válido. Si un codificador tiene agallas y solo trabaja con decimales, se podría modificar el código para emitir cadenas convertidas en decimales a través de getLine() y usar un marcador de posición como "_". (Desafortunadamente, no soy tan programador :P)
El resultado de los siguientes elementos insertados en orden: 8, 12, 4, 2, 5, 15 es
8
/
4 12
/
2 5 15
getHeight() se deja al lector como ejercicio. 🙂 Incluso se podrían obtener mejores resultados actualizando retroactivamente el conjunto de nodos poco profundos en función de la cantidad de elementos en los nodos más profundos. Eso también se deja al lector como ejercicio.
Si eres capaz, tienes el poder dejar un post acerca de qué le añadirías a esta división.