C语言中按层次顺序打印红黑树

Question

我已经完成了一个红黑树的c语言实现，但是我发现很难按层次顺序打印树结构。我有一个按中序遍历的打印方法，但是我不知道怎么在控制台输出树结构。这可行吗？我们可以在此处实现BFS或DFS算法吗？我在维基百科上找到了一篇文章，但是无法应用它。

如果有人有相应的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)

- BugShotGG

---

这是作业吗？如果是，请打上标签。 - Sergey Kalinichenko

红黑树是作业内容。以那种形式打印并不是必须的，这只是为了方便我自己 :) - BugShotGG

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)

- Fred Foo

---

我该如何找到红黑树的最大深度？我需要在插入数据时添加计数器吗？ - BugShotGG

@GeoPapas：有很多方法可以获取深度。请注意，红黑树的属性保证了最大深度与元素数量的关系。您还可以进行深度优先搜索（DFS）。 - Fred Foo

所以我可以让一棵树从根节点遍历到一个叶子节点（左右子节点都为空），并计算我遇到的节点数。这应该可以给出一个近似的高度，对吧？ - BugShotGG

@GeoPapas：然后进行适当的算术运算，因为您想要深度的上限，而不是下限（否则您将无法打印整棵树）。但是，是的，那会起作用。 - Fred Foo