Binary Search Tree - RemoveNodeFunction.

[hazardnguyen]

I have 1 problem when I want to delete a node in tree.I think problem in 3 function
1/RemoveRoot().
2/RemoveMatch(Node *parent, Node *match, bool left);
3/Node *ReturnNodePrivate(int val, Node *tmp)
Here is the code:

  #include<iostream>

using namespace std;

class Tree
{
private:
	struct Node
	{
		int c;
		Node *left;
		Node *right;
	};
	Node *top;
	void AddLeafPrivate(int val, Node *tmp)
	{
		if (top == NULL)
		{
			top = CreateLeaf(val);
		}
		else if (val < tmp->c)
		{
			if (tmp->left == NULL)
			{
				tmp->left = CreateLeaf(val);
			}
			else
			{
				AddLeafPrivate(val, tmp->left);
			}
		}
		else if (val > tmp->c)
		{
			if (tmp->right == NULL)
			{
				tmp->right = CreateLeaf(val);
			}
			else
			{
				AddLeafPrivate(val, tmp->right);
			}
		}
		else
		{
			cout << "This value " << val << " has already added in tree !!!" << endl;
		}
	}

	void infixPrivate(Node *tmp)
	{
		if (tmp != NULL)
		{
			if (tmp->left != NULL)
			{
				infixPrivate(tmp->left);
			}
			cout << tmp->c << " ";
			if (tmp->right != NULL)
			{
				infixPrivate(tmp->right);
			}

		}
	}

	Node *ReturnNodePrivate(int val, Node *tmp)
	{
		if (tmp != NULL)
		{
			if (tmp->c == val)
			{
				return tmp;
			}
			else if (val < tmp->c)
			{
				return ReturnNodePrivate(val, tmp->left);
			}
			else if (val > tmp->c)
			{
				return ReturnNodePrivate(val, tmp->right);
			}
		}
		else
		{
			return NULL;
		}
	}

	int FindTheSmallestPrivate(Node *tmp)
	{
		if (top == NULL)
		{
			cout << "The Tree is empty !!!" << endl;
		}
		else
		{
			if (tmp->left == NULL)
			{
				return tmp->c; 
			}
			else
			{
				FindTheSmallestPrivate(tmp->left);
			}
		}
	}

	void RemoveNodePrivate(int key, Node *tmp)
	{
		if (top != NULL)
		{
			if (top->c == key)
			{
				RemoveRoot();
			}
			else if (key < tmp->c && tmp->left != NULL)
			{
				tmp->left->c == key ?
					RemoveMatch(tmp,tmp->left,true) :
					RemoveNodePrivate(key, tmp->left);
			}
			else if (key > tmp->c && tmp->right != NULL)
			{
				tmp->right->c == key ?
					RemoveMatch(tmp,tmp->right,false) :
					RemoveNodePrivate(key, tmp->right);
			}
			else
			{
				cout << "The node has value" << key << "tha	t isn't in the tree !!" << endl;
			}
		}
		else
		{
			cout << "The Tree is empty !!" << endl;
		}
	}
public:
	
	Tree()
	{
		top = NULL;
	}

	Node *CreateLeaf(int val)
	{
		Node *n = new Node;
		n->c = val;
		n->left = NULL;
		n->right = NULL;
		return n;
	}

	void AddLeaf(int val)
	{
		AddLeafPrivate(val, top);
	}

	void infix()
	{
		infixPrivate(top);
	}

	Node *ReturnNode(int val)
	{
		return ReturnNodePrivate(val, top);
	}

	void PrintChildren(int val)
	{
		Node *tmp = ReturnNode(val);
		if (tmp == NULL)
		{
			cout << "This Value " << val << "don't in the tree !!!" << endl;
		}
		else
		{
			cout << "Parent Node = " << tmp->c << endl;
			tmp->left == NULL ?
				cout << "Left Child = NULL " << endl :
				cout << "Left Child = " << tmp->left->c << endl;

			tmp->right == NULL ?
				cout << "Right Child = NULL " << endl :
				cout << "Right Child = " << tmp->right->c << endl;
		}
	}

	int FindTheSmallest()
	{
		return FindTheSmallestPrivate(top);
	}

	void RemoveNode(int key)
	{
		RemoveNodePrivate(key, top);
	}

	void RemoveRoot()
	{
		if (top != NULL)
		{
			Node *delPointer = top;
			int topkey = top->c;
			int smallestRight;
			//Case 1: 0 Children
			if (top->left == NULL && top->right == NULL)
			{
				top = NULL;
				delete delPointer;
			}
			//Case 2: 1 Children
			else if (top->left != NULL && top->right == NULL)
			{
				top = top->left;
				delPointer->left = NULL;
				delete delPointer;
				cout << "The Root Node has " << topkey << ",was deleted" << endl;
				cout << "The New Root contains the value " << top->c << endl;
			}
			else if (top->left == NULL && top->right != NULL)
			{
				top = top->right;
				delPointer->right = NULL;
				delete delPointer;
				cout << "The Root Node has " << topkey << ",was deleted" << endl;
				cout << "The New Root contains the value " << top->c << endl;
			}
			//Case 3 : 2 Children
			else
			{
				smallestRight = FindTheSmallestPrivate(top->right);
				RemoveNodePrivate(smallestRight, top);
				top->c = smallestRight;
				cout << "The Root Containing key " << topkey <<
					" was overwritten with key " << top->c << endl;
			}	
		}
		else
		{
			cout << "The Tree is empty !!" << endl;
		}
	}

	//Muon Delete Node thi phai tao mot pointer delete = Node muon dele
	void RemoveMatch(Node *parent, Node *match, bool left)
	{
		if (top != NULL)
		{
			Node *delPointer;
			int Matchkey = match->c;
			int smallestRight1;
			//Case 1 : 0 Children
			if (match->left == NULL && match->right == NULL)
			{
				delPointer = match;
				left == true ?
					parent->left == NULL :
					parent->right == NULL;	
				delete delPointer;
			}

			//Case 2: 1 Child
			else if (match->left != NULL && match->right == NULL)
			{
				left == true ?
					parent->left = match->left :
					parent->right = match->left;
				match->left = NULL;
				delPointer = match;
				delete delPointer;
			}
			else if (match->left == NULL && match->right != NULL)
			{
				left == true ?
					parent->left = match->right :
					parent->right = match->right;
				match->right = NULL;
				delPointer = match;
				delete delPointer;
			}
			//Case 3: 2 Children
			else
			{
				smallestRight1 = FindTheSmallestPrivate(match->right);
				RemoveNodePrivate(smallestRight1, match);
				match->c = smallestRight1;
			}
		}
		else
		{
			cout << "Can't remove. The Tree is empty." << endl;
		}
	}
};


void main()
{
	int input = 0;
	Tree root;
	int a[15] = { 50, 76, 21, 32, 64, 15, 52, 14, 100, 83, 2, 3, 70, 87, 82 };
	for (int i = 0; i < 15; i++)
	{
		root.AddLeaf(a[i]);
	}
	
	cout << "Print Inorder form:\n";
	root.infix();
	cout << endl;
	for (int i = 0; i < 2; i++)
	{
		root.PrintChildren(a[i]);
		cout << endl;
	}
	cout << "The Smallest Number = " << root.FindTheSmallest() << endl;
	cout << "Enter value which you want to delete.Enter -1 to end the process." << endl;
	while (input != -1)
	{
		cout << "Delete Node: "; cin >> input;
		if (input != -1)
		{
			root.RemoveNode(input);
			root.infix();
			cout << endl;
		}
	}
}

P/s : You can copy this code and run it to see what is the problem.

[Disch]

P/s : You can copy this code and run it to see what is the problem.

Or you could just tell us.

[hazardnguyen]

Alright , Example :
I have the tree in Inorder form :
2 3 14 15 21 32 50 52 64 70 76 82 83 87 100

I want to delete node contain value : 21 but it just print.

2 3 14 15 32 .

and BinaryTreeTraversal.exe has stopped working.

[Disch]

Line 258 and 259 should probably be assigning (=) null, not comparing (==)

[hazardnguyen]

Thanks ,bro ,i just have solved it :D