binary tree help? (C++)

[foreverpsycotic]

ok, for an assignment for class we had to make a program that would build a binary tree, give the preorder, postorder and inorder traversals. The program also has to give the level that the node was on durring the recursive traversals, as well as the number of leaf nodes, nodes with one child, and nodes with 2 children.

so far, my program does all of that except the level the node is on durring the traversal. i cant seem to figure out how to get the level. any help would be appreciated. I am not looking for someone to do the work, only the logic behind so that i can do it myself. but if someone wants to toss me a few lines of code, i wont complain.

heres the code that i have

#include <iostream>
using namespace std;

const int nil = 0;
class treenode_type		    // declaration of class//
{
public:						// Tree node type//
		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 *r);
void postorder(treenode_type *r);
void countNodes(treenode_type *r);
treenode_type *p,*q,*root;
int n, m, c, l;
int number;
void main()
{
    n=0;
	m=0;
	c=0;
	l=0;
	cout << "Enter first value: \n";
	cin >> number;
	cout << number << "\n";
	root = new treenode_type;
	(*root).info = number;
	(*root).left = nil;
	(*root).right = nil;
	cout <<"Enter other numbers terminated by -999\n";
	cin >> number;
	while (number != -999)
	{
		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 \n";
		else if (number < (*p).info)
		{
			setleft(number);
			cout << number <<" is a left child of "<< (*p).info << "\n";
			m++;
			cout << "Located on level " << m << endl;
			if (((*p).left ==nil && (*p).right != nil) || ((*p).right ==nil && (*p).left != nil))
				c++;
			if ((*p).left != nil && (*p).right != nil)
				l++;
		}
		else
		{
			setright(number);
			cout << number <<" is a right child of "<< (*p).info << "\n";
			n++;
			cout << "Located on level " << n << endl;
			if ((*p).left ==nil || (*p).right ==nil)
				c++;
			if ((*p).left != nil && (*p).right != nil)
				l++;
		}
		cin >> number;

	}
	cout << "The tree traversed inorder is \n";
	p = root;
	inorder(p);
	cout << "The tree traversed preorder is \n";
	p = root;
	preorder(p);
	cout << "The tree traversed postorder is \n";
	p = root;
	postorder(p);
	
	cout << "There are " << c << " nodes with one child" << endl;
	cout << "There are " << l << " nodes with 2 children" << endl;
	cout << "There are " << c << " leaf nodes"<< endl;


}

void setleft(int x)
{
	treenode_type *q;
	q = new treenode_type;
	(*q).info = x;
	(*q).left = nil;
	(*q).right = nil;
	(*p).left = q;
}
void setright(int x)
{
	treenode_type *q;
	q = new treenode_type;
	(*q).info = x;
	(*q).left = nil;
	(*q).right = nil;             
	(*p).right = q;
}
void inorder(treenode_type *r)
{
  if (r != nil)
	{
	inorder((*r).left);
	cout << (*r).info << "\n";
	inorder((*r).right);
	}
}
void preorder(treenode_type *r)
{
  if (r != nil)
	{
	cout << (*r).info << "\n";
	preorder((*r).left);	
	preorder((*r).right);
	}
}
void postorder(treenode_type *r)
{
  if (r != nil)
	{
	postorder((*r).left);
	postorder((*r).right);
	cout << (*r).info << "\n";
	}
}

TYIA

 

[SupraDerk]

Ouch, I had to do this program about a year ago, although I didn't have to say what level the node was on.

But maybe you could have a counter while the tree is being built that increments as the levels grow. Like you have your root node, then that node has it's children nodes so you at least have one new level, so increment your counter, then for every sibling node on that level, attach that counter number to them. Then if those sibling nodes in the second row have children nodes, increment your counter again and take note of all the new sibling nodes on the third level and attach that counter number to them.

Hmmm... hope that kind of makes sense

 

[lagged]

heh its finals time.

i took data structures this semester, pretty challenging.

the binary tree class i had to wrote didnt need to keep track of what level you were on, but its pretty easy to figure it out.

like what was said previously, create a counter, the root would be zero and you ++ it as you go. pretty simple.

id probably make the counter a private member of the node class and every time you add a leaf you keep track of the level.