Scribd
Upload
7 views

BST CPP

Bst tree C++

Uploaded by

umar playsyt
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
7 views

BST CPP

Bst tree C++

Uploaded by

umar playsyt
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 3

#include "BST.

h"

BST::BST() : root_ptr(nullptr) {}

BST::~BST() {
destroy_tree(root_ptr);
}

Node* BST::insert(Node* node, int value) {


if (node == nullptr) {
return new Node(value);
}
if (value < node->data) {
node->left = insert(node->left, value);
} else if (value > node->data) {
node->right = insert(node->right, value);
} else {
node->count++;
}
return node;
}

Node* BST::remove(Node* node, int value, bool& found) {


if (node == nullptr) {
return node;
}
if (value < node->data) {
node->left = remove(node->left, value, found);
} else if (value > node->data) {
node->right = remove(node->right, value, found);
} else {
found = true;
if (node->count > 1) {
node->count--;
} else {
if (node->left == nullptr) {
Node* temp = node->right;
delete node;
return temp;
} else if (node->right == nullptr) {
Node* temp = node->left;
delete node;
return temp;
}
Node* temp = findMin(node->right);
node->data = temp->data;
node->count = temp->count;
temp->count = 1;
node->right = remove(node->right, temp->data, found);
}
}
return node;
}

Node* BST::findMin(Node* node) {


while (node && node->left != nullptr) {
node = node->left;
}
return node;
}

void BST::inOrder(Node* node) {


if (node != nullptr) {
inOrder(node->left);
std::cout << node->data << "(" << node->count << ") ";
inOrder(node->right);
}
}

void BST::destroy_tree(Node* node) {


if (node) {
destroy_tree(node->left);
destroy_tree(node->right);
delete node;
}
}

void BST::insert(int value) {


root_ptr = insert(root_ptr, value);
}

void BST::remove(int value) {


bool found = false;
root_ptr = remove(root_ptr, value, found);
if (!found) {
std::cout << "Value " << value << " not found in the tree." << std::endl;
} else {
std::cout << "Value " << value << " removed from the tree." << std::endl;
}
}

void BST::inorder() {
inOrder(root_ptr);
std::cout << std::endl;
}

int BST::count(int value) {


Node* current = root_ptr;
while (current != nullptr) {
if (value == current->data) {
return current->count;
} else if (value < current->data) {
current = current->left;
} else {
current = current->right;
}
}
return 0;
}

bool BST::searchtree(int value, int& comparisons, int& level) {


Node* current = root_ptr;
comparisons = 0;
level = 0;
while (current != nullptr) {
comparisons++;
if (value == current->data) {
return true;
} else if (value < current->data) {
current = current->left;
} else {
current = current->right;
}
level++;
}
return false;
}

You might also like