Binary Search Tree help

[Josh]

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

[mwb1100]

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]

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

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]

What mwb suggested is what I would do (except that i would use a better name for the variable!).

[Josh]

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]

i would use a better name for the variable!

-mouser (February 13, 2014, 04:30 AM)

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

 -- Phil Karlton

-http://martinfowler.com/bliki/TwoHardThings.html