How to print binary tree in horizontal way?

user_10799032 0
Viewed 1134

How can I print my binary tree in this way?

the original tree      I need 
      5                5
     /  \              
    2    9             2   9
   / \  / \   
  0  3  7  12          0 3 7 12

My print function is :

void display(struct node* start){
    cout << start->data << " ";
   if(start != NULL){
        if(start->left){
            cout << "\n";
           display(start->left);
    }
        if(start->right) {
            display(start->right);
        }
    }
}

Currently my function prints this way

5
2 
0 3 9
7 12
binary-tree data-structures binary c++
3 Answers

You could create a hash map to indicate the level of the tree you are at in association with the values at that level of the tree. For example:

std::map<unsigned, std::vector<unsigned>> hash;

Then you can go through your tree and populate your map so that your map would look like this:

hash[0] = { 5 };
hash[1] = { 2, 9 };
hash[2] = { 0, 3, 7, 12 };

You may need to use a temporary counter variable to know what level of depth you are at in your tree and update it accordingly. Use that temporary index counter to indicate the key of the map and use that to populate the rows of your tree saving the values into the vector, then from there, you can print this map at each key level...

for (unsigned i = 0; i < hash.size(); i++ ) { // each level of tree
    for (auto& v : hash[i] ) { // each element in that vector
        std::cout << v << " ";
    }
    std::cout << '\n';
}

Something like this could be one possible solution...

user_17578050

The problem is that you can't print "backward". Once you printed a line, you can't go back up (using standard C++, it might be possible using terminal control codes or functions which will make your code overly complex).

Instead consider using a "matrix" buffer, where each "line" of the tree is stored in a single row in a "2D" array.

For a tree like yours the buffer could be something like

int buffer[3][4];

Then buffer[0][0] would be the root of the tree, buffer[1][0] would be the 2 node, buffer[1][1] would be the 9 node, and buffer[2] would contain all the leaf nodes.

Then to print you just iterate over the "buffer" to and space out all nodes evenly (experimentation needed).

This requires you to know (or have functions to let you learn) the depth of the tree as well as the number of leaf nodes. For a pure binary tree it's pretty simple to find that out though.

user_4405580

Start with std::vector<node*> frontier = { root_node }

Then, repeat the following:

  • Print node->value for each element in frontier, side by side on one line.
  • Walk frontier again and collect all node->left and node->right pointers into a new vector. Assign this to frontier.
  • If any of the child pointers are NULL, stop.
user_15484680
Related