Can someone please explain this

[mpj88]

Hi can someone explain this piece of code for me:

void printTree(struct node* point) 
{ 
  if (point == NULL) return; 

  printTree(point->left); 
  cout<<point->data<<"\n";
  //std::cin.get();
  printTree(point->right); 
 
}

I know it prints an ordered binary tree in order. But i'm not sure how. I need to count how many times it has cycled through commands so that i can find and print the median value.

Thanks

[Computergeek01]

It calls itself based on the the value stored in "left" and "right", which appear to be members of a structure, that contains data members of itself, that is passed into it.

EDIT: In order to know a "real number" value for your question you need to know exactly what data is being stored in this structure, otherwise if this is the entire assignment you need to give the answer as a mathmatical function.

[mpj88]

right that sounds confusing! so where can i put a count so that everytime a number is "cout"ed it increases?

ive tried replacing the 6th line with something like runs++; but it doesn't work. Just stays at the initialised value

[Computergeek01]

You already have one at line 6. Just move it to Line 4 and change "data" to "left", repeat it on line 7 and change "data" to "right".

[mpj88]

no i don't want to print the left and right nodes. I want to count everytime that function prints a number out. For example that function would read from a ordered binary search function the following numbers:
1
2
3
4
5

i want to know when its at 3 so that i can only print that one number

[Computergeek01]

The reason runs++ didn't increase I'll bet is because you declared it locally within the function. To keep it simple declare "runs" as a global variable and it should work.

EDIT: You do realize that assuming the program doesn't stop evaluating the number set that it will change everytime there is a new input right?

[mpj88]

bingo! thank you! will try and work from there!

not quite sure what you mean in the end. so it doesnt read them off in order

I tried the following:

void find_median(struct node* point)
{

	if (point == NULL) return;
	find_median(point->left);
	runs++;
	//cout<<point->data<<"\n";
	//cout<<runs;
	//std::cin.get();
	if (runs == count/2)  
	{
	cout<<point->data<<"is the median at line "<<point->line_number<<"\n";
	}

	find_median(point->right); 
	
}

count is the number of items in the tree

but it didnt work! :(

[Computergeek01]

"runs" is declared globally? As in outside of any functions including Main(...)? That should work then, can you post the whole thing? from the Header declarations to the end of file? If it's too large we can work around that too.

EDIT: So it should look something like this:

int runs;

void find_median(struct node* point)
{
  //... Your Code
 // ...
}

int Main()
{
   //... More of your code
   //... 

return EXIT_SUCCESS;
}

[mpj88]

#include "stdafx.h"

#include <iostream>
#include <iomanip>
#include <fstream>

using namespace std;

int count=1;
int runs=0;


struct node 
{
	float data;
	int line_number;
    struct node* left;
    struct node* right;

}; 


struct node* NewNode(float data, int line)

{	
	struct node* node = new(struct node);// "new" is like "malloc" 

	node->line_number=line;
	node->data = data; 
	node->left = NULL; 
	node->right = NULL; 

	return(node); 
}

struct node* insert(struct node* point, float data, int line) 
{ 
  // If the tree is empty, return a new, single node 
  if (point == NULL) { 
    return(NewNode(data, line)); 
  } 
  else { 
    // Otherwise, work your way down the tree 
    if (data <= point->data) point->left = insert(point->left, data, line); 
    else point->right = insert(point->right, data, line); 

    return(point); // return the node pointer 
  } 
}




struct node* inserting()
{

	float x;
	int line_number = 1;
	
	ifstream inFile;
	
	inFile.open("test.txt");
    if (!inFile) {
        cout << "Unable to open file";
	std::cin.get();
        exit(1); // terminate with error
    
	}

	inFile >> x;
	inFile.close();
	
	node* point = insert(NULL,x,line_number);
	
	line_number++;

	inFile.open("test.txt");
    if (!inFile) {
        cout << "Unable to open file";
	std::cin.get();
        exit(1); // terminate with error
    
	}
	inFile >> x;

	insert(NULL,x,line_number);

	while (!inFile.eof()) {
	inFile >> x;
	
	insert(point,x, line_number);
	count++;
	line_number++;
	
	}
	
	//cout << count;
	//std::cin.get();
	return(point);

}


float minValue(struct node* node) 
{ 
	struct node* current = node; 

  // loop down to find the leftmost leaf 
  while (current->left != NULL) { 
    current = current->left; 
  } 
  cout<<current->data<<" is the minimum at line "<<current->line_number;
  std::cin.get();
  return(current->data); 
}

float maxValue(struct node* node) 
{ 
  struct node* current = node; 

  // loop down to find the leftmost leaf 
  while (current->right != NULL) { 
    current = current->right; 
  } 
  cout<<current->data<<" is the maximum at line "<<current->line_number;
  std::cin.get();
  return(current->data); 
}

void printTree(struct node* point) 
{ 
  if (point == NULL) return; 

  printTree(point->left); 
  cout<<point->data<<"\n";
  //std::cin.get();
  printTree(point->right); 
 
}

void find_median(struct node* point)
{

	if (point == NULL) return;
	find_median(point->left);
	runs++;
	//cout<<point->data<<"\n";
	//cout<<runs;
	//std::cin.get();
	if (runs == count/2)  
	{
	cout<<point->data<<"is the median at line "<<point->line_number<<"\n";
	}

	find_median(point->right); 
	
}


int main()
{

	int numberValues;
	minValue(inserting());
	numberValues = count;
	maxValue(inserting());
	printTree(inserting()); 
	find_median(inserting());
	cout<<numberValues<<" items in table";
	std::cin.get();

	return 0;

}

[mpj88]

Am i best outputting the numbers into an array and then working out the middle from there?

[Computergeek01]

To tell you the truth? No, this kind of thing is perfect for a vector but I'm assuming for one reason or another you can't use that data type. It'll take me a minute to go over your code.

[mpj88]

Never used/heard of vectors. Ok thanks for your help btw!

I'm thinking that its better just to output the numbers into an array and then get the min, max and median from the array as at the moment I'm calling the "inserting" function 3 times. And a lot of this assignment is based on efficiency.

[Computergeek01]

If you know how big the data set is going to be then using an array is fine, otherwise take a look at this: http://www.cplusplus.com/reference/stl/vector/

These will be dynamically sized so there is no need to predict the largest possible data set and make your array a mass of wasted space.

[mpj88]

I don't think I'm going to have time to learn vectors as this has to be in on Monday and this has taken me nearly a week!

I suppose I'm going to have to pass through one loop of "inserting" as this will count the number of items so i know how big an array to make.

But i could also change the way min and max are found by just watching the numbers that are being entered and if its larger than the current max then replace that and vice-versa for the min.

[Computergeek01]

Honestly, I see things in here that you may take a hit for in grade points.

- There are a few places where memory is going to "leak".

- You are opening "test.txt" every time the Struct node inserting() function is being called, this isn't ideal if you're being graded on efficency.

- Your "node" structure should probably be a class at this point. This you may not get docked for but it's good to know when to use which one.

That's just what I see so far. You're doing more work then you have to and I think that is what is getting you stuck in this hole.

EDIT: As a side note this doesn't even compile for me. I'm looking into why that is right now, and no it isn't the inclusion of "sdafx" I know enough to cut that out.

REEDIT: I found out why, "count" was declared in some other header file. And this is why we don't use global variables in headers!

[Computergeek01]

What's going on with "struct node* inserting()"? You should be using a loop for this kind of work, something like this:

struct node* inserting()
{

	float x;
	int line_number = 1;
                node* point = NULL;
	
	ifstream inFile;
	
	inFile.open("test.txt");
    if (!inFile) {
        cout << "Unable to open file";
	std::cin.get();
        exit(1); // terminate with error
    
	}
        while(inFile)
           { //Start of "while(inFile) Loop, this runs while inFile is true, meaning it is not at the eof
	inFile >> x;

	
	point = insert(point, x, line_number);
	
	line_number++;

                                      } //End of the "while(inFile) Loop
	inFile.close();

EDIT: Sorry, wow just spotted a hole in my loop here :p I need to test this stuff before I post it. I think I fixed it. I'm kind of in a rush not to get ninja'd

[Computergeek01]

What is going on with lines 86 and 91? The functions are returning a node that contains data but it isn't being stored anywhere.

EDIT: Screw it, do you know how to use a class? http://www.cplusplus.com/doc/tutorial/classes/

It would do wonders for the organization of this code if "node" was part of a class with member functions and a constructor. In fact I'm going to "crack" a beginner forum rule and say here is some of your prototype:

class NodeTree 
{
   private:
        int LineNumber;
        int count;
        int runs;
        ifstream inFile; /*This may be easier for you if it were a member of the class*/

    public:
        NodeTree(); /*This is our constuctor*/

        node mynode; 
/*I don't like making members public but this makes it easier to plug into your code */
        node* Insert(node*, float);
/*line_number is now a private part of the NodeTree class */
        float minValue(node*);
        float maxValue(node*);
// Give the rest a shot and I'll help you if I can 

REEDIT: I forgot to give minValue and maxValue a data return type, that's what I get for rushing.

[ne555]

"count" was declared in some other header file. And this is why we don't use global variables in headers!

That is why we use namespaces. (I guess is std::count from algorithm).

        while(inFile)
           { //Start of "while(inFile) Loop, this runs while inFile is true, meaning it is not at the eof
	inFile >> x;

	//what if here inFIle is not Ok
	point = insert(point, x, line_number);

//change it to
while( inFile>>x ){
  //do stuff to x 

You better try to encapsulate the behaviour in a class Tree. That inserting is confusing and you should call it only one time.
Also wrap find_median, so you don't forget to reset "runs"

[Computergeek01]

Although I like your suggestion for the while loop because it looks better, I'm curious as to what you mean by

what if here inFile is not OK

? If inFile was at the eof then the loop would not have executed. Am I forgetting about something? (This is for me not the OP's)

[ne555]

Sorry, my mistake. I thought that the eof was not set till you read it, instead of the last one.

Edit: Sorry, I misread it again.

	while( input ){
		int var;
		input >> var;
		if( input.fail() ){
			cout << "crap ";
		}
		cout << var << endl;
	}

input: 1 2 3
1
2
3
crap 3

This works, but I'm not so sure about it

while( !input.eof() ){
  input>>var;