按层次打印二叉树

Question

我们知道，可以按层或竖直方式打印二叉树。

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

                 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：

解释 layer

绿色标记的圆圈是第一层，

蓝色标记的圆圈是第二层，

红色标记的圆圈是第三层。

- zangw

---

你需要精确定义“层”这个术语的含义。 - ooga

抱歉，我不知道如何表达我的想法超越“层”，因为我不是母语使用者。我只是用一个例子来解释我的问题。 - zangw

为什么数字13和10属于同一层？ - Nghia Bui

这是一个有效的B树，我认为他只想忽略值遍历它。 - Catalyst

@Khalos，图层的顺序并不重要。 - zangw

Answer 1

一些澄清

• I will use C# in my answer. It is easy to translate C# to C++
• I will have 0-based arrays, layers and rows as it is common for C language
• However, I will add 1 to them at output in order to get the desirable output

• I suggest that you store your binary tree in a linear array of size 2n - 1 where n is a number of rows. Values where -1 are non-existent nodes:

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

算法解决方案

让我们绘制一个恰当的（就层次而言，而不是设计）图层图片：

http://ideone.com/fL4XCx

如果我们用层代替值，它将变成：

If we replace values with layers, it will 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

我们注意到:

1. 每行长度为n表示n \ 2层。
2. 每行的第一个和最后一个节点总是属于第一层。
3. 第二个和n-1总是属于第二层，以此类推。
4. 简单地说，层ID从1增加到n \ 2，然后再从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工作演示。

如果您将二叉树存储在带有祖先指针的数组中，而不是普通数组中，则可以执行BFS以按顺序获取值，并将其注入循环中。

- Yeldar Kurmangaliyev

Answer 2

我认为现在应该清晰简单了。

首先，请按标准顺序重新索引节点：

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

考虑一行，例如：

4, 5, 6, 7

第一个节点是2的幂次方，这个数字也是该行的长度。

考虑从左到右的前半部分4, 5，我们有：

• 4属于第1层
• 5属于第2层

考虑从右到左的第二半部分6, 7，我们有：

• 7属于第1层
• 6属于第2层

因此，在这一行中，节点的层索引可以根据节点到第一个和最后一个节点的距离来计算。

以下是代码：

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

- Nghia Bui

Answer 3

我还没检查过，但感觉应该是对的。

层数等于在该分支左右节点中较小的数量。

如果你的树节点是 R,R,L,R,R,L。
那么 R-cnt 是 4，L-cnt 是 2。
因此它是第 2 层...

谢谢！

- Tomer W

---

@Mox 好的，我再次检查了一下... 15 没问题，2xL 和 2xR => 第二层（如果从1开始计数，则为第三层） - Tomer W

Answer 4

对于@Tomer W的回答，我想补充两点：

1. 使用先序遍历（所以最左边的节点首先被访问）。
2. 将所有节点（或其某些引用）+层放入向量中，并使用stable_sort（在层上）以保留相等层级的节点之间的遍历顺序。

- marom

---

我的答案完全错误了...看起来是对的，但实际上并不是! - Tomer W