1 Replies - 1669 Views - Last Post: 12 December 2012 - 10:52 PM Rate Topic: -----

#1 danglesauce19  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 20-February 12

C++ Binary Trees problem

Posted 10 December 2012 - 10:40 PM

I only need help with finding the maximum leaf level and the minimum leaf level. I got my code to print out something for them but I'm pretty sure it's not right. Please help. Thank you.

Here is the entire code. I have the min and max in the inorder function.
//=========================================================================================
//=========================================================================================

#include <iostream>
using namespace std;

const int nil = 0;
int oneChild = 0;
int twoChildren = 0;
int leafCount = 0;
int maxLeaf = 0;
int minLeaf = 0;
int height;
int level;

class treenode_type		
{
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);
treenode_type *p, *q, *root;
int number;

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

int main()
{
	cout << "Enter first value: \n";
	cin >> number;
	cout << number << " is the root number\n";
	root = new treenode_type;
	(*root).info = number;
	(*root).left = nil;
	(*root).right = nil;
	cout << "Enter 19 more values: \n";
	cin >> number;

	for (int j=0; j<7; j++)
	{
		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";
		}
		else 
		{
			setright(number);
			cout << number << " is a right child of " << (*p).info << "\n";
		}
		cin >> number;
	}

	cout << "The tree traversed INORDER is \n";
	p = root;
	level = -1;
	inorder(p);
	cout << endl << "Number of leaves in the tree are: " << leafCount << endl;
	cout << "Number of nodes with one child: " << oneChild << endl;
	cout << "Number of nodes with two children: " << twoChildren << endl;	
	cout << "Maximum leaf level = " << maxLeaf << endl;
	cout << "Minimum leaf level = " << minLeaf << endl;
	cout << "Height = " << height << endl;
		if (height == minLeaf)
		{
			cout << "Balanced" << endl;
		}
		else
		{
			cout << "Not balanced" << endl;
		}
	cout << endl << "The tree traversed PREORDER is \n";
	p = root;
	preorder(p);
	cout << endl << "The tree traversed POSTORDER is \n";
	p = root;
	postorder(p);
	
}

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

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)
	{
		level = level + 1;
		inorder((*r).left);	
		cout << (*r).info << " (Level " << level << ")" << "\n";
		inorder((*r).right);
		level = level - 1;

		if (((*r).left != nil) && ((*r).right != nil))
		{
			twoChildren ++;
		}
		else if ((((*r).left == nil) && ((*r).right != nil)) || (((*r).left != nil) && ((*r).right == nil)))
		{
			oneChild ++;
		}
		else if (((*r).right == nil) && ((*r).left == nil))
		{
			leafCount ++;
			maxLeaf = level + 1;
			minLeaf = level -1;
		}
		
		height = maxLeaf;
	}
}

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

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";
	}
}



Is This A Good Question/Topic? 0
  • +

Replies To: C++ Binary Trees problem

#2 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1371
  • View blog
  • Posts: 4,750
  • Joined: 19-February 09

Re: C++ Binary Trees problem

Posted 12 December 2012 - 10:52 PM

I suppose for a max level recursive function, you could test the return value of left and right and return the greatest.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1