c++ - Print a binary tree by layer -

as know, can print 1 binary tree either level or vertical

i want print 1 binary tree layer. let me explain through 1 example.

                 1                         /         \           2              3               /      \       /     \       4        5      6         7         /   \    /   \   /   \    /    \    8    9  15    12 14   13  10     11 

for 1 binary tree above, want output like

1st layer: 8 4 2 1 3 7 11 2nd layer: 9 5 6 10  3rd layer: 15 13 4th layer: 12 14 

is question reasonable? if so, how that?

edit 1:

explain layer

the circle marked green first layer,

the circle marked blue second layer,

the circle marked red third layer.

some clarifications

• i use c# in answer. easy translate c# c++
• i have 0-based arrays, layers , rows common c language
• however, add 1 them @ output in order desirable output

• i suggest store binary tree in linear array of size 2n - 1 n number of rows. values -1 non-existent nodes:

  [ 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, 12, 14, 13, 10, 11 ] 

algorithmical solution

let's draw proper (in terms of layers, not design) picture of layers:

http://ideone.com/fl4xcx

if replace values layers, become:

1 1 1 1 2 2 1 1 2 3 4 4 3 2 1 1 2 3 4 5 6 7 8 8 7 6 5 4 3 2 1 

we notice that:

1. every row of length n represents n \ 2 layers.
2. the first , last node in row belongs layer 1.
3. the second 1 , n - 1 belongs layer 2 , on.
4. simply said, layers id being increased 1 one n \ 2, , decreased 1.

that's how solve problem: traverse through binary tree level level , count layer every node according these rules.

solution code

actually, values contained in tree don't affect solution. required @ output.

let's declare variables:

our array:

int[] arr = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, 12, 14, 13, 10, 11 }; 

dictionary<int, int> (map<int,int> in c++).
key-value pair means node of index key belongs layer value:

dictionary<int, int> layers = new dictionary<int, int>(); 

some variables:

int n = arr.length,              // length of array (for convenience)         nodesinrow = 1,          // how many nodes in current row         currentnodeinrow = -1,   // position of node in current row         rowcenter,               // center of array (for convenience)         currentnodelayer = 0,    // layer of current node         maxlayer = -1;           // maximum layer (we should know how many output) 

and main loop:

for (int = 0; < n; i++)     {         if (currentnodeinrow == nodesinrow - 1) // if @ end of row         {             nodesinrow *= 2; // count of nodes in binary tree doubles every row             currentnodeinrow = 0; // reset beginning          } else currentnodeinrow++; // go following node          if (i == 0) {             // 0-th node special case row odd count of nodes             layers.add(0, 0);              continue;         }          rowcenter = nodesinrow / 2 - 1; // row center          if (currentnodeinrow <= rowcenter) // calculate layer according rules above             currentnodelayer = currentnodeinrow;         else             currentnodelayer = nodesinrow - currentnodeinrow - 1;          if (currentnodelayer > maxlayer) maxlayer = currentnodelayer;         layers.add(i, currentnodelayer);           // console.writeline("{0} => {1}", i, currentnodelayer);     } 

now, have following dictionary:

{{0, 0}, {1, 0}, {2, 0}, {3, 0}, {4, 1}, {5, 1} ...} 

we can output because know count of layers in our tree:

for (int = 0; <= maxlayer; i++) {     console.write("layer {0}:", + 1); // here add 1 1-based output     foreach (var x in layers.where((p) => p.value == i)) // sorry being c#         if (arr[x.key] != -1) console.write("{0} ", arr[x.key]);      console.writeline(); } 

notice didn't work array of values before output because layers not affected contents of array.

as result, following output:

layer 1: 1 2 3 4 7 8 11  layer 2: 5 6 9 10  layer 3: 13  layer 4: 12 14  

here ideone working demo.

in case store binary tree not in plain array in array pointers ancestors - can execute bfs values in order , inject in loop.