Printing a binary tree by layer

Question

As we know, we can print a single binary tree either in level or in vertical

I want to print one binary tree on a layer. let me explain this with one example.

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

For one binary tree above, I want the result as

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

Is my question reasonable? if so, how to do it?

Edit 1:

Explain layer

The circle marked in green is the first layer,

The circle marked in blue is the second layer,

The circle marked in red is the third layer.

Answer 1

Some explanation

• I will use C # in my answer. Easy to translate C#toC++
• 0-based , , C
• , 1 ,

• 2n - 1, n - . , -1 :

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

( , ) :

http://ideone.com/fL4XCx

, :

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

, :

• n n \ 2.
• node 1.
• n - 1 2 ..
• , 1 n \ 2 1.

: node .

, , , . .

:

:

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> ++).
- , node Key Value:

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

:

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 to output)

:

for (int i = 0; i < n; i++)
    {
        if (currentNodeInRow == nodesInRow - 1) // if we are at the end of row
        {
            nodesInRow *= 2; // the count of nodes in binary tree doubles with every row
            currentNodeInRow = 0; // reset to the beginning 
        } else currentNodeInRow++; // go to the following node

        if (i == 0) {
            // 0-th node is a special case as it is the only row with odd count of nodes
            layers.Add(0, 0); 
            continue;
        }

        rowCenter = nodesInRow / 2 - 1; // row center

        if (currentNodeInRow <= rowCenter) // calculate layer according to rules above
            currentNodeLayer = currentNodeInRow;
        else
            currentNodeLayer = nodesInRow - currentNodeInRow - 1;

        if (currentNodeLayer > maxLayer) maxLayer = currentNodeLayer;
        layers.Add(i, currentNodeLayer); 

        // Console.WriteLine("{0} => {1}", i, currentNodeLayer);
    }

:

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

, :

for (int i = 0; i <= maxLayer; i++)
{
    Console.Write("Layer {0}:", i + 1); // Here we add 1 for 1-based output
    foreach (var x in layers.Where((p) => p.Value == i)) // sorry for being too C#
        if (arr[x.Key] != -1) Console.Write("{0} ", arr[x.Key]); 
    Console.WriteLine();
}

, , .

:

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

IDEOne Working Demo.

, - BFS .

Answer 2

i havnt , ,

.

node R, R, L, R, R, L.
THEN R-cnt 4, L-cnt - 2 2...

Answer 3

@Tomer W :

• ( ).
• ( ) + stable_sort ( ),

Answer 4

, .

:

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

, :

4, 5, 6, 7

node 2- , .

Consider the first half 4, 5from left to right, we have:

• 4 belongs to layer 1
• 5 belongs to layer 2

Consider the second half 6, 7from right to left, we have:

• 7 belongs to layer 1
• 6 belongs to layer 2

Thus, in this line, the index of the node layer can be calculated by the base at a distance from the node to the first and last node.

Here is the code:

bool isPowerOfTwo(int x) {
    return (x & (x - 1)) == 0;
}

int getLayerIndex(int nodeIndex) {
    int firstNode = nodeIndex;
    while ( ! isPowerOfTwo(firstNode) ) {
        --firstNode;
    }
    // Now firstNode is power of 2
    // firstNode is also the length of current row
    int lastNode = firstNode + firstNode - 1;
    return min( nodeIndex - firstNode + 1, lastNode - nodeIndex + 1 );
}