How to display length/width of binary tree

[jimmy5023]

//keith lin, this is one of the original keith program since it's very few. April 29 2011 project 5_2


#include<iostream>
#include<cstring>
using namespace std;

void insertNode(float num);
void deleteNode(float num);
bool isTreeEmpty(void);
float isInTree(float num);
void remove (float num);
void showMenu(void);
void displayL(void);
void displayW(void);

float num;

struct TreeNode
{
	//static const int size = 50;
	float value;
	struct TreeNode *next[2];
};
struct TreeNode* root = NULL;
void deleteNode(float num, TreeNode *&nodePtr);
void makeDeletion(TreeNode *&nodePtr);

int main(void)
{
	cout<<"this program will display the depth and width of the tree of the floats you inserted"<<endl;
	short unsigned int selection;
	float num;
	char answer;

	do 
	{
		cout << "please enter your value ";
		cin >> num;			
		insertNode(num);
		cout << "do you want to enter another value? ";
		cin >> answer;
	} 
		while (toupper(answer)=='Y');
		system("CLS");
		
		
			showMenu();
			cout << "\tSelection --> ";
				cin >> selection;
				cout << endl;
				switch(selection) 
				{
					case 1:
						{
						cout << "please enter your value ";
						cin >> num;			
						insertNode(num);
						cout << endl;
						break;
						}
					case 2:
						{
						cout << "please enter your value you want to delete ";
						cin >> num;			
						remove(num);
						cout << endl;
						break;
						}
					case 3:
						{
						exit(1);
						}
			
					default:
						cout << "Invalid selection!\n";
						cout << "Program will halt!\n";
						exit(1);
				}
				
}




void insertNode(float num)

{
	struct TreeNode *newNode=NULL, *nodePtr = root;
	bool index;
	newNode = new TreeNode;
	if(newNode == NULL) {
		cout << "Dynamic memory allocation failed!\n";
		cout << "Program will halt!\n";
		exit(1);
	}
	newNode->value = num;
	newNode->next[0] = NULL;
	newNode->next[1] = NULL;

	if(isTreeEmpty())  { // check for empty tree
		cout << "Tree was empty . . . ";
		cout<<num<<" will be your root"<<endl;
		root = newNode;
	}
	else {
		index = (newNode->value > nodePtr->value);
		while(nodePtr->next[index] != NULL) {
			nodePtr = nodePtr->next[index];
			index = (newNode->value > nodePtr->value);
		}
		nodePtr->next[index] = newNode;
	}

}


void deleteNode(float num, TreeNode *&nodePtr)
{
	if (isTreeEmpty())
		{
			cout<<"the tree is empty!\n";
			return;
		}
	if(isInTree(num))
	{
		cout<<"the value ("<<num<<") is not in tree!\n\n";
		return;
	}
	if(num==nodePtr->value)
		makeDeletion(nodePtr);
	else
	{
		short int indexx = (num>nodePtr->value);
		deleteNode(num,nodePtr->next[indexx]);
	}
}

void makeDeletion(TreeNode *&nodePtr)
{
	struct TreeNode *tempNodePtr; // used to reattach left sub-tree
	if (nodePtr == NULL)
				cout << "Cannot delete empty node!\n";
	else if (nodePtr->next[1] == NULL) {
				tempNodePtr = nodePtr;
		nodePtr = nodePtr->next[0];  // reattach the left child
				delete [] tempNodePtr;
	}
	else if (nodePtr->next[0] == NULL) {
		tempNodePtr = nodePtr;
				nodePtr = nodePtr->next[1];  // reattach the right child
		delete [] tempNodePtr;
	}
	else {   // case where node to be deleted has 2 children
				// move one node to the right
		tempNodePtr = nodePtr->next[1];
		// go to the end left node
		while(tempNodePtr->next[0] != NULL)
			tempNodePtr = tempNodePtr->next[0];
		// reattach the left subtree
		tempNodePtr->next[0] = nodePtr->next[0];
		tempNodePtr = nodePtr;
				// reattach the right subtree
		nodePtr = nodePtr->next[1];
		delete [] tempNodePtr;
	}

}




void remove (float num)
{
	deleteNode(num, root);
}

bool isTreeEmpty(void)
// This function simply determines if a b-tree is empty!
{
	return (root==NULL);
}


float isInTree(float num)

// If so, it returns the depth at which it is located (1 = root).
// If not, it returns a value of -1.  If the b-tree is empty,
// it returns a value of 0.
{
	struct TreeNode* nodePtr = root;
	float depth = 0;
	bool index;

	if(isTreeEmpty())
		return depth;
	else if(nodePtr->value == num)
		return 1;
	else {
		depth = 1;
		while(nodePtr != NULL && nodePtr->value != num) {
			index = (num > nodePtr->value);
			nodePtr = nodePtr->next[index];
			depth++;  // increment depth as we descend tree
		}
	}

	if(nodePtr == NULL)
		return -1;
	else
		return depth;
}

void showMenu(void)
{
	cout<<"select the following"<<endl;
	cout << "\t 1 - to insert a node\n";
	cout << "\t 2 - to delete a node\n";
	cout << "\t 3 - to exit the program\n";
		
}

how to write the void displayl(void) and void displayw(void)
displaying length and width of the tree.
E.G
i put 34, 65, 32. The length will be 3.

[Zeillinger]

In your example the length is actually the number of nodes in the tree. Checking for that would be simple of you use a recursive function such as (kind of a pseudo-code, your implementation is using a array of pointers instead of right & left which I wouldn't recommend):

int countNodes(TreeNode *root) {
	if (root == NULL)
		return 0;
	return 1 + countNodes(root->left) + countNodes(root->right);
}

As for the width, I assume you are looking for the maximum width of the tree. This is a little more problematic if you aren't dealing with a perfect tree since you have to check the width of every level and only then find the max width. Instead of writing an example, I refer you to the following resource: http://geeksforgeeks.org/?p=7447

[jimmy5023]

Thanks zeillinger, however, i don't really understand your answer.

Why would the length of the code be 1+ countnode(root-left) + countnode(root->right) what's left and right?

[jimmy5023]

hello? anyone? It gives me ALOT of error.

2010\cmpsc\cmpsc 122\project5_2\project5_2\project5_2.cpp(225): error C2678: binary '==' : no operator found which takes a left-hand operand of type 'TreeNode' (or there is no acceptable conversion)
1> d:\program files\vs 2010\vc\include\exception(470): could be 'bool std::operator ==(const std::_Exception_ptr &,const std::_Exception_ptr &)'
1> d:\program files\vs 2010\vc\include\exception(475): or 'bool std::operator ==(std::_Null_type,const std::_Exception_ptr &)'
1> d:\program files\vs 2010\vc\include\exception(481): or 'bool std::operator ==(const std::_Exception_ptr &,std::_Null_type)'
1> d:\program files\vs 2010\vc\include\system_error(408): or 'bool std::operator ==(const std::error_code &,const std::error_condition &)'
1> d:\program files\vs 2010\vc\include\system_error(416): or 'bool std::operator ==(const std::error_condition &,const std::error_code &)'
1> while trying to match the argument list '(TreeNode, int)'
1>d:\spring 2010\cmpsc\cmpsc 122\project5_2\project5_2\project5_2.cpp(227): error C2819: type 'TreeNode' does not have an overloaded member 'operator ->'
1> d:\spring 2010\cmpsc\cmpsc 122\project5_2\project5_2\project5_2.cpp(21) : see declaration of 'TreeNode'
1> did you intend to use '.' instead?
1>d:\spring 2010\cmpsc\cmpsc 122\project5_2\project5_2\project5_2.cpp(227): error C2039: 'left' : is not a member of 'TreeNode'
1> d:\spring 2010\cmpsc\cmpsc 122\project5_2\project5_2\project5_2.cpp(21) : see declaration of 'TreeNode'
1>d:\spring 2010\cmpsc\cmpsc 122\project5_2\project5_2\project5_2.cpp(227): error C2819: type 'TreeNode' does not have an overloaded member 'operator ->'
1> d:\spring 2010\cmpsc\cmpsc 122\project5_2\project5_2\project5_2.cpp(21) : see declaration of 'TreeNode'
1> did you intend to use '.' instead?
1>d:\spring 2010\cmpsc\cmpsc 122\project5_2\project5_2\project5_2.cpp(227): error C2039: 'right' : is not a member of 'TreeNode'
1> d:\spring 2010\cmpsc\cmpsc 122\project5_2\project5_2\project5_2.cpp(21) : see declaration of 'TreeNode'
========== Rebuild All: 0 succeeded, 1 failed, 0 skipped ==========

[ne555]

1+ countnode(root->left) + countnode(root->right);
1: me
countnode(root->left): how many are at my left
countnode(root->right): how many are at my right
----------------------------
total

left: of, pertaining to, or located on or near the side of a person or thing that is turned toward the west when the subject is facing north ( opposed to right).

int countNodes(TreeNode *root) Note that it should receive a pointer.

[Zeillinger]

@ne555, thanks for pointing this out - I haven't noticed.
@OP, as I said, you shouldn't actually use this code. This is only the general idea you should follow when writing such a function, consistent with your design of TreeNode.

[jimmy5023]

I did spot the (Treenode *root) mistake, but i still don't quite get the right left, what is left and right in my situation. Normally in binary tree i know newNode->next[0] is left while newNode->next[1] is right. But it seems it's a difference case in here,

[jimmy5023]

???

[ne555]

newNode->next[0] is left while newNode->next[1] is right

Yep

[jimmy5023]

ok I can sucessfully run it now how to display it?

int countNodes(TreeNode *root) {
	if (root == NULL)
		return 0;
	return 1 + countNodes(root->next[0]) + countNodes(root->next[1]);
}

i tried cout<<countNodes(); doesn't work.

[jimmy5023]

??

[ne555]

http://www.cplusplus.com/forum/articles/40071/#msg218019

[jimmy5023]

'TreeNode' : illegal use of this type as an expression,

so bascially the cout statment should be cout<<countNodes(pass in something i guess?); but i tried but the results are not ideal.

[Zeillinger]

Well, you should pass the root of the tree (to count its nodes).

[jimmy5023]

I am not really fimliar with Binary tree but what i think is we just imagine as if it's a binary tree but it actually isn't. from what i see it's just we inserting numbers by using pointers. As for the "tree" i thought its' treeNode. Since i did not declare any tree to start with i just add in the node right away.

[Zeillinger]

I'm not sure about what you're trying to say here. TreeNode should be the structure implementing a binary tree, nothing is being imagined. I'm a little confused (ans seems like you are, too) so could you post the code you're working with right now?

[jimmy5023]

okay....

//keith lin, this is one of the original keith program since it's very few. April 29 2011 project 5_2


#include<iostream>
#include<cstring>
using namespace std;

void insertNode(float num);
void deleteNode(float num);
bool isTreeEmpty(void);
float isInTree(float num);
void remove (float num);
void showMenu(void);
void displayL(void);
void displayW(void);


float num;

struct TreeNode
{
	//static const int size = 50;
	float value;
	struct TreeNode *next[2];
};
struct TreeNode* root = NULL;
void deleteNode(float num, TreeNode *&nodePtr);
void makeDeletion(TreeNode *&nodePtr);
int countNodes(TreeNode *root);
int main(void)
{
	cout<<"this program will display the depth and width of the tree of the floats you inserted"<<endl;
	short unsigned int selection;
	float num;
	char answer;

	do 
	{
		cout << "please enter your value ";
		cin >> num;			
		insertNode(num);
		cout << "do you want to enter another value?(y/n) ";
		cin >> answer;
	} 
		while (toupper(answer)=='Y');
		system("CLS");
		
		
			showMenu();
			cout << "\tSelection --> ";
				cin >> selection;
				cout << endl;
				switch(selection) 
				{
					case 1:
						{
						cout << "please enter your value ";
						cin >> num;			
						insertNode(num);
						cout << endl;
						break;
						}
					case 2:
						{
						cout << "please enter your value you want to delete ";
						cin >> num;			
						remove(num);
						cout << endl;
						break;
						}
					case 3:
						{
						exit(1);
						}
			
					default:
						cout << "Invalid selection!\n";
						cout << "Program will halt!\n";
						exit(1);
				}
	cout<<countNodes();
	
}




void insertNode(float num)

{
	struct TreeNode *newNode=NULL, *nodePtr = root;
	bool index;
	newNode = new TreeNode;
	if(newNode == NULL) {
		cout << "Dynamic memory allocation failed!\n";
		cout << "Program will halt!\n";
		exit(1);
	}
	newNode->value = num;
	newNode->next[0] = NULL;
	newNode->next[1] = NULL;

	if(isTreeEmpty())  { // check for empty tree
		cout << "Tree was empty . . . ";
		cout<<num<<" will be your root"<<endl;
		root = newNode;
	}
	else {
		index = (newNode->value > nodePtr->value);
		while(nodePtr->next[index] != NULL) {
			nodePtr = nodePtr->next[index];
			index = (newNode->value > nodePtr->value);
		}
		nodePtr->next[index] = newNode;
	}

}


void deleteNode(float num, TreeNode *&nodePtr)
{
	if (isTreeEmpty())
		{
			cout<<"the tree is empty!\n";
			return;
		}
	if(isInTree(num))
	{
		cout<<"the value ("<<num<<") is not in tree!\n\n";
		return;
	}
	if(num==nodePtr->value)
		makeDeletion(nodePtr);
	else
	{
		short int indexx = (num>nodePtr->value);
		deleteNode(num,nodePtr->next[indexx]);
	}
}

void makeDeletion(TreeNode *&nodePtr)
{
	struct TreeNode *tempNodePtr; // used to reattach left sub-tree
	if (nodePtr == NULL)
				cout << "Cannot delete empty node!\n";
	else if (nodePtr->next[1] == NULL) {
				tempNodePtr = nodePtr;
		nodePtr = nodePtr->next[0];  // reattach the left child
				delete [] tempNodePtr;
	}
	else if (nodePtr->next[0] == NULL) {
		tempNodePtr = nodePtr;
				nodePtr = nodePtr->next[1];  // reattach the right child
		delete [] tempNodePtr;
	}
	else {   // case where node to be deleted has 2 children
				// move one node to the right
		tempNodePtr = nodePtr->next[1];
		// go to the end left node
		while(tempNodePtr->next[0] != NULL)
			tempNodePtr = tempNodePtr->next[0];
		// reattach the left subtree
		tempNodePtr->next[0] = nodePtr->next[0];
		tempNodePtr = nodePtr;
				// reattach the right subtree
		nodePtr = nodePtr->next[1];
		delete [] tempNodePtr;
	}

}




void remove (float num)
{
	deleteNode(num, root);
}

bool isTreeEmpty(void)
// This function simply determines if a b-tree is empty!
{
	return (root==NULL);
}


float isInTree(float num)

// If so, it returns the depth at which it is located (1 = root).
// If not, it returns a value of -1.  If the b-tree is empty,
// it returns a value of 0.
{
	struct TreeNode* nodePtr = root;
	float depth = 0;
	bool index;

	if(isTreeEmpty())
		return depth;
	else if(nodePtr->value == num)
		return 1;
	else {
		depth = 1;
		while(nodePtr != NULL && nodePtr->value != num) {
			index = (num > nodePtr->value);
			nodePtr = nodePtr->next[index];
			depth++;  // increment depth as we descend tree
		}
	}

	if(nodePtr == NULL)
		return -1;
	else
		return depth;
}

void showMenu(void)
{
	cout<<"select the following"<<endl;
	cout << "\t 1 - to insert a node\n";
	cout << "\t 2 - to delete a node\n";
	cout << "\t 3 - to exit the program\n";
		
}

int countNodes(TreeNode *root) {
	if (root == NULL)
		return 0;
	return 1 + countNodes(root->next[0]) + countNodes(root->next[1]);
}

line 82 is the problem

[jimmy5023]

??

[LB]

Uh, line 82 is blank...?

[jimmy5023]

81 i mean the cout statement.