Stampa albero binario in un modo piuttosto utilizzando C++

Question

io sono un "po '" persi cercando di stampare un albero binario come qui di seguito in C++:

  8 
     /\ 
     / \ 
     / \ 
     5  10 
    /\ /\ 
     2 6 9 11 

so come ottenere l'altezza dell'albero e il numero di nodi in ogni livello, ma non riuscivo a capire come impostare il giusto numero di spazi tra la radice e il secondo livello (ci sono 3 linee sotto la radice per 3 livelli ma credo che non sia sempre questa volta, ho pensato potrebbe essere 3 volte l'altezza per alberi più grandi).

Mi piacerebbe avere qualche aiuto per stampare questi spazi nelle righe e il numero di linee tra le righe. Grazie.

sto codifica in C++

Get height 

int tree::getHeight(No *node) { 
    if (node == NULL) return 0; 
    return 1 + max(getHeight(node->esq), getHeight(node->dir)); 
} 

Get number of nodes per line 

void tree::getLine(const No *root, int depth, vector<int>& vals){ 
    int placeholder = 10; 
    if (depth <= 0 && root != nullptr) { 
     vals.push_back(root->chave); 
     return; 
    } 
    if (root->esq != nullptr) 
     getLine(root->esq, depth-1, vals); 
    else if (depth-1 <= 0) 
     vals.push_back(placeholder); 
    if (root->dir != nullptr) 
     getLine(root->dir, depth-1, vals); 
    else if (depth-1 <= 0) 
     vals.push_back(placeholder); 
} 

Answer 1

Ecco un esempio di codice di creare una rappresentazione testuale di un albero binario. Questa dimostrazione utilizza una classe di albero binario minimamente utile (BinTree), con un ingombro ridotto, solo per evitare di gonfiare le dimensioni dell'esempio.

Le funzioni membro di rendering del testo sono più serie, utilizzando l'iterazione anziché la ricorsione, come si trova in altre parti della classe.

Questo fa il suo lavoro in tre fasi, prima viene messo insieme un vettore di righe di valori stringa.

Quindi viene utilizzato per formattare le righe di stringhe di testo che rappresentano l'albero.

Quindi le stringhe vengono pulite e scaricate in cout.

Come bonus aggiuntivo, la demo include una funzione "albero casuale", per ore di intrattenimento non-stop.

#include <iostream> 
#include <vector> 
#include <string> 
#include <sstream> 
#include <algorithm> 
#include <random> 

using std::vector; 
using std::string; 
using std::cout; 

template <typename T> 
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 <typename ...Args> 
    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<Node*> traversal_stack; 
     vector< std::vector<Node*> > 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<string> 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<string> 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<row_count; ++r) { 
      const auto& cd_row = rows_disp[row_count-r-1]; // r reverse-indexes the row 
      // "space" will be the number of rows of slashes needed to get 
      // from this row to the next. It is also used to determine other 
      // text offsets. 
      s_t space = (s_t(1) << r) * (cell_width + 1)/2 - 1; 
      // "row" holds the line of text currently being assembled 
      string row; 
      // iterate over each element in this row 
      for(s_t c=0; c<row_elem_count; ++c) { 
       // add padding, more when this is not the leftmost element 
       row += string(c ? left_pad*2+1 : left_pad, ' '); 
       if(cd_row[c].present) { 
        // This position corresponds to an existing Node 
        const string& valstr = cd_row[c].valstr; 
        // Try to pad the left and right sides of the value string 
        // with the same number of spaces. If padding requires an 
        // odd number of spaces, right-sided children get the longer 
        // padding on the right side, while left-sided children 
        // get it on the left side. 
        s_t long_padding = cell_width - valstr.length(); 
        s_t short_padding = long_padding/2; 
        long_padding -= short_padding; 
        row += string(c%2 ? short_padding : long_padding, ' '); 
        row += valstr; 
        row += string(c%2 ? long_padding : short_padding, ' '); 
       } else { 
        // This position is empty, Nodeless... 
        row += string(cell_width, ' '); 
       } 
      } 
      // A row of spaced-apart value strings is ready, add it to the result vector 
      formatted_rows.push_back(row); 

      // The root has been added, so this loop is finsished 
      if(row_elem_count == 1) break; 

      // Add rows of forward- and back- slash characters, spaced apart 
      // to "connect" two rows' Node value strings. 
      // The "space" variable counts the number of rows needed here. 
      s_t left_space = space + 1; 
      s_t right_space = space - 1; 
      for(s_t sr=0; sr<space; ++sr) { 
       string row; 
       for(s_t c=0; c<row_elem_count; ++c) { 
        if(c % 2 == 0) { 
         row += string(c ? left_space*2 + 1 : left_space, ' '); 
         row += cd_row[c].present ? '/' : ' '; 
         row += string(right_space + 1, ' '); 
        } else { 
         row += string(right_space, ' '); 
         row += cd_row[c].present ? '\\' : ' '; 
        } 
       } 
       formatted_rows.push_back(row); 
       ++left_space; 
       --right_space; 
      } 
      left_pad += space + 1; 
      row_elem_count /= 2; 
     } 

     // Reverse the result, placing the root node at the beginning (top) 
     std::reverse(formatted_rows.begin(), formatted_rows.end()); 

     return formatted_rows; 
    } 

    // Trims an equal number of space characters from 
    // the beginning of each string in the vector. 
    // At least one string in the vector will end up beginning 
    // with no space characters. 
    static void trim_rows_left(vector<string>& 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 << " <empty tree>\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<int> bt; 

    // Build OP's tree 
    bt.insert(8,5,2,6,10,9,11); 
    cout << "Tree from OP:\n\n"; 
    bt.Dump(); 
    cout << "\n\n"; 

    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<int> dist(Min,Max); 

    while(MaxCount--) { 
     bt.insert(dist(rng)); 
     if(bt.get_max_depth() >= MaxDepth) break; 
    } 

    cout << "Randomly generated tree:\n\n"; 
    bt.Dump(); 
} 

Un esempio di output:

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 

Answer 2

• prima funzione - livello stampe per livello (root lv -> lascia lv)
• 2 ° funzione - distanza dall'inizio della nuova linea
• Terza funzione: stampa i nodi e calcola la distanza tra due stampe;

---

void Tree::TREEPRINT() 
{ 
    int i = 0; 
    while (i <= treeHeight(getroot())){ 
     printlv(i); 
     i++; 
     cout << endl; 
    } 
} 

void Tree::printlv(int n){ 
    Node* temp = getroot(); 
    int val = pow(2, treeHeight(root) -n+2); 
    cout << setw(val) << ""; 
    prinlv(temp, n, val); 
} 

void Tree::dispLV(Node*p, int lv, int d) 
{ 
    int disp = 2 * d; 
    if (lv == 0){ 
     if (p == NULL){ 

      cout << " x "; 
      cout << setw(disp -3) << ""; 
      return; 
     } 
     else{ 
      int result = ((p->key <= 1) ? 1 : log10(p->key) + 1); 
      cout << " " << p->key << " "; 
      cout << setw(disp - result-2) << ""; 
     } 
    } 
    else 
    { 
     if (p == NULL&& lv >= 1){ 
      dispLV(NULL, lv - 1, d); 
      dispLV(NULL, lv - 1, d); 
     } 
     else{ 
      dispLV(p->left, lv - 1, d); 
      dispLV(p->right, lv - 1, d); 
     } 
    } 
} 

ingresso:

50-28-19-30-29-17-42-200-160-170-180-240-44-26-27 

uscita: https://i.stack.imgur.com/TtPXY.png