如何水平打印二叉树？

Question

我该如何以这种方式打印我的二叉树？

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

我的打印函数是：

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

目前我的函数是这样打印的

5
2 
0 3 9
7 12

- neostar

---

树是否总是完整的，还是有缺失的分支？ - Botje

你需要对树进行层序遍历（或 BFS），而不是深度优先遍历（DFS）。你应该使用队列来进行遍历，而不是递归。 - prakasht

@Botje树已完成 - neostar

Answer 1

您可以创建哈希映射来指示您所处树的级别，与该级别顶部的值相关联。例如：

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

然后你可以遍历你的树，填充你的映射表，使得你的映射表看起来像这样：

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

您可能需要使用一个临时计数器变量来确定树的深度级别，并相应地更新它。使用该临时索引计数器指示映射的键，并用其填充树的行，将值保存到向量中，然后从那里，您可以在每个键级别上打印此映射...

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

像这样的东西可能是一个可能的解决方案...

- Francis Cugler

Answer 2

问题在于你无法“反向”打印。一旦你打印了一行，你就不能再回到上面（使用标准C++，也许可以使用终端控制代码或函数，但这会使你的代码过于复杂）。

相反，考虑使用“矩阵”缓冲区，其中每个树的“行”都存储在“2D”数组的一个单独行中。

对于像你的树这样的树，缓冲区可能是这样的：

int buffer[3][4];

然后，buffer[0][0] 将成为树的根节点，buffer[1][0] 将成为 2 节点，buffer[1][1] 将成为 9 节点，而 buffer[2] 将包含所有叶子节点。

然后，只需遍历“buffer”并均匀地分隔所有节点即可打印（需要实验）。

这需要您了解树的深度以及叶节点的数量（或具有用于学习的函数）。对于纯二叉树，找出这些信息非常简单。

- Some programmer dude

Answer 3

从 std::vector<node*> frontier = { root_node } 开始

然后，重复以下步骤:

• 对于frontier中的每个元素，将node->value打印在同一行上。
• 再次遍历frontier，并将所有node->left和node->right指针收集到一个新的向量中。 将其分配给frontier。
• 如果任何子指针为NULL，则停止。

- Botje