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

This is a discussion on displaying B-tree in tree traversal order/1 level at a time within the C++ Programming forums, part of the General Programming Boards category; I've written code for displaying a B-tree in tree traversal order or 1 level of the B-tree at a time. ...

  1. #1
    Registered User daluu's Avatar
    Join Date
    Dec 2002
    Posts
    42

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

    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; 
    
    }

  2. #2
    Registered User
    Join Date
    Feb 2003
    Posts
    595
    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)

  3. #3
    Registered User daluu's Avatar
    Join Date
    Dec 2002
    Posts
    42
    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?

  4. #4
    Registered User
    Join Date
    Feb 2003
    Posts
    595
    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).
    Last edited by R.Stiltskin; 05-22-2003 at 08:01 PM.

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >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.
    My best code is written with the delete key.

  6. #6
    Cat
    Cat is offline
    Registered User
    Join Date
    May 2003
    Posts
    1,571
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. plain tree traversal
    By kmel in forum C++ Programming
    Replies: 2
    Last Post: 02-18-2008, 11:15 AM
  2. Recursive Tree Traversal
    By John_L in forum C++ Programming
    Replies: 12
    Last Post: 02-17-2008, 07:34 AM
  3. Iterative Tree Traversal using a stack
    By BigDaddyDrew in forum C++ Programming
    Replies: 7
    Last Post: 03-10-2003, 04:44 PM
  4. I apologize. Good bye.
    By doubleanti in forum A Brief History of Cprogramming.com
    Replies: 14
    Last Post: 05-03-2002, 06:51 PM
  5. displaying the time
    By face_master in forum C++ Programming
    Replies: 2
    Last Post: 09-07-2001, 03:43 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21