Después de de nuestra prolongada búsqueda de información pudimos resolver este atascamiento que suelen tener muchos usuarios. Te compartimos la solución y deseamos servirte de mucha apoyo.
Solución:
Aunque no es exactamente lo que pediste, imprimir árboles horizontalmente es mucho más sencillo. Y especialmente en el caso de árboles grandes, creo que esta es la mejor forma de representación.
└──8
├──5
│ ├──2
│ └──6
└──10
├──9
└──11
Siguiendo las raíces del código C ++ en esta implementación de Java.
void printBT(const std::string& prefix, const BSTNode* node, bool isLeft)
if( node != nullptr )
std::cout << prefix;
std::cout << (isLeft ? "├──" : "└──" );
// print the value of the node
std::cout << node->m_val << std::endl;
// enter the next tree level - left and right branch
printBT( prefix + (isLeft ? "│ " : " "), node->m_left, true);
printBT( prefix + (isLeft ? "│ " : " "), node->m_right, false);
void printBT(const BSTNode* node)
printBT("", node, false);
// pass the root node of your binary tree
printBT(root);
A continuación se muestra un ejemplo de código que crea una representación basada en texto de un árbol binario. Esta demostración utiliza una clase de árbol binario mínimamente útil (BinTree), con una huella pequeña, solo para evitar aumentar el tamaño del ejemplo.
Sus funciones de miembro de representación de texto son más serias, utilizando iteración en lugar de recursividad, como se encuentra en otras partes de la clase.
Esto hace su trabajo en tres pasos, primero un vector de filas de string los valores se juntan.
Luego, esto se usa para formatear líneas de cadenas de texto que representan el árbol.
Luego, las cuerdas se limpian y se tiran a cout.
Como beneficio adicional, la demostración incluye una función de “árbol aleatorio”, para horas de entretenimiento sin parar.
#include
#include
#include
#include
#include
#include
using std::vector;
using std::string;
using std::cout;
template
class BinTree
struct Node
T value;
Node *left,*right;
Node() : left(nullptr),right(nullptr)
Node(const T& value) :value(value),left(nullptr),right(nullptr)
// stack-abusing recursion everywhere, for small code
~Node() delete left; delete right;
int max_depth() const
const int left_depth = left ? left->max_depth() : 0;
const int right_depth = right ? right->max_depth() : 0;
return (left_depth > right_depth ? left_depth : right_depth) + 1;
;
Node *root;
public:
BinTree() : root(nullptr)
~BinTree() delete root;
int get_max_depth() const return root ? root->max_depth() : 0;
void clear() delete root; root = nullptr;
void insert()
template
void insert(const T& value, Args...more)
if(!root)
root = new Node(value);
else
Node* p = root;
for(;;)
if(value == p->value) return;
Node* &pchild = value < p->value ? p->left : p->right;
if(!pchild)
pchild = new Node(value);
break;
p = pchild;
insert(more...);
struct cell_display
string valstr;
bool present;
cell_display() : present(false)
cell_display(std::string valstr) : valstr(valstr), present(true)
;
using display_rows = vector< vector< cell_display > >;
// The text tree generation code below is all iterative, to avoid stack faults.
// get_row_display builds a vector of vectors of cell_display structs
// each vector of cell_display structs represents one row, starting at the root
display_rows get_row_display() const
// start off by traversing the tree to
// build a vector of vectors of Node pointers
vector traversal_stack;
vector< std::vector > rows;
if(!root) return display_rows();
Node *p = root;
const int max_depth = root->max_depth();
rows.resize(max_depth);
int depth = 0;
for(;;)
// Max-depth Nodes are always a leaf or null
// This special case blocks deeper traversal
if(depth == max_depth-1)
rows[depth].push_back(p);
if(depth == 0) break;
--depth;
continue;
// First visit to node? Go to left child.
if(traversal_stack.size() == depth)
rows[depth].push_back(p);
traversal_stack.push_back(p);
if(p) p = p->left;
++depth;
continue;
// Odd child count? Go to right child.
if(rows[depth+1].size() % 2)
p = traversal_stack.back();
if(p) p = p->right;
++depth;
continue;
// Time to leave if we get here
// Exit loop if this is the root
if(depth == 0) break;
traversal_stack.pop_back();
p = traversal_stack.back();
--depth;
// Use rows of Node pointers to populate rows of cell_display structs.
// All possible slots in the tree get a cell_display struct,
// so if there is no actual Node at a struct's location,
// its boolean "present" field is set to false.
// The struct also contains a string representation of
// its Node's value, created using a std::stringstream object.
display_rows rows_disp;
std::stringstream ss;
for(const auto& row : rows)
rows_disp.emplace_back();
for(Node* pn : row)
if(pn)
ss << pn->value;
rows_disp.back().push_back(cell_display(ss.str()));
ss = std::stringstream();
else
rows_disp.back().push_back(cell_display());
return rows_disp;
// row_formatter takes the vector of rows of cell_display structs
// generated by get_row_display and formats it into a test representation
// as a vector of strings
vector row_formatter(const display_rows& rows_disp) const
using s_t = string::size_type;
// First find the maximum value string length and put it in cell_width
s_t cell_width = 0;
for(const auto& row_disp : rows_disp)
for(const auto& cd : row_disp)
if(cd.present && cd.valstr.length() > cell_width)
cell_width = cd.valstr.length();
// make sure the cell_width is an odd number
if(cell_width % 2 == 0) ++cell_width;
// formatted_rows will hold the results
vector formatted_rows;
// some of these counting variables are related,
// so its should be possible to eliminate some of them.
s_t row_count = rows_disp.size();
// this row's element count, a power of two
s_t row_elem_count = 1 << (row_count-1);
// left_pad holds the number of space charactes at the beginning of the bottom row
s_t left_pad = 0;
// Work from the level of maximum depth, up to the root
// ("formatted_rows" will need to be reversed when done)
for(s_t r=0; r& rows)
if(!rows.size()) return;
auto min_space = rows.front().length();
for(const auto& row : rows)
auto i = row.find_first_not_of(' ');
if(i==string::npos) i = row.length();
if(i == 0) return;
if(i < min_space) min_space = i;
for(auto& row : rows)
row.erase(0, min_space);
// Dumps a representation of the tree to cout
void Dump() const
const int d = get_max_depth();
// If this tree is empty, tell someone
if(d == 0)
cout << " n";
return;
// This tree is not empty, so get a list of node values...
const auto rows_disp = get_row_display();
// then format these into a text representation...
auto formatted_rows = row_formatter(rows_disp);
// then trim excess space characters from the left sides of the text...
trim_rows_left(formatted_rows);
// then dump the text to cout.
for(const auto& row : formatted_rows)
std::cout << ' ' << row << 'n';
;
int main()
BinTree bt;
// Build OP's tree
bt.insert(8,5,2,6,10,9,11);
cout << "Tree from OP:nn";
bt.Dump();
cout << "nn";
bt.clear();
// Build a random tree
// This toy tree can't balance, so random
// trees often look more like linked lists.
// Just keep trying until a nice one shows up.
std::random_device rd;
std::mt19937 rng(rd());
int MaxCount=20;
int MaxDepth=5;
const int Min=0, Max=1000;
std::uniform_int_distribution dist(Min,Max);
while(MaxCount--)
bt.insert(dist(rng));
if(bt.get_max_depth() >= MaxDepth) break;
cout << "Randomly generated tree:nn";
bt.Dump();
Un ejemplo de la salida:
Tree from OP:
8
/
/
/
5 10
/ /
2 6 9 11
Randomly generated tree:
703
/
/
/
/
/
/
/
/
/
/
/
/
/
/
/
137 965
/ /
/ /
/ /
/ /
/ /
/ /
/ /
41 387 786
/ /
/ /
/ /
95 382 630 726 813
841
Escribí una impresora bonita de árbol arbitrario como parte de la autoeducación de algoritmos de C ++.
El enfoque está siguiendo.
- Desde cada nodo de árbol nodo imprimible con valor de nodo original en cadena y posición absoluta en la línea compuesta.
- Nodos imprimibles hermanos agrupados. Cada grupo de hermanos contiene una lista de nodos y un puntero al nodo imprimible principal.
- Grupos de hermanos agrupados en líneas, cada línea representa el nivel del árbol original.
A continuación, se calcula la posición de los nodos imprimibles.
- Líneas iteradas saltando la primera.
- Los hermanos en la línea iteraron, cada grupo de hermanos se trasladó a su centro de nodo padre si el centro está más allá de la mitad del grupo. Se mueve aún más si se cruza con el grupo de hermanos anteriores. El nodo principal se movió al medio de los nodos secundarios si el centro está más lejos que el centro principal. Los nodos que siguen al nodo principal se desplazan si se cruzan con el nodo principal desplazado.
- El paso anterior se repite de forma recursiva para el grupo de hermanos.
Para el último paso, las líneas iteradas una vez más se escriben en el flujo de salida proporcionado, llenándose con espacios de compensación de acuerdo con las posiciones de los nodos calculados.
Los símbolos de dibujo de caja de Unix se utilizan para dibujar líneas. No estoy seguro de si se imprimirán correctamente en Windows cmd, tal vez deberían ser reemplazados por sus homólogos de DOS para Windows.
1
┌────────────┬────────┴────────────────────┐
11 12 13
┌────┼────┐ ┌──┴─┐ ┌─────────┴────┬────┐
111 112 113 121 122 131 132 133
┌─────┼─────┐ ┌─────┼─────┐ ┌──┴──┐
1221 1222 1223 1311 1312 1313 1321 1322
Pruebas unitarias con muestras de uso
Reseñas y puntuaciones
Agradecemos que quieras secundar nuestra investigación dejando un comentario y valorándolo te damos la bienvenida.