CODEWITHSUNDEEP
c++binary-treetraversal
starcorn
starcorn

Reputation: 8531

C++ print out a binary search tree

Got nothing better to do this Christmas holiday, so I decided to try out making a binary search tree. I'm stuck with the print function. How should the logic behind it work? Since the tree is already inserting it in a somewhat sorted order, and I want to print the tree from smallest values to the biggest.

So I need to travel to the furthest left branch of the tree to print the first value. Right, so after that how do I remember the way back up, do I need to save the previous node? A search in wikipedia gave me an solution which they used stack. And other solutions I couldn't quite understand how they've made it, so I'm asking here instead hoping someone can enlight me.

I also wonder my insert function is OK. I've seen other's solution being smaller.

void treenode::insert(int i)
{

   if(root == 0)
   {
      cout << "root" << endl;
      root = new node(i,root);
   }
   else
   {
      node* travel = root;
      node* prev;
      while(travel)
      {
         if(travel->value > i)
         {
            cout << "travel left" << endl;
            prev = travel;
            travel = travel->left;
         }
         else
         {
            cout << "travel right" << endl;
            prev = travel;
            travel = travel->right;
         }
      }
      //insert
      if(prev->value > i)
      {
         cout << "left" << endl;
         prev->left = new node(i);
      }
      else
      {
         cout << "right" << endl;
         prev->right = new node(i);
      }
   }

}

void treenode::print()
{

   node* travel = root;
   while(travel)
   {
      cout << travel->value << endl;
      travel = travel->left;
   }

}

Upvotes: 2

Views: 14532

Answers (3)

David Rodr&#237;guez - dribeas
David Rodr&#237;guez - dribeas

Reputation: 208323

It all depends on the definition of the tree. If the nodes do not contain pointers back to the parent, then you need to use a stack to print the in-order transversal. The simplest way would be to write a recursive function to use the application's stack. The algorithm has already been shown before, but basically:

in-order(node):
   in-order(node.left) if node.left not null
   process(node)
   in-order(node.right) if node.right not null

If nodes hold pointers back to the parent, then you could write an iterative version, but it is probably not worth the effort (for anything but food for thought)

Upvotes: 0

T.E.D.
T.E.D.

Reputation: 44794

The traditional CS101 way to traverse a binary tree to do anything (printing, searching, insertion, etc.) is to use recursion. Have the (whatever) routine check its current node, then if that isn't the one it is looking for, call itself with the left and/or right subtree (if there is one).

For a nice discussion, with psedocode, check out the Wikipedia article on tree traversal. It even shows how to do it without recursion, which would match how you did insertion.

Upvotes: 0

crazylammer
crazylammer

Reputation: 1172

You can use recursion (pseudocode):

prin-tree(node):
   print-tree(left-subnode) if exists
   print(node-value)
   print-tree(right-subnode) if exists
...
print(root-of-tree)

Upvotes: 1

Related Questions