Hi everybody,
I really need some help, I posted a question about a week ago about binary search trees and got some good feedback but I am still having trouble, I have a program written, that takes in ten values and puts them into a bst, it traverses the tree in the three standard ways, and also outputs the level of each node. I need to find the minimum and maximum leaf level. (these are the lowest number level that contains a leaf and the highest number level that contains a leaf. I have the entire program written excepot this last part, finding the min and max leaf level. could you guys please help me do this? I'm really struggling with it. Thanks for everything, everyone is great here. I will post the code below
[code]
#include

const int nil = 0;
int treeCount = -1;
int min;
int max;
int temp1, temp2;
int array1[6];
int array2[6];
float avgmin, avgmax;
//=========================================================================
class treenode_type //declaration of class
{
public:
int info;
treenode_type *left;
treenode_type *right;
};

//==========================================================================
void setleft(int x);
void setright(int x);
void inorder(treenode_type *p);
void preorder(treenode_type *p);
void postorder(treenode_type *p);
void findLevel(treenode_type *p);
treenode_type *p, *q, *root;
int number;

//==========================================================================

int main()
{
for(int k=1; k <= 5; k++)
{

max = 0;
min = 0;
int i = 1;
cout << "Enter first value: ";
cin >> number;
cout << number << "
";
root = new treenode_type;
(*root).info = number;
(*root).left = nil;
(*root).right = nil;
cout << "Enter the other nine values:
";

while (i <= 9)
{
cin >> number;
p = root;
q = p;
while ((number != (*p).info) && (q != nil))
{
p = q;
if (number < (*p).info)
q = (*p).left;
else
q = (*p).right;
}

if (number == (*p).info)
{
cout << number << " is a duplicate
";
}
else if (number < (*p).info) //sets node to left if number is less than p.info
{
setleft(number);
cout << number << " is a left child of " << (*p).info << "
";
}
else //sets node to right if number is greater than p.info
{
setright(number);
cout << number << " is a right child of " << (*p).info << "
";
}

i++;
}

cout << "
The tree traversed INORDER is:
";
p = root;
inorder(p);
cout << "
The tree traversed PRE-ORDER is:
";
p = root;
preorder(p);
cout << "
The tree traversed POST-ORDER is:
";
p = root;
postorder(p);
cout << "
The level of each node is:
";
p = root;
findLevel(p);
cout<<"The Minimum leaf level is "<< min <<"
";
cout<<"The Maximum leaf level is "<< max <<"
";
array1[k] = min;
array2[k] = max;

cout << endl;
cout << endl;
}

for(int i=1;i<5;i++)
{
temp1=array1[i];
avgmin=avgmin+temp1;
temp2=array2[i];
avgmax=avgmax+temp2;
}
avgmin=avgmin/5;
avgmax=avgmax/5;
cout<<"
The average min leaf node is "<<avgmin;
cout<<"
The average max leaf node is "<<avgmax;

cout << endl;
cout << endl;

return 0;
}

//=========================================================================================

//* * * * * Sets Node to Left * * * * *
void setleft(int x)
{
treenode_type *q;
q = new treenode_type;
(*q).info = x;
(*q).left = nil;
(*q).right = nil;
(*p).left = q;
}

//* * * * * Sets Node to Right * * * * *
void setright(int x)
{
treenode_type *q;
q = new treenode_type;
(*q).info = x;
(*q).left = nil;
(*q).right = nil;
(*p).right = q;
}

//* * * * * Inorder Traversal * * * * *
void inorder(treenode_type *r)
{
if (r != nil)
{
inorder ((*r).left);
cout << (*r).info << "
";
inorder ((*r).right);
}
}

//* * * * * Pre-order Traversal * * * * *
void preorder(treenode_type *r)
{
if (r!= nil)
{
cout << (*r).info << "
";
preorder ((*r).left);
preorder ((*r).right);
}
}

//* * * * * Post-order Traversal * * * * *
void postorder(treenode_type *r)
{
if (r!= nil)
{
postorder ((*r).left);
postorder ((*r).right);
cout << (*r).info << "
";
}
}

//* * * * * To find level of each node * * * * *
void findLevel(treenode_type *r)
{
if (r != nil)
{
treeCount = treeCount + 1;
findLevel ((*r).left);
cout << (*r).info << " is at level # "<< treeCount <<"
";
if((*r).left == nil && (*r).right == nil)//this part is
{
if(treeCount < min) //where it is
min = treeCount;
else
max = treeCount; //a problem
}
findLevel ((*r).right);
treeCount = treeCount - 1;
}

}

[/code]

• I've tried to fix your problem with all my heart. But I'm not sure this is what you want.. ^^

I modified findLevel() function and created two new functions below.

Although this couldn't slove the problem you could get some idea from this..

Good Luck..

void findLevel(treenode_type *r)
{
if (r != nil)
{
min = getLeftNodeLevel(r);
max = getRightNodeLevel(r);
cout << "Minimum value Level of left most leaf is : " << min << endl;
cout << "Maximum value level of right most leaf is : " << max << endl;
}

}

int getLeftNodeLevel(treenode_type *r)
{
if(r != nil)
{
treeCount++;
getLeftNodeLevel(r->left);
}
return treeCount+1;
}

int getRightNodeLevel(treenode_type *r)
{
if(r != nil)
{
treeCount++;
getLeftNodeLevel(r->right);
}
return treeCount+1;
}

: Hi everybody,
: I really need some help, I posted a question about a week ago about binary search trees and got some good feedback but I am still having trouble, I have a program written, that takes in ten values and puts them into a bst, it traverses the tree in the three standard ways, and also outputs the level of each node. I need to find the minimum and maximum leaf level. (these are the lowest number level that contains a leaf and the highest number level that contains a leaf. I have the entire program written excepot this last part, finding the min and max leaf level. could you guys please help me do this? I'm really struggling with it. Thanks for everything, everyone is great here. I will post the code below
: [code]
: #include
:
: const int nil = 0;
: int treeCount = -1;
: int min;
: int max;
: int temp1, temp2;
: int array1[6];
: int array2[6];
: float avgmin, avgmax;
: //=========================================================================
: class treenode_type //declaration of class
: {
: public:
: int info;
: treenode_type *left;
: treenode_type *right;
: };
:
: //==========================================================================
: void setleft(int x);
: void setright(int x);
: void inorder(treenode_type *p);
: void preorder(treenode_type *p);
: void postorder(treenode_type *p);
: void findLevel(treenode_type *p);
: treenode_type *p, *q, *root;
: int number;
:
: //==========================================================================
:
: int main()
: {
: for(int k=1; k <= 5; k++)
: {
:
: max = 0;
: min = 0;
: int i = 1;
: cout << "Enter first value: ";
: cin >> number;
: cout << number << "
";
: root = new treenode_type;
: (*root).info = number;
: (*root).left = nil;
: (*root).right = nil;
: cout << "Enter the other nine values:
";
:
: while (i <= 9)
: {
: cin >> number;
: p = root;
: q = p;
: while ((number != (*p).info) && (q != nil))
: {
: p = q;
: if (number < (*p).info)
: q = (*p).left;
: else
: q = (*p).right;
: }
:
: if (number == (*p).info)
: {
: cout << number << " is a duplicate
";
: }
: else if (number < (*p).info) //sets node to left if number is less than p.info
: {
: setleft(number);
: cout << number << " is a left child of " << (*p).info << "
";
: }
: else //sets node to right if number is greater than p.info
: {
: setright(number);
: cout << number << " is a right child of " << (*p).info << "
";
: }
:
: i++;
: }
:
: cout << "
The tree traversed INORDER is:
";
: p = root;
: inorder(p);
: cout << "
The tree traversed PRE-ORDER is:
";
: p = root;
: preorder(p);
: cout << "
The tree traversed POST-ORDER is:
";
: p = root;
: postorder(p);
: cout << "
The level of each node is:
";
: p = root;
: findLevel(p);
: cout<<"The Minimum leaf level is "<< min <<"
";
: cout<<"The Maximum leaf level is "<< max <<"
";
: array1[k] = min;
: array2[k] = max;
:
: cout << endl;
: cout << endl;
: }
:
: for(int i=1;i<5;i++)
: {
: temp1=array1[i];
: avgmin=avgmin+temp1;
: temp2=array2[i];
: avgmax=avgmax+temp2;
: }
: avgmin=avgmin/5;
: avgmax=avgmax/5;
: cout<<"
The average min leaf node is "<<avgmin;
: cout<<"
The average max leaf node is "<<avgmax;
:
: cout << endl;
: cout << endl;
:
: return 0;
: }
:
: //=========================================================================================
:
: //* * * * * Sets Node to Left * * * * *
: void setleft(int x)
: {
: treenode_type *q;
: q = new treenode_type;
: (*q).info = x;
: (*q).left = nil;
: (*q).right = nil;
: (*p).left = q;
: }
:
:
: //* * * * * Sets Node to Right * * * * *
: void setright(int x)
: {
: treenode_type *q;
: q = new treenode_type;
: (*q).info = x;
: (*q).left = nil;
: (*q).right = nil;
: (*p).right = q;
: }
:
:
: //* * * * * Inorder Traversal * * * * *
: void inorder(treenode_type *r)
: {
: if (r != nil)
: {
: inorder ((*r).left);
: cout << (*r).info << "
";
: inorder ((*r).right);
: }
: }
:
: //* * * * * Pre-order Traversal * * * * *
: void preorder(treenode_type *r)
: {
: if (r!= nil)
: {
: cout << (*r).info << "
";
: preorder ((*r).left);
: preorder ((*r).right);
: }
: }
:
: //* * * * * Post-order Traversal * * * * *
: void postorder(treenode_type *r)
: {
: if (r!= nil)
: {
: postorder ((*r).left);
: postorder ((*r).right);
: cout << (*r).info << "
";
: }
: }
:
: //* * * * * To find level of each node * * * * *
: void findLevel(treenode_type *r)
: {
: if (r != nil)
: {
: treeCount = treeCount + 1;
: findLevel ((*r).left);
: cout << (*r).info << " is at level # "<< treeCount <<"
";
: if((*r).left == nil && (*r).right == nil)//this part is
: {
: if(treeCount < min) //where it is
: min = treeCount;
: else
: max = treeCount; //a problem
: }
: findLevel ((*r).right);
: treeCount = treeCount - 1;
: }
:
: }
:
: [/code]
:

• To finish your assignment, one solution is to add these methods:
[code]
//=========================================================================
class treenode_type //declaration of class
{
public:
int info;
treenode_type *left;
treenode_type *right;

int findMin(int nodelevel)
{
int minLeft, minRight, ret;
[green]// find minimum node level for each dependent tree[/green]
minLeft = (left == NULL ? -1 : left->findMin(nodelevel + 1));
minRight = (right == NULL ? -1 : right->findMin(nodelevel + 1));

[green]// if no dependent nodes, return the input branch level[/green]
if (minLeft < 0 && minRight < 0) ret = nodelevel;
[green]// if one of the nodes is NULL< use value for other node[/green]
else if (minLeft < 0) ret = minRight;
else if (minRight < 0) ret = minLeft;
[green]// otherwise return smaller value of right or left[/green]
else ret = (minLeft < minRight ? minLeft : minRight);
return ret;
}

int findMax(int nodelevel)
{
int maxLeft, maxRight, ret = nodelevel;
[green]// find manimum node level for each dependent tree[/green]
maxLeft = (left == NULL ? -1 : left->findMax(nodelevel + 1));
maxRight = (right == NULL ? -1 : right->findMax(nodelevel + 1));

[green]// get greater of right or left level[/green]
ret = (maxLeft > maxRight ? maxLeft : maxRight);
[green]// return greater of right/left or this node, if no sub branches[/green]
return (nodelevel > ret ? nodelevel : ret);
}
};[/code]
call them like this:
[code]
[green]// Call new methods [/green]
cout << "The Minimum leaf level is " << root->findMin(0) << "
";
cout << "The Maximum leaf level is " << root->findMax(0) << "
";[/code]
• [red]
tom sw, thanks so much for all your help, you have been great but I really am at a loss for this stuff. I'm not sure how to change it to fit it into my program, I don't know what a lot of those symbols mean. I was taught differently and I'm not getting it. thanks for the solution though. any chance you could translate it for me? thanks for everything, really.
[/red]

: To finish your assignment, one solution is to add these methods:
: [code]
: //=========================================================================
: class treenode_type //declaration of class
: {
: public:
: int info;
: treenode_type *left;
: treenode_type *right;
:
: int findMin(int nodelevel)
: {
: int minLeft, minRight, ret;
: [green]// find minimum node level for each dependent tree[/green]
: minLeft = (left == NULL ? -1 : left->findMin(nodelevel + 1));
: minRight = (right == NULL ? -1 : right->findMin(nodelevel + 1));
:
: [green]// if no dependent nodes, return the input branch level[/green]
: if (minLeft < 0 && minRight < 0) ret = nodelevel;
: [green]// if one of the nodes is NULL< use value for other node[/green]
: else if (minLeft < 0) ret = minRight;
: else if (minRight < 0) ret = minLeft;
: [green]// otherwise return smaller value of right or left[/green]
: else ret = (minLeft < minRight ? minLeft : minRight);
: return ret;
: }
:
: int findMax(int nodelevel)
: {
: int maxLeft, maxRight, ret = nodelevel;
: [green]// find manimum node level for each dependent tree[/green]
: maxLeft = (left == NULL ? -1 : left->findMax(nodelevel + 1));
: maxRight = (right == NULL ? -1 : right->findMax(nodelevel + 1));
:
: [green]// get greater of right or left level[/green]
: ret = (maxLeft > maxRight ? maxLeft : maxRight);
: [green]// return greater of right/left or this node, if no sub branches[/green]
: return (nodelevel > ret ? nodelevel : ret);
: }
: };[/code]
: call them like this:
: [code]
: [green]// Call new methods [/green]
: cout << "The Minimum leaf level is " << root->findMin(0) << "
";
: cout << "The Maximum leaf level is " << root->findMax(0) << "
";[/code]
:

• What things are you not clear on? Is it the use of class methods? Since you are using a class for you list node, I thought you had been exposed to how a class is constructed. The basic theme is that a class holds data and has the methods (aka functions) to perform appropriate operations on that data. A list tree is a perfect example for using class methods, because it bundles the actions performed on the list with the data so is safer to use than a seperate function. I should think you would want all the list manipulation functions to be member methods so as to contain your activities to the class.

If this is intended to be a C program, then the class declaration should not be used, but it is still easy to add the reference to the node to the function. Your functions would look like:
[code] int findMin(treenode_type* node, int nodelevel);
int findMax(treenode_type* node, int nodelevel);[/code]

and the calls would be:
[code][green]// Call new methods [/green]
cout << "The Minimum leaf level is " << findMin(root, 0) << "
";
cout << "The Maximum leaf level is " << findMax(root, 0) << "
";[/code]

The logic would work the same within the functions except where I called left and right as implicitly part of this object, you would use
[blue]node->left [/blue]and [blue]node->right [/blue]
(or [blue](*node).left[/blue])

and the recursive call would be:
[blue]minLeft = findMin((*node).left, nodeLevel + 1); [/blue]

The indirect notation for calling a class method from a pointer is
[red][italic]object[/italic]->[italic]method[/italic] [/red]or [red][italic]object[/italic]->[italic]variable[/italic][/red]
these are equivalent to:
[red][italic](*object)[/italic].[italic]method[/italic] [/red]or[red] [italic](*object)[/italic].[italic]variable[/italic][/red]
its just easier to use the -> notation.

The trinary operator:
[red][italic]cond[/italic] ? [italic]true result[/italic] : [italic]false result [/italic]; [/red]
is often overlooked, but is just a shorthand way to say:
[code]if ([italic]cond[/italic])
[italic]true result[/italic];
else
[italic]false result[/italic]; [/code]

Hope that helps.
You should be able to reformat the class methods into seperate functions as described above and reformat the trinary operators as above. The logic is sound (I built and ran it before posting it earlier), and it does what you want. The logic that you had posted earlier earlier worked OK for the max level, but always gave 0 for the min level. That is because you need to check for a terminal node (no dependeant leaves) before before using that for a possible min level. Also, the recursive method I give here returns the min or max level that has been found from that node, so you do not need to maintain any global variables for the min and max levels (Any time you can cleanly avoid global variables is GOOD).

Take some time to look over this, I think you can figure it out from here. I will be happy to look over anything else you post, if you still need help. Good luck.

: [red]
: tom sw, thanks so much for all your help, you have been great but I really am at a loss for this stuff. I'm not sure how to change it to fit it into my program, I don't know what a lot of those symbols mean. I was taught differently and I'm not getting it. thanks for the solution though. any chance you could translate it for me? thanks for everything, really.
: [/red]
:
:
: : To finish your assignment, one solution is to add these methods:
: : [code]
: : //=========================================================================
: : class treenode_type //declaration of class
: : {
: : public:
: : int info;
: : treenode_type *left;
: : treenode_type *right;
: :
: : // [red]Add these methods:[/red]
: : int findMin(int nodelevel)
: : {
: : int minLeft, minRight, ret;
: : [green]// find minimum node level for each dependent tree[/green]
: : minLeft = (left == NULL ? -1 : left->findMin(nodelevel + 1));
: : minRight = (right == NULL ? -1 : right->findMin(nodelevel + 1));
: :
: : [green]// if no dependent nodes, return the input branch level[/green]
: : if (minLeft < 0 && minRight < 0) ret = nodelevel;
: : [green]// if one of the nodes is NULL< use value for other node[/green]
: : else if (minLeft < 0) ret = minRight;
: : else if (minRight < 0) ret = minLeft;
: : [green]// otherwise return smaller value of right or left[/green]
: : else ret = (minLeft < minRight ? minLeft : minRight);
: : return ret;
: : }
: :
: : int findMax(int nodelevel)
: : {
: : int maxLeft, maxRight, ret = nodelevel;
: : [green]// find manimum node level for each dependent tree[/green]
: : maxLeft = (left == NULL ? -1 : left->findMax(nodelevel + 1));
: : maxRight = (right == NULL ? -1 : right->findMax(nodelevel + 1));
: :
: : [green]// get greater of right or left level[/green]
: : ret = (maxLeft > maxRight ? maxLeft : maxRight);
: : [green]// return greater of right/left or this node, if no sub branches[/green]
: : return (nodelevel > ret ? nodelevel : ret);
: : }
: : };[/code]
: : call them like this:
: : [code]
: : [green]// Call new methods [/green]
: : cout << "The Minimum leaf level is " << root->findMin(0) << "
";
: : cout << "The Maximum leaf level is " << root->findMax(0) << "
";[/code]
: :
:
:

• And you still owe me that beer if you ever make it out west :-)
• [b][red]This message was edited by otss5353 at 2003-7-1 19:3:48[/red][/b][hr]
tom sw, sorry man, I know you must be getting pissed, but I am still unclear with how to put what you have into my program. I do understand classes, I just don't get this stuff. I will post my code below again, if you could find it in your heart to help me out one more time, I promise not to bother you anymore, I have to finish this by wed. afternoon, then I am finished with this stuff, thanks so much for everything. any changes you could make would be appreciated, I still need to use the kind of code((*r).right and things like that below, it's part of the project.
[code]
#include

const int nil = 0;
int treeCount = -1;
int min;
int max;
int temp1, temp2;
int array1[6];
int array2[6];
float avgmin, avgmax;
//=========================================================================
class treenode_type //declaration of class
{
public:
int info;
treenode_type *left;
treenode_type *right;
};

//==========================================================================
void setleft(int x);
void setright(int x);
void inorder(treenode_type *p);
void preorder(treenode_type *p);
void postorder(treenode_type *p);
void findLevel(treenode_type *p);
treenode_type *p, *q, *root;
int number;

//==========================================================================

int main()
{
for(int k=1; k <= 5; k++)
{

max = 0;
min = 0;
int i = 1;
cout << "Enter first value: ";
cin >> number;
cout << number << "
";
root = new treenode_type;
(*root).info = number;
(*root).left = nil;
(*root).right = nil;
cout << "Enter the other nine values:
";

while (i <= 9)
{
cin >> number;
p = root;
q = p;
while ((number != (*p).info) && (q != nil))
{
p = q;
if (number < (*p).info)
q = (*p).left;
else
q = (*p).right;
}

if (number == (*p).info)
{
cout << number << " is a duplicate
";
}
else if (number < (*p).info) //sets node to left if number is less than p.info
{
setleft(number);
cout << number << " is a left child of " << (*p).info << "
";
}
else //sets node to right if number is greater than p.info
{
setright(number);
cout << number << " is a right child of " << (*p).info << "
";
}

i++;
}

cout << "
The tree traversed INORDER is:
";
p = root;
inorder(p);
cout << "
The tree traversed PRE-ORDER is:
";
p = root;
preorder(p);
cout << "
The tree traversed POST-ORDER is:
";
p = root;
postorder(p);
cout << "
The level of each node is:
";
p = root;
findLevel(p);
cout<<"The Minimum leaf level is "<< min <<"
";
cout<<"The Maximum leaf level is "<< max <<"
";
array1[k] = min;
array2[k] = max;

cout << endl;
cout << endl;
}

for(int i=1;i<5;i++)
{
temp1=array1[i];
avgmin=avgmin+temp1;
temp2=array2[i];
avgmax=avgmax+temp2;
}
avgmin=avgmin/5;
avgmax=avgmax/5;
cout<<"
The average min leaf node is "<<avgmin;
cout<<"
The average max leaf node is "<<avgmax;

cout << endl;
cout << endl;

return 0;
}

//=========================================================================================

//* * * * * Sets Node to Left * * * * *
void setleft(int x)
{
treenode_type *q;
q = new treenode_type;
(*q).info = x;
(*q).left = nil;
(*q).right = nil;
(*p).left = q;
}

//* * * * * Sets Node to Right * * * * *
void setright(int x)
{
treenode_type *q;
q = new treenode_type;
(*q).info = x;
(*q).left = nil;
(*q).right = nil;
(*p).right = q;
}

//* * * * * Inorder Traversal * * * * *
void inorder(treenode_type *r)
{
if (r != nil)
{
inorder ((*r).left);
cout << (*r).info << "
";
inorder ((*r).right);
}
}

//* * * * * Pre-order Traversal * * * * *
void preorder(treenode_type *r)
{
if (r!= nil)
{
cout << (*r).info << "
";
preorder ((*r).left);
preorder ((*r).right);
}
}

//* * * * * Post-order Traversal * * * * *
void postorder(treenode_type *r)
{
if (r!= nil)
{
postorder ((*r).left);
postorder ((*r).right);
cout << (*r).info << "
";
}
}

//* * * * * To find level of each node * * * * *
void findLevel(treenode_type *r)
{
if (r != nil)
{
treeCount = treeCount + 1;
findLevel ((*r).left);
cout << (*r).info << " is at level # "<< treeCount <<"
";
if((*r).left == nil && (*r).right == nil)
{
if(treeCount < min)
min = treeCount;
else
max = treeCount;
}
findLevel ((*r).right);
treeCount = treeCount - 1;
}

}

[/code]

• [b][red]This message was edited by tom_sw at 2003-7-2 11:30:31[/red][/b][hr]
: tom sw, sorry man, I know you must be getting pissed, but I am still unclear with how to put what you have into my program. I do understand classes, I just don't get this stuff. I will post my code below again, if you could find it in your heart to help me out one more time, I promise not to bother you anymore, I have to finish this by wed. afternoon, then I am finished with this stuff, thanks so much for everything. any changes you could make would be appreciated, I still need to use the kind of code((*r).right and things like that below, it's part of the project.

Go back to the class methods I wrote out in an earlier message and reformat the pointer calls as in the next message (from r->right to (*r).right, etc). That will cover you.