Initializes an empty binary tree. The constructor sets the root pointer to 'nullptr', indicating that the tree starts empty.
template <typename T>
struct Node
{
T data;
Node *right;
Node *left;
Node *parent;
Node(T data, Node *parent = nullptr) : right(nullptr), left(nullptr), data(data), parent(parent) {}
};
template <typename T>
BinaryTree<T>::BinaryTree(/* args */)
{
this->root = nullptr;
}Destroys the binary tree by recursively deleting all its nodes, starting from the root. This method ensures all dynamically allocated memory is properly freed.
template <typename T>
void BinaryTree<T>::destroyTree(Node<T> *node)
{
if (node)
{
destroyTree(node->left);
destroyTree(node->right);
delete node;
}
}
template <typename T>
BinaryTree<T>::~BinaryTree()
{
this->destroyTree(this->root);
}Inserts a new node with a specified value into the binary tree. If the tree is empty, the new node becomes the root. Otherwise, the method finds the correct position for the new node to maintain the binary search properties.
template <typename T>
void BinaryTree<T>::insert(T value)
{
if (this->root == nullptr)
this->root = new Node<T>(value);
else
{
Node<T> *temp = this->root;
while (temp != nullptr)
{
if (temp->data >= value)
{
if (temp->left == nullptr)
{
temp->left = new Node<T>(value, temp);
temp = temp->left; // to force temp nullptr after creation
}
temp = temp->left;
}
else
{
if (temp->right == nullptr)
{
temp->right = new Node<T>(value, temp);
temp = temp->right; // to force temp nullptr after creation
}
temp = temp->right;
}
}
}
}Deletes a node with the given value. The tree may undergo reorganization if the deleted node has children, ensuring that the binary search property is maintained.
template <typename T>
void BinaryTree<T>::insertPreorder(Node<T> *node)
{
if (node)
{
this->insert(node->data);
this->insertPreorder(node->left);
this->insertPreorder(node->right);
}
}
template <typename T>
void BinaryTree<T>::deleteNode(T value)
{
if (!this->root)
return;
else if (this->root->data == value)
{
Node<T> *current = this->root;
if (this->root->right != nullptr)
{
this->root = root->right;
this->insertPreorder(current->left);
}
else if (this->root->left != nullptr)
{
this->root = root->left;
this->insertPreorder(current->right);
}
std::cout << current->data << " deleted(Root)" << std::endl;
delete current;
}
else
{
Node<T> *current = this->search(value);
if (current != nullptr)
{
Node<T> *parent = current->parent;
if (current->data > parent->data)
{
parent->right = nullptr;
}
else
{
parent->left = nullptr;
}
this->insertPreorder(current->right);
this->insertPreorder(current->left);
std::cout << current->data << " deleted" << std::endl;
delete current;
}
else
{
std::cout << value << " Not Found" << std::endl;
}
}
}Searches for a node with a specific value. Starts from the root and navigates through the tree. Returns the node if found or 'nullptr' if the node is not in the tree.
template <typename T>
Node<T> *BinaryTree<T>::search(T value)
{
Node<T> *temp = this->root;
bool found = false;
bool traversed = false;
while (!found && !traversed)
{
if (temp->data > value)
if (temp->left == nullptr)
traversed = true;
else
temp = temp->left;
else if (temp->data < value)
if (temp->right == nullptr)
traversed = true;
else
temp = temp->right;
else
found = true;
}
return found ? temp : nullptr;
}template <typename T>
void BinaryTree<T>::inorder(Node<T> *node)
{
if (node)
{
this->inorder(node->left);
std::cout << node->data << " ";
this->inorder(node->right);
}
}
template <typename T>
void BinaryTree<T>::inorder()
{
std::cout << "Inorder: ";
this->inorder(this->root);
std::cout << std::endl;
}#include <iostream>
#include "BinaryTree.h"
int main(){
BinaryTree<int> *tree = new BinaryTree<int>();
tree->insert(31);
tree->insert(13);
tree->insert(23);
tree->insert(54);
tree->insert(72);
tree->insert(91);
tree->inorder();
tree->deleteNode(14);
tree->inorder();
tree->deleteNode(15);
tree->inorder();
tree->deleteNode(13);
tree->inorder();
tree->deleteNode(31);
tree->inorder();
tree->deleteNode(54);
tree->inorder();
tree->deleteNode(13);
tree->inorder();
tree->~BinaryTree();
std::cout << "Tree destroyed" << std::endl;
return 0;
}Comments
Be the first one to comment!