displaying B-tree in tree traversal order/1 level at a time

**daluu** · 05-22-2003

I've written code for displaying a B-tree in tree traversal order or 1 level of the B-tree at a time. However, I my code is not implemented as it should. It only works logically for a B-tree of level 2, since the nodes under the root are leaf nodes. but for larger depths, the B-tree would print children nodes from left branches 1st then going back up to the right branches. How should I modify the recursion, etc. to print nodes of a B-tree, from left to right before going to the next level?

Code:

void print_btree(short root){ 
   BTPAGE page; 
   int i; 

   btread(root,&page); 

   //print pg # 
   printf("%d\t",root); 

   //print keys of page 
   for(i = 0; i < page.keycount; ++i) 
      printf("%s ",page.key[i]); 
    
   //add space padding 
   for(i = page.keycount; i < MAXKEYS; ++1) 
      printf("       "); 
   printf("\t"); 

   //print child ptrs of page 
   for(i = 0; i <= page.keycount; ++i) 
      printf("%d ",page.child[i]); 
   printf("\n"); 

    
   //print lower/next level of btree - RECURSIVE 
   for(i = 0; i <= page.keycount; ++i){ 
      if(page.child[i] != NIL) 
         print_btree(page.child[i]); 
   } 
    

   return; 

}

**R.Stiltskin** · 05-22-2003

Instead of recursion, why not use a queue?
print node
insert children (left, then right) on queue
print next on queue
...
(loop until queue is empty)

**daluu** · 05-22-2003

Unfortunately, the project lists recursion as a requirement.

Regarding the use of a queue. Kind of fuzzy as how to make use of that. Additionally, wouldn't placing children nodes (or just pointers) from root down to leaf into the queue, as we are printing, require recursion anyways? Puzzled on the idea. Can you explain some more?

**R.Stiltskin** · 05-22-2003

No, it wouldn't be recursive.

A queue is just a first-in, first-out ordered list. So, first you print the root and place a pointer to its left child, followed by its right child, in the queue. Next, you remove the first element from the queue (which is the root's left child), print it, add its left child and then its right child to the queue; next, you remove the new first element from the queue (which is the root's right child), and so on ...

But this isn't recursive. It just goes something like:

Code:

root->print();
q.insert(root.getleft());
q.insert(root.getright());
while(!q.empty()){
    node*next=q.remove();
    next->print();
    q.insert(next->getleft());
    q.insert(next->getright());
}

anyway, that's the general idea.
On the other hand, it's so simple, I don't know why you would knock yourself out figuring out a recursive algorithm to do it (except if the assignment requires it, I guess).

**Prelude** · 05-23-2003

>Unfortunately, the project lists recursion as a requirement.
Then you can't do a level order traversal without bending over backward. Recursion is the equivalent of using a stack; the algorithm for level order traversal with a stack is called preorder, the two are not the same thing at all.

**Cat** · 05-23-2003

Hmm, are you SURE you're supposed to be printing the tree in level order? "Tree traversal order", at least in the texts I've read, is just the generic term for any of the different kinds of orders, such as preorder, postorder, in-order, level-order.

Recursion makes it very easy to traverse a BST in preorder, postorder, or in-order, are you sure you're not supposed to use one of those? Level-order is not easy to do recursively at all. A queue is really the best way, there.

Thread: displaying B-tree in tree traversal order/1 level at a time

Thread Tools

Search Thread

Display

displaying B-tree in tree traversal order/1 level at a time

Similar Threads

plain tree traversal

Recursive Tree Traversal

Iterative Tree Traversal using a stack

I apologize. Good bye.

displaying the time