С++
Доброго времени суток. Я уже довольно часто задаю вопросы здесь и каждый раз мне помогают. Надеюсь и в этот раз мне смогут помочь. Задача заключается в то, что надо создать шаблонный класс бинарного дерева на С++. Просто реализацию бинарного дерева я написал. Вот она:
#include <iostream>
int tabs = 0;
int kol_vo = 0;
struct Branch
{
int Data;
Branch* LeftBranch;
Branch* RightBranch;
};
void Add(int aData, Branch*& aBranch)
{
if (!aBranch)
{
aBranch = new Branch;
aBranch->Data = aData;
aBranch->LeftBranch = 0;
aBranch->RightBranch = 0;
return;
}
else
if (aBranch->Data > aData)
{
Add(aData, aBranch->LeftBranch);
}
else
{
Add(aData, aBranch->RightBranch);
};
}
void print(Branch* aBranch)
{
if (!aBranch) return;
tabs += 5;
print(aBranch->LeftBranch);
for (int i = 0; i < tabs; i++) std::cout « " ";
std::cout « aBranch->Data «std:: endl;
print(aBranch->RightBranch);
tabs-= 5;
return;
}
void pr_obh(Branch*& aBranch)
{
if (NULL == aBranch) return;
std::cout « aBranch->Data « std::endl;
pr_obh(aBranch->LeftBranch);
pr_obh(aBranch->RightBranch);
}
void add_elem(int aData, Branch*& aBranch)
{
if (!aBranch)
{
aBranch = new Branch;
aBranch->Data = aData;
aBranch->LeftBranch = 0;
aBranch->RightBranch = 0;
return;
}
else
{
if (aData < aBranch->Data)
{
add_elem(aData, aBranch->LeftBranch);
}
else if (aData > aBranch->Data)
{
add_elem(aData, aBranch->RightBranch);
}
}
}
void is_Empty(Branch*& aBranch)
{
if (!aBranch)
{
std::cout « "The tree is empty";
}
else
{
std::cout « "The tree is not empty";
}
}
void FreeTree(Branch* aBranch)
{
if (!aBranch) return;
FreeTree(aBranch->LeftBranch);
FreeTree(aBranch->RightBranch);
delete aBranch;
return;
}
Branch* del_elem(Branch*& aBranch, int aData)
{
if (aBranch == NULL)
return aBranch;
if (aData == aBranch->Data)
{
Branch* tmp;
if (aBranch->RightBranch == NULL)
tmp = aBranch->LeftBranch;
else
{
Branch* ptr = aBranch->RightBranch;
if (ptr->LeftBranch == NULL)
{
ptr->LeftBranch = aBranch->LeftBranch;
tmp = ptr;
}
else
{
Branch* pmin = ptr->LeftBranch;
while (pmin->LeftBranch != NULL)
{
ptr = pmin;
pmin = ptr->LeftBranch;
}
ptr->LeftBranch = pmin->RightBranch;
pmin->LeftBranch = aBranch->LeftBranch;
pmin->RightBranch = aBranch->RightBranch;
tmp = pmin;
}
}
delete aBranch;
return tmp;
}
else if (aData < aBranch->Data)
aBranch->LeftBranch = del_elem(aBranch->LeftBranch, aData);
else
aBranch->RightBranch = del_elem(aBranch->RightBranch, aData);
return aBranch;
}
int main()
{
setlocale(LC_ALL, "rus");
Branch* Root = 0;
int vel;
int element;
int k;
std::cout « "Enter the number of elements for the future tree: ";
std::cin » vel;
std::cout «std:: endl;
std::cout « std::endl;
for (int i = 0; i < vel; i++)
{
Add(rand() % 100, Root);
}
std::cout « std::endl;
std::cout « "Binary tree: " « std::endl;
print(Root);
std::cout « std::endl;
std::cout « "Direct traversal of the binary tree: " « std::endl;
pr_obh(Root);
std::cout « std::endl;
std::string instruction;
std::cout « "add - 01, delete - 02, exit - 00" « std::endl;
std::cin » instruction;
while (instruction != "00")
{
if(instruction == "01")
{
std::cout « "Adding a new element to the binary tree:" « std::endl;
std::cout « "Enter a new element: ";
std::cin » instruction;
std::cin.ignore();
if(instruction == "01" || instruction == "02" || instruction == "00")
{
continue;
}
else
{
element = atoi(instruction.c_str());
instruction = "01";
}
add_elem(element, Root);
std::cout « "Binary tree: " « std::endl;
print(Root);
std::cout « std::endl;
}
else if(instruction == "02")
{
std::cout « "Removing an element from a binary tree:" « std::endl;
std::cout « "Enter the element to delete: ";
std::cin » instruction;
std::cin.ignore();
if(instruction == "01" || instruction == "02" || instruction == "00")
{
continue;
}
else
{
element = atoi(instruction.c_str());
instruction = "02";
}
del_elem(Root, element);
std::cout « "Binary tree: " « std::endl;
print(Root);
std::cout « std::endl;
}
}
FreeTree(Root);
return 0;
}
Очень надеюсь, что мне смогут помочь или хотя бы подробно объяснят, как это сделать. Даю все баллы!
Ответы
Для создания шаблонного класса бинарного дерева на C++ вам нужно сначала определить шаблонный класс узла для дерева, который будет иметь поля для хранения ключа (data) и указателей на левое и правое поддеревья. Затем вы можете определить шаблонный класс для самого дерева, который будет иметь корневой элемент и функции для добавления и удаления узлов, обхода дерева и т.д.
Вот пример шаблонного класса узла:
template <typename T>
class Node {
public:
T data;
Node<T>* left;
Node<T>* right;
Node<T>(T data) : data(data), left(NULL), right(NULL) {}
};
А вот пример класса бинарного дерева, использующего узел Node:
template <typename T>
class BinarySearchTree {
private:
Node<T>* root;
public:
BinarySearchTree() : root(NULL) {}
void insert(T data) {
Node<T>* newNode = new Node<T>(data);
if (root == NULL) {
root = newNode;
}
else {
Node<T>* currentNode = root;
while (true) {
if (data < currentNode->data) {
if (currentNode->left == NULL) {
currentNode->left = newNode;
break;
}
else {
currentNode = currentNode->left;
}
}
else {
if (currentNode->right == NULL) {
currentNode->right = newNode;
break;
}
else {
currentNode = currentNode->right;
}
}
}
}
}
void remove(T data) {
root = removeNode(root, data);
}
Node<T>* removeNode(Node<T>* currentNode, T data) {
if (currentNode == NULL) {
return NULL;
}
if (data == currentNode->data) {
if (currentNode->left == NULL && currentNode->right == NULL) {
delete currentNode;
return NULL;
}
if (currentNode->left == NULL) {
Node<T>* tempNode = currentNode->right;
delete currentNode;
return tempNode;
}
if (currentNode->right == NULL) {
Node<T>* tempNode = currentNode->left;
delete currentNode;
return tempNode;
}
Node<T>* tempNode = getMinNode(currentNode->right);
currentNode->data = tempNode->data;
currentNode->right = removeNode(currentNode->right, tempNode->data);
}
else if (data < currentNode->data) {
currentNode->left = removeNode(currentNode->left, data);
}
else {
currentNode->right = removeNode(currentNode->right, data);
}
return currentNode;
}
Node<T>* getMinNode(Node<T>* currentNode) {
while (currentNode->left != NULL) {
currentNode = currentNode->left;
}
return currentNode;
}
void printInOrder(Node<T>* currentNode) {
if (currentNode != NULL) {
printInOrder(currentNode->left);
std::cout << currentNode->data << " ";
printInOrder(currentNode->right);
}
}
void printInOrder() {
printInOrder(root);
}
};
В этом примере класс BinarySearchTree имеет функции для добавления, удаления и обхода дерева. Они используют узлы типа Node<T>. Аргумент шаблона T можно использовать для любого типа данных, например, int, char или любого пользовательского типа.