c - 在C中按级别顺序打印红黑树

Question

我已经在 c 中完成了一棵红黑树，我发现很难按级别顺序打印它。我有一个打印顺序，但我无法想象我应该如何在控制台打印中将它显示为树。可行吗？我们可以在这里实现 BFS 或 DFS 吗？我在 wiki 中找到了一个算法，但我无法应用它。如果有人有 C 语言的代码，你能把它贴在这里以便我研究吗？来自维基：

levelorder(root) 
  q = empty queue
  q.enqueue(root)
  while not q.empty do
    node := q.dequeue()
    visit(node)
    if node.left ≠ null
      q.enqueue(node.left)
    if node.right ≠ null
      q.enqueue(node.right)

Answer 1

您可以进行 BFS，但进行迭代深化搜索可能更容易，因为这样可以省去在 C 中实现 FIFO 队列的麻烦。伪代码：

algorithm iterative-deepening(root)
    D = max-depth(root)
    for d=0 to D
        depth-limited-search(root, d)

/* variant of DFS */
algorithm depth-limited-search(node, d)
    if node != NULL
        if d == 0
            print node.contents
        else
            depth-limited-search(node.left, d - 1)
            depth-limited-search(node.right, d - 1)