trees

mail@pastecode.io avatar
unknown
aql
2 years ago
2.8 kB
1
Indexable
Never
#include<iostream>
#include<conio.h>
using namespace std;
class TNode
{

public:
	int data;
	TNode* left;
	TNode* right;
	TNode();
	TNode(int);
};
class BST
{

public:
	TNode* root;
	BST();
	void insert(TNode*, int); //to insert a node of given value
	void delete_node(TNode*, int); //to search and delete a node of given value
	bool isEmpty(); //to check if the BST is empty or not
	TNode* getParent(TNode*, int); //to return the parent of a given node
};
TNode::TNode()
{
	this->left = NULL;
	this->right = NULL;
}
TNode::TNode(int a)
{
	this->data = a;
	this->left = NULL;
	this->right = NULL;
}
BST::BST()
{
	this->root = NULL;
}
void BST::insert(TNode* root, int key)
{
	TNode* curr = root;
	TNode* parent = NULL;
	if (root == NULL)
	{
		this->root = new TNode(key);
		return;
	}
	while (curr != NULL)
	{
		parent = curr;
		if (key < curr->data)
			curr = curr->left;
		else
			curr = curr->right;
	}
	if (key < parent->data)
	{
		parent->left = new TNode(key);
	}
	else
	{
		parent->right = new TNode(key);
	}
}

void BST::delete_node(TNode* root, int key)
{
	TNode* curr = root;
	TNode* prev = NULL;
	while (curr != NULL && curr->data != key)
	{
		prev = curr;
		if (key < curr->data)
			curr = curr->left;
		else
			curr = curr->right;
	}
	if (curr == NULL)
	{
		cout << "Key " << key << " Not Found In The BST.\n";
		return;
	}
	if (curr->left == NULL || curr->right == NULL) {
		TNode* newCurr;
		if (curr->left == NULL)
			newCurr = curr->right;
		else
			newCurr = curr->left;
		if (prev == NULL)
		{
			this->root = newCurr;
			return;
		}
		if (curr == prev->left)
			prev->left = newCurr;
		else
			prev->right = newCurr;
		delete curr;
	}
	else
	{
		TNode* p = NULL;
		TNode* temp;
		temp = curr->right;
		while (temp->left != NULL) {
			p = temp;
			temp = temp->left;
		}
		if (p != NULL)
			p->left = temp->right;
		else
			curr->right = temp->right;
		curr->data = temp->data;
		delete temp;
	}
	this->root = root;
	cout << "Node deleted" << endl;
}
bool BST::isEmpty() 
{
if(this->root == NULL
	)
	return true
	;
return false;
}

TNode* BST::getParent(TNode* root, int key
)
{
	if
		(root == NULL
			)
	{
		return NULL
			;
	}
	TNode* p = root
		;
	if (p
		->left == NULL && p
		->right == NULL
		)
		return NULL
		;
	if (p
		->left != NULL && p
		->data > key
		)
	{
		p = p
			->left;
		if (p
			->left
			->data == key
			)
			return p;
	}
	if (p
		->right != NULL && p
		->data < key
		)
	{
		p =p->right;
		if (p->right->data == key)
			return p;
	}
	if (p->left != NULL && p->right != NULL)
	{
		if (p->data < key)
			p = p->right;
		else
			p = p->left;
	}
	return p;
}
int main() 
{
 

}