正如我们所知，我们可以按级别或 vertical 打印一棵二叉树

我想逐层打印一棵二叉树。让我通过一个例子来解释。

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

对于上面的一棵二叉树，我想要这样的输出

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

我的问题合理吗？如果可以，该怎么做？

编辑 1:

解释层

绿色圆圈为第一层，

蓝色圆圈为第二层，

红色圆圈为第三层。

最佳答案

一些说明

• 我将在我的回答中使用 C#。很容易翻译C#至 C++
• 我将使用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

我们注意到:

1. 每一行的长度n代表n \ 2层。
2. 一行中的第一个和最后一个节点始终属于第 1 层。
3. 第二个和 n - 1始终属于第 2 层，依此类推。
4. 简而言之，层 ID 从 1 增加 1 到 n \ 2 , 并减少回 1。

这正是我们解决这个问题的方式:我们将根据这些规则逐层遍历二叉树并为每个节点计数层。

解决方案代码

实际上，树中包含的值不会影响解决方案。它仅在输出时需要。

让我们声明一些变量:

我们的数组:

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

Dictionary<int, int> (在 C++ 中为 map<int,int>)。
键值对表示索引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 以按该顺序获取值并将其注入(inject)循环。

关于c++ - 逐层打印二叉树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31282710/