4

Cで赤黒の木を完成させましたが、レベル順で印刷するのは難しいと思います。print-inorder がありますが、コンソール印刷でツリーとして表示する方法を想像できません。それは実現可能ですか？ここに 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)
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 に答える