Print binary tree in a pretty way using c++
Asked Answered
D

7

25

I am a "bit" lost trying to print a binary tree like below in c++:

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

I know how to get the height of the tree and the number of nodes in each level, but I couldn't figure out how to set the right number of spaces between the root and the second level (there are 3 lines under the root for 3 levels but I believe it is not this everytime,I thought it could be 3 times the height for greater trees).

I would like to have some help to print these spaces in the rows and the number of lines between the rows.Thank you.

I am coding 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);
}
Dupre answered 22/4, 2016 at 20:0 Comment(4)
A binary tree may be printed in many different ways, see en.wikipedia.org/wiki/Tree_traversal. What is your desired output?Extraction
Are you trying to print the binary tree on the terminal?Schwing
I'd like to print it in the level-order,but I wanto print like a mentioned in the post, with the "/" ,jumping line and so on...Dupre
The output must be a tree in the console, not a sequence of numbersDupre
B
26

Here is an example of code creating a text-based representation of a binary tree. This demonstration uses a minimally useful binary tree class (BinTree), with a small footprint, just to avoid bloating the example's size.

Its text-rendering member functions are more serious, using iteration rather than recursion, as found in other parts of the class.

This does its job in three steps, first a vector of rows of string values is put together.

Then this is used to format lines of text strings representing the tree.

Then the strings are cleaned up and dumped to cout.

As an added bonus, the demo includes a "random tree" feature, for hours of nonstop entertainment.

#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;

        // allows leaf nodes to be connected when they are
        // all with size of a single character
        if(cell_width < 3) cell_width = 3;


        // 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();
}

An example of the 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
Banking answered 23/4, 2016 at 11:18 Comment(5)
Thank you Christopher. I think there is no easy way for this problem. I almost got a quick solution using queues but I couldn't figure out the intern distances.Dupre
I was surprised at how involved it turned out to be, but I was interested in seeing it finished because I have wanted something like this on several occasions in the past.Banking
@ChristopherOicles. could you please mention the compilation dependencies? using -std=c++11 flag throwing a lot of warnings+errors in my windows system.Sprue
@Sprue You probably have an old version of gcc which doesn't fully support c++11, it probably lacks the random library and may not support using for typedefs.Banking
Can anyone please simplify this code which consist value of "int" data type not template, also no need for generating tree from random values. I am a beginner and it is little complex for me, i just want to understand the logic. @ChristopherOiclesChili
B
71

Even tough it is not exactly what you asked for, printing trees horizontally is way simpler. And especially in case of large trees, I think this is the better representation form.

└──8
   ├──5
   │   ├──2
   │   └──6
   └──10
       ├──9
       └──11

Following C++ code roots in this java implementation.

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);
Bunde answered 7/8, 2018 at 15:44 Comment(2)
To be clear: I translated a java implementation reaching back to the user VasiliNovikov. This was his idea.Bunde
Although this is very elegant and compact, it only works for proper/complete binary trees. When, e.g., the root has no right subtree the whole line to the nonexistent node is still drawn. However, I can't think of a good way to make this more general.Highlight
B
26

Here is an example of code creating a text-based representation of a binary tree. This demonstration uses a minimally useful binary tree class (BinTree), with a small footprint, just to avoid bloating the example's size.

Its text-rendering member functions are more serious, using iteration rather than recursion, as found in other parts of the class.

This does its job in three steps, first a vector of rows of string values is put together.

Then this is used to format lines of text strings representing the tree.

Then the strings are cleaned up and dumped to cout.

As an added bonus, the demo includes a "random tree" feature, for hours of nonstop entertainment.

#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;

        // allows leaf nodes to be connected when they are
        // all with size of a single character
        if(cell_width < 3) cell_width = 3;


        // 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();
}

An example of the 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
Banking answered 23/4, 2016 at 11:18 Comment(5)
Thank you Christopher. I think there is no easy way for this problem. I almost got a quick solution using queues but I couldn't figure out the intern distances.Dupre
I was surprised at how involved it turned out to be, but I was interested in seeing it finished because I have wanted something like this on several occasions in the past.Banking
@ChristopherOicles. could you please mention the compilation dependencies? using -std=c++11 flag throwing a lot of warnings+errors in my windows system.Sprue
@Sprue You probably have an old version of gcc which doesn't fully support c++11, it probably lacks the random library and may not support using for typedefs.Banking
Can anyone please simplify this code which consist value of "int" data type not template, also no need for generating tree from random values. I am a beginner and it is little complex for me, i just want to understand the logic. @ChristopherOiclesChili
T
6

I wrote arbitrary tree pretty printer as a part of C++ algorithms self-education.

The approach is following.

  • From each tree node printable node with stringified original node value and absolute position in the line composed.
  • Sibling printable nodes grouped. Each sibling group contains list of nodes and pointer to parent printable node.
  • Sibling groups grouped to lines, each line represents original tree level.

Next, printable nodes position are calculated.

  • Lines iterated through skipping first one.
  • Siblings in the line iterated, each sibling group moved to its parent node center if the center is further then the middle of the group. It moves even further if intersected with previous siblings group. Parent node moved to the middle of the children nodes if the middle is further than parent center. Nodes following parent node are shifted if intersected with shifted parent node.
  • Previous step repeated for siblings group parent siblings group recursively.

For the last step lines iterated once again to be written to the provided output stream, filling with spaces offsets according to the calculated nodes positions.

Unix box-drawing symbols are used to draw lines. Not sure if they will be printed correctly in Windows cmd, maybe they should be replaced by their DOS counterparts for Windows.

                            1
      ┌────────────┬────────┴────────────────────┐
     11           12                            13
 ┌────┼────┐    ┌──┴─┐                 ┌─────────┴────┬────┐
111  112  113  121  122               131            132  133
               ┌─────┼─────┐     ┌─────┼─────┐     ┌──┴──┐
             1221  1222  1223  1311  1312  1313  1321  1322

Unit tests with usage samples

Tippler answered 1/11, 2019 at 16:24 Comment(2)
Hi @Nikita Karatun,Psycho
Please help with the compilation of your tree_printer_test. How can I reach you? You could send me a reply to [email protected] and I will send you the VC++ project. Please help.Psycho
R
6

I updated the vertical output again, the tree view was mirrored and some characters were not accepted in VS, so i put them in UTF8:

void printBT(const std::string& prefix, const TreeNode* node, bool isLeft)
{
    if (node != nullptr)
    {
        std::cout << prefix;
        std::cout << (isLeft ? "|--" : "L--");
        // print the value of the node
        std::cout << node->val << std::endl;
        // enter the next tree level - left and right branch
        printBT(prefix + (isLeft ? "|   " : "    "), node->right, true);
        printBT(prefix + (isLeft ? "|   " : "    "), node->left, false);
    }
}

void printBT(const TreeNode* node)
{
    printBT("", node, false);
}

Thanks a lot for that solution!! Example of Nodes: { 3, 5, 1, 6, 2, 9, 8, NULL, NULL, 7, 4 };

L--3
    |--1
    |   |--8
    |   L--9
    L--5
        |--2
        |   |--4
        |   L--7
        L--6

Not soo pretty, but very handy! Cheers Michael

Restitution answered 20/1, 2022 at 18:23 Comment(0)
D
0
  • 1st function - prints level by level (root lv -> leaves lv)
  • 2nd function - distance from the beginning of new line
  • 3rd function - prints nodes and calculates distance between two prints;

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);
        }
    }
}   

Input:

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

Output: Image

Deception answered 1/8, 2017 at 15:23 Comment(0)
C
0

I've edited the solution of Adrian Schneider and made the output more specific to understand better.

void print() {
  print("", root, false, true);
}

void print(const string &prefix, Node *parent, bool isLeft, bool isRoot) {
  if (parent == nullptr)
    return;

  if (isRoot) {
    cout << "─────";
  } else {
    cout << prefix <<
      (isLeft ? "L├────" : "R└───");
  }
  cout << parent -> value << endl;

  print(prefix + (isLeft ? " │   " : "    "),
    parent -> left, true, false);
  print(prefix + (isLeft ? " │   " : "    "),
    parent -> right, false, false);
}

The output looks like this for the input: {5, 6, 3, 2, 7}

─────5
    L├────3
     │   L├────2
    R└───6
        R└───7
Chryso answered 15/1, 2023 at 14:39 Comment(0)
D
0

All I did is check if the value of the node is greater or less, then check if its grandparent is null then check where its grandparent directs its parent.

ENTER A NUMBER : 20
                            T---(20)R
                       T---(19)B
                  T---(18)R
                  |    D---(17)B
             T---(16)B
             |    |    T---(15)B
             |    D---(14)R
             |         D---(13)B
        T---(12)R
        |    |    T---(11)B
        |    D---(10)B
        |         D---(9)B
ROOT---(8)B
        |         T---(7)B
        |    T---(6)B
        |    |    D---(5)B
        D---(4)R
             |    T---(3)B
             D---(2)B
                  D---(1)B

[Program finished]

1

Dentiform answered 4/4, 2023 at 16:9 Comment(2)
Did you use c++ for your solution? If so, you should include the code in your answer. If not, it's not really useful as an answer to the original question.Tuberose
I don't know how to use stack over flow, but here's the code's link that I made drive.google.com/file/d/1snw3y4pu4ToMieYXswgioPAbPuhG1nXH/…Dentiform

© 2022 - 2025 — McMap. All rights reserved.