topbanner_forum
  *

avatar image

Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length
  • Thursday March 28, 2024, 3:54 am
  • Proudly celebrating 15+ years online.
  • Donate now to become a lifetime supporting member of the site and get a non-expiring license key for all of our programs.
  • donate

Author Topic: Binary Search Tree help  (Read 6867 times)

Josh

  • Charter Honorary Member
  • Joined in 2005
  • ***
  • Points: 45
  • Posts: 3,411
    • View Profile
    • Donate to Member
Binary Search Tree help
« on: February 12, 2014, 10:35 PM »
Hello all, let me preface this by saying that YES, this is for a homework assignment. That said, I have already completed 99% of the program and the only thing left is what I am about to ask for help on.

I have a function to display a binary search tree using in-order traversal. The function works fine (as does the rest of the program, but I am having some trouble in limiting the output to 10 numbers per line.

I.E,
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
etc.

The function looks like such

Code: C++ [Select]
  1. void inOrderDisplay(bstNode *nodeToDisplay)
  2. {
  3.         if (nodeToDisplay == NULL) return;
  4.         inOrderDisplay(nodeToDisplay->left);
  5.         cout << setw(6) << right << nodeToDisplay->integer;
  6.         inOrderDisplay(nodeToDisplay->right);  
  7. }

Now, what I am trying to achieve, as said above, is 10 numbers per line followed by a newline, then the next 10 numbers, etc.

I have tried various things like having a static int counter inside of the function, I have tried using a standard local variable, I have tried passing in the counter as a parameter (reference). Once inside, I have attempted to use (if counter == 0), if (counter % 10 == 0), or if (counter > 10).

I am really at a loss here and this is the only thing holding up my submission of this program. How do you go about doing something like this inside of a recursive function?

Thanks in advance :)
« Last Edit: February 12, 2014, 10:43 PM by Josh »

mwb1100

  • Supporting Member
  • Joined in 2006
  • **
  • Posts: 1,645
    • View Profile
    • Donate to Member
Re: Binary Search Tree help
« Reply #1 on: February 13, 2014, 02:24 AM »
I'm not sure why passing in a counter by reference didn't work for you.  Maybe you can post that attempt.

If you're OK with me just posting what I believe to be a solution (though it's not tested, so maybe it's no help at all), here's a snippet that I think should work:

Spoiler
Code: C++ [Select]
  1. void inOrderDisplay(bstNode *nodeToDisplay)
  2.     {
  3.         int state = 0;  // will keep track of number of elements printed per line
  4.        
  5.         inOrderDisplay( nodeToDisplay, state);
  6.     }
  7.  
  8.  
  9.     void inOrderDisplay(bstNode *nodeToDisplay, int& state)
  10.     {
  11.         if (nodeToDisplay == NULL) return;
  12.         inOrderDisplay(nodeToDisplay->left, state);
  13.         cout << setw(6) << right << nodeToDisplay->integer;
  14.        
  15.         ++state;
  16.         if (state >= 10) {
  17.             cout << endl;
  18.             state = 0;
  19.         }
  20.            
  21.         inOrderDisplay(nodeToDisplay->right, state);   
  22.     }
   



Jibz

  • Developer
  • Joined in 2005
  • ***
  • Posts: 1,187
    • View Profile
    • Donate to Member
Re: Binary Search Tree help
« Reply #2 on: February 13, 2014, 03:40 AM »
A static variable should work as well, you just have to remember that it is initialized at program start, so you will need some way to reset it between uses.

You could also pass and return an int that contains the total number of integers printed so far.

But this being C++, perhaps a better solution would be to create a little helper class, which wraps an ostream, and then pass it to your function. This way, you have removed the details of how the numbers are printed from the traversal, and you can reuse it if you have to print the tree in some other order as well.

Spoiler
Disclaimer: this was written rather quickly, might not work as intended ;D

Code: C++ [Select]
  1. class NumberPrinter {
  2.         std::ostream &to;
  3.         const int lim;
  4.         int num;
  5.  
  6. public:
  7.         NumberPrinter(std::ostream &to, int lim) : to(to), lim(lim), num(0) { ; }
  8.  
  9.         void reset() { num = 0; }
  10.  
  11.         void print_number(int n)
  12.         {
  13.                 to << std::setw(6) << std::right << n;
  14.  
  15.                 if (++num == lim) {
  16.                         to << std::endl;
  17.                         num = 0;
  18.                 }
  19.         }
  20.  
  21.         void finish()
  22.         {
  23.                 if (num > 0) {
  24.                         to << std::endl;
  25.                         num = 0;
  26.                 }
  27.         }
  28. };
  29.  
  30. // for convenience
  31. NumberPrinter &operator<<(NumberPrinter &np, int i)
  32. {
  33.         np.print_number(i);
  34.         return np;
  35. }
  36.  
  37. // your traversal function
  38. void inOrderDisplay(bstNode *nodeToDisplay, NumberPrinter &np)
  39. {
  40.         if (nodeToDisplay == NULL) return;
  41.         inOrderDisplay(nodeToDisplay->left, np);
  42.         np << nodeToDisplay->integer;
  43.         inOrderDisplay(nodeToDisplay->right, np);      
  44. }
  45.  
  46. // print 10 numbers per line to cout
  47. NumberPrinter np(std::cout, 10);
  48. inOrderDisplay(root, np);
  49. np.finish();


mouser

  • First Author
  • Administrator
  • Joined in 2005
  • *****
  • Posts: 40,896
    • View Profile
    • Mouser's Software Zone on DonationCoder.com
    • Read more about this member.
    • Donate to Member
Re: Binary Search Tree help
« Reply #3 on: February 13, 2014, 04:30 AM »
What mwb suggested is what I would do (except that i would use a better name for the variable!).

Josh

  • Charter Honorary Member
  • Joined in 2005
  • ***
  • Points: 45
  • Posts: 3,411
    • View Profile
    • Donate to Member
Re: Binary Search Tree help
« Reply #4 on: February 13, 2014, 09:23 AM »
mwb!!!!!! That is exactly what I had before with the exception of the fact of where I had the ++counter set at. I had it at the end of the function (made logical sense to me). Now it works beautifully!

Jibz, thanks for the suggestion as well. Unfortunately, we have to use structured code and not OOP (I love OOP and this is driving me nuts). Plus, each function I add I would have to calculate the Big-O for so I want to minimize my number of functions :)

Thanks again everyone! This is working like a champ!

mwb1100

  • Supporting Member
  • Joined in 2006
  • **
  • Posts: 1,645
    • View Profile
    • Donate to Member
Re: Binary Search Tree help
« Reply #5 on: February 13, 2014, 12:42 PM »
i would use a better name for the variable!

There are only two hard things in Computer Science: cache invalidation and naming things.

 -- Phil Karlton