4

我已经在 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)
4

1 回答 1

4

您可以进行 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)
于 2012-01-07T13:21:34.933 回答