Saltar al contenido

Imprime un árbol binario de una manera bonita usando c ++

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.

¡Haz clic para puntuar esta entrada!
(Votos: 2 Promedio: 4)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *