CODEWITHSUNDEEP
cred-black-tree
BugShotGG
BugShotGG

Reputation: 5190

Red Black tree print in level order in C

I have completed a red black tree in c and i find it hard to print it in level-order. I have a print-inorder but i cant imagine how am i supposed to display it as a tree in the console print. Is it feasible? Can we implement BFS or DFS here? i've found an algorithm in wiki but i cant apply it. If anyone has code for it in C could you post it here so i can study it? from wiki:

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)

Upvotes: 4

Views: 2488

Answers (1)

Fred Foo
Fred Foo

Reputation: 363517

You can do a BFS, but it might be easier to do an iterative deepening search, since that will save you the trouble of implementing a FIFO queue in C. Pseudocode:

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)

Upvotes: 4

Related Questions