Binary Trees

[ohsnap1319]

Hello Everyone!

I am currently working on a program that allows the user to select from a menu of options. The options include: insert a node, delete a node, and exit the program. Then after each selected option has been made the program then prints out the height of the tree(that is, the number of levels in the tree counting the root node as a level). I believe I have the code for the program completed but my problem is that I am not sure how to print out the height of the tree. If anyone could help me with this problem that would be awesome! Thanks for any future help! Here is what I have so far:

#include <iostream>
using namespace std;

struct TreeNode {
	float value;
	struct TreeNode *next[2];
};
struct TreeNode *root = NULL;

int insertNode(float num);
void remove(double num);
int deleteNode(double num, TreeNode *&nodePtr);
void makeDeletion(TreeNode *&nodePtr);
bool isEmpty();
bool isinTree(double num);

int main()
{
	int choice; 
	float num, num2;
	char answer;
	do {
	cout << "Please enter a choice from one of these options!\n";
	cout << "1 - Insert a node!\n";
	cout << "2 - Delete a node!\n";
	cout << "3 - Exit the program!\n";
	cin >> choice;
	if(choice==1) {
		cout << "Please enter the value you would like to add to the tree: ";
		cin >> num;
		insertNode(num);
	}
	else if(choice==2) {
		cout << "Please enter the value you would like to delete from the tree: ";
		cin >> num2;
		remove(num2);
	}
	else if(choice==3) {
		cout << "You have selected to exit the program!\n";
		cout << "The program will now halt!\n";
		exit(1);
	}
	else {
		cout << "You have entered an invalid choice!\n";
		cout << "Please enter your choice again from the following options!\n";
		cout << "1 - Insert a node!\n";
		cout << "2 - Delete a node!\n";
		cout << "3 - Exit the program!\n";
		cin >> choice;
	}
	cout << "Would you like to make another selection?: ";
	cin >> answer;
	
	}while(toupper(answer)=='Y');
}

int insertNode(float num)
{
	struct TreeNode *newNode, *nodePtr = root;
	int index;
	newNode = new TreeNode;
	if(newNode == NULL)
		return 1;
	newNode->value = num;
	newNode->next[0] = NULL;
	newNode->next[1] = NULL;
	if(isEmpty()) {
		cout << "Tree was empty...\n";
		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;
	}
	return 0;
}

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

int deleteNode(double num, TreeNode *&nodePtr)
{
	if(isEmpty()) {
		cout << "The tree is empty!\n";
		return 0;
	}
	if(!(isinTree(num))) {
		cout << "That value (" << num << ") is NOT in tree!\n\n";
		return 0;
	}
	if(num==nodePtr->value)
		makeDeletion(nodePtr);
	else {
		short int indexx = (num > nodePtr->value);
		deleteNode(num,nodePtr->next[indexx]);
		return 0;
	}
	return 0;
}

void makeDeletion(TreeNode *&nodePtr)
{
	struct TreeNode *tempNodePtr;
	if (nodePtr == NULL)
		cout << "Cannot delete empty node!\n";
	else if (nodePtr->next[1] == NULL) {
		tempNodePtr = nodePtr;
		nodePtr = nodePtr->next[0];
		delete [] tempNodePtr;
	}
	else if (nodePtr->next[0] == NULL) {
		tempNodePtr = nodePtr;
		nodePtr = nodePtr->next[1];
		delete [] tempNodePtr;
	}
	else {
		tempNodePtr = nodePtr->next[1];
		while(tempNodePtr->next[0] != NULL)
			tempNodePtr = tempNodePtr->next[0];
		tempNodePtr->next[0] = nodePtr->next[0];
		tempNodePtr = nodePtr;
		nodePtr = nodePtr->next[1];
		delete [] tempNodePtr;
	}
}

bool isEmpty()
{
	return (root==NULL);
}

bool isinTree(double num)
{
	struct TreeNode *nodePtr = root;
	short int index;
	while (nodePtr != NULL) {
		if (nodePtr->value == num)
			return true;
		else {
			index = num > nodePtr->value;
			nodePtr = nodePtr->next[index];
		}
	}
	return false;

}

[n4nature]

Foll. func can be called with root node after each insertion and deletion

int printHeight(const nodePtr* const node)
{

                 int lheight=0; int rheight=0;

	if(node->next[0])
		lheight=printHeight(const nodePtr* const node->next[0]);
	if(node->next[1])
		rheight=printHeight(const nodePtr* const node->next[1]);

	return max(lheight, rheight)+1;
}

Warning Note: Your calling functions are not handling error conditions from insertion and deletion functions.

[ohsnap1319]

When I tryed to use your function in my program it gave me like 15 errors and to be honest I don't really know why...Could you possibly show me in the code how you use it to print out the height of the tree after each selection?

[TheBear]

Hi,

here is a corrected version of the function, calling it should be straight forward.

int getHeight(const TreeNode* const node)
{

    int lheight=0;
    int rheight=0;

	if(node->next[0])
	{
		lheight=getHeight(node->next[0]);
	}
	if(node->next[1])
	{
		rheight=getHeight(node->next[1]);
	}

	return max(lheight, rheight)+1;
}

Another thing: At the end of your deletion function, you might have some dangeling pointers.