Binary Tree

[BradleyHeat]

Hey guys, I'm having some trouble with my binary tree for school. It is a data structures class so we are working on learning how to make our own binary trees and encrypt messages. Everything so far is working, except for my delete node function. I'm trying to do it recursively but if you know a better way to do it then please let me know. I will show you parts of my code.

/******** Node *********/
struct node
{
	char data;
	node* right;
	node* left;
};

/******** Binary Tree Class *********/
class BinaryTree
{
private:
	node* root;
	int CountNode(node* n);
	void DeleteNode(node* n);
	void Search(node* n,char item);
	void Put(node* n,char item);
	void Delete(node* n,char item);
	void Remove(node* n);
	void Replace(node* n,char& info);
public:
	BinaryTree():root(0){};
	~BinaryTree(){MakeEmpty(); };

	void MakeEmpty();
	bool IsEmpty(){return !root; };
	char GetItem(char item);
	void PutItem(char item);
	void DeleteItem(char item);
	int CountNodes(){return CountNode(root); };
	char Traverse(char* path);
};

/******** Delete Item Function *********/
void BinaryTree::DeleteItem(char item)
{
	Delete(root, item);
}

void BinaryTree::Delete(node* n,char item)
{
	if(item<n->data)
		Delete(n->left,item);
	else if(item>n->data)
		Delete(n->right,item);
	else
		Remove(n->data);
}

void Remove(node* n)
{
	char info;
	node* tempnode;

	tempnode = n;
	if(n->left=='\0')
	{
		n=n->right;
		delete tempnode;
	}
	else if(n->right=='\0')
	{
		n=n->left;
		delete tempnode;
	}
	else
	{
		Replace(n->left,info); //right here says replace is undefined..
		n->data = info;
		delete n->left;
	}
}

void BinaryTree::Replace(node* n,char& info)
{
	while(n->right!='\0')
	{
		n=n->right;
		info=n->data;
	}
}

So if you guys could look over my code and tell me what is wrong with my delete node function and help me fix it, that could help me a lot.

-BradleyHeat

[BradleyHeat]

Sorry, really need help.

bump.

[jain amit 14]

/******** Delete Item Function *********/
void BinaryTree::DeleteItem(char item)
{
Delete('\0', root,item);
}

void BinaryTree::Delete(node* pn, node* n,char item)
{
//pn is parent node of n
if(item<n->data)
Delete(n,n->left,item);
else if(item>n->data)
Delete(n,n->right,item);
else
Remove(pn,n);
}

void BinaryTree::Remove(node* pn, node* n)
{
char info;
node* tempnode;

tempnode = n;
//check if left or right child is null
if(n->left=='\0' || n->right=='\0')
{
//if n is left child of pn
if(pn->left == n)
{
//if n left child is null but right child is not null
if(n->left=='\0' && n->right!='\0')
pn->left=n->right;
//If n left child is not null but right child is null
else if(n->left!='\0')
pn->left=n->left;
//If n left child is null and right child is null
else
pn->left = '\0';
delete tempnode;
}
//if n is right child of pn
else if(pn->right == n)
{
if(n->left=='\0' && n->right!='\0')
pn->right=n->right;
else if(n->left!='\0')
pn->right=n->left;
else
pn->right = '\0';
delete tempnode;
}
}
else
{
//go to left child and search the rightmost of that left chlid
node* tmpleft = n->left;
node* ptmpleft = n;
//if left child of n does not have right child.
if(tmpleft->right == '\0')
{
if(pn->left == n)
pn->left = tmpleft;
else
pn->right = tmpleft;

tmpleft->right = n->right;
}
else
{
//search the rightmost child of left child of n
while (tmpleft->right != '\0')
{
ptmpleft = tmpleft;
tmpleft = tmpleft->right;
}

node* mostrchild = tmpleft;
ptmpleft->right = tmpleft->left;
if(pn->left == n)
pn->left = mostrchild;
else
pn->right = mostrchild;
mostrchild->left = n->left;
mostrchild->right = n->right;
}
delete tempnode;
}
}

[BradleyHeat]

Please learn to show code, this is really hard to read.

You aren't really explaining what I did wrong and how you are fixing it. Just seems like you're changing my code how you see fit because that is how you do things. I'd like to keep my code as close to what I have as possible, just please explain what is wrong with it, and what to do to fix it. You changed stuff that didn't really need changing, what you did would make me have to go back and change my whole program (because I only showed you a little bit of it.)

This wasn't very helpful, sorry.

[naraku9333]

void Remove(node* n) should be void BinaryTree::Remove(node* n)

[BradleyHeat]

Wow I can't believe I didn't see that before. Thanks, having a fresh set of eyes always helps I guess :p