Построение BSTree для класса структур данных и алгоритмов. ⇐ C++

[Anonymous]

Моя программа должна пройти несколько тестов в определенных рамках, предоставленных моим профессором. Включая BSTree.cpp, BSTree.h, Main.cpp, Node.h, Node.cpp.
Необходимые открытые функции-члены
void Insert(const string &): Insert элемент в двоичное дерево поиска. Обязательно сохраните свойства двоичного дерева поиска. Когда элемент впервые вставляется в дерево, счетчик должен быть установлен на 1. При добавлении повторяющейся строки (с учетом регистра) вместо добавления еще одного узла переменная счетчика должна просто увеличиваться.
bool search(const string) &) const: поиск строки в дереве двоичного поиска. Он должен возвращать true, если строка находится в дереве, и false в противном случае.
string наибольший( ) const: Найти и вернуть наибольшее значение в дереве. Возвращает пустую строку, если дерево пусто.
string small() const: находит и возвращает наименьшее значение в дереве. Возвращает пустую строку, если дерево пусто.
int height(const string &) const: Вычисляет и возвращает высоту определенной строки в дереве. Высота листового узла равна 0 (подсчитайте количество ребер на самом длинном пути). Верните -1, если строка не существует.
void Remove(const string &): Удалить указанную строку из дерева. Обязательно сохраните все свойства двоичного дерева поиска. При удалении узла со счетчиком больше 1 просто уменьшите счетчик, в противном случае, если счетчик просто равен 1, удалите узел. Вы ДОЛЖНЫ следовать алгоритму удаления, показанному на слайдах и обсуждаемому в классе, иначе ваша программа не пройдет тестовые функции. При удалении листового узла просто удалите лист. В противном случае, если у удаляемого узла есть левый дочерний элемент, замените удаляемый узел на наибольшее строковое значение, меньшее, чем текущая удаляемая строка (т. е. найдите наибольшее значение в левом поддереве удаляемого узла). Если у узла нет левого дочернего элемента, замените удаляемый узел наименьшим значением, большим, чем текущая удаляемая строка (т. е. найдите наименьшее значение в правом поддереве удаляемого узла).
Печать дерева:
void preOrder(): просмотрите и распечатайте дерево в предварительной записи, следуя рекомендациям по печати, указанным выше.
void inOrder(): просмотрите и распечатайте дерево в предварительной записи, следующей th< /p>

инструкции по печати, указанные выше.
void postOrder(): просмотр и печать дерева в записи обратного порядка, следуя рекомендациям по печати, указанным выше.

инструкции по печати, указанные выше. p>
Примечание о рекурсии
Некоторые из вышеперечисленных функций, используемых для взаимодействия с основным тестовым файлом, не подходят для рекурсивной методологии. Однако вы должны писать функции inOrder, preOrder, postOrder, search и Remove рекурсивно (вы потеряете очки, если не сделаете это рекурсивно). Это может потребовать от вас перегрузки одной или нескольких функций. Например, preOrder вызывается из main, но ему не передается ни один параметр (у вас не должно быть возможности передать корень из main, поскольку это должна быть частная переменная вашего класса дерева). Однако вы можете перегрузить функцию preOrder, чтобы она работала рекурсивно. Например, ваша функция preOrder должна выглядеть так:
и вы напишете код preOrder внутри рекурсивной функции, которая принимает узел в качестве параметра. Возможно, вам придется сделать что-то подобное для функций inOrder, postOrder, search и/или Remove, чтобы можно было писать эти функции рекурсивно. Должны ли эти рекурсивные вспомогательные функции быть общедоступными или частными?
Что бы я ни пробовал, я не могу заставить программу пройти тест, чтобы вернуть этот тест: Test5:
1
папа
1
Квебек
1
альфа
1
отель
1
Индия
1
Джульетта
1
кило
1
браво
1
альфа
1
Лима
1
Чарли
1
альфа
1
Индия
1
дельта
1
эпсилон
1
Майк
1
ноябрь
1
Оскар
1
фокстрот
1
гольф
2
альфа
2
браво
2
Оскар
2
эпсилон
2
лима
2
альфа
2
отель
2
альфа
3
8
МОЙ код
#include "BSTree.h"
#include

using namespace std;

void BSTree::insert(const string& key) {
// Edge case: The tree is empty
if (root == nullptr) {
root = new Node(key);
return;
}
// Traverse the tree to find the insertion point
for (Node* curr = root; curr != nullptr;) {
if (key == curr->key) {
curr->count++; // Edge case: If key already exists, increment count
return;
} else if (key < curr->key) {
if (curr->left == nullptr) { // go left if key is smaller
curr->left = new Node(key); // Insert new node on the left
return;
}
curr = curr->left;
} else { // key > curr->key
if (curr->right == nullptr) { // go right if key is larger
curr->right = new Node(key); // Insert new node on the right
return;
}
curr = curr->right;
}
}
}

// Traverse the tree to search for the key
bool BSTree::search(const string& key) const {
for (Node* curr = root; curr != nullptr;) {
if (key == curr->key) return true; // Key found
curr = (key < curr->key) ? curr->left : curr->right;
}
return false; // Key not found
}

string BSTree::largest() const {
if (!root) return ""; // Edge case: Tree is empty
Node* curr = root;
while (curr->right) curr = curr->right; // Find the rightmost node, largest key
return curr->key;
}

string BSTree::smallest() const {
if (!root) return ""; // Edge case: Tree is empty
Node* curr = root;
while (curr->left) curr = curr->left; // Find the leftmost node, smallest key
return curr->key;
}

// Traverse the tree to find the node with the specified key
int BSTree::height(const string& key) const {
for (Node* curr = root; curr != nullptr;) {
if (key == curr->key) return height_of(curr); // Key found, return height
curr = (key < curr->key) ? curr->left : curr->right; // Continue search
}
return -1; // Key not found
}

void BSTree::remove(const string& key) {
remove(nullptr, root, key);
}

void BSTree::preOrder() const {
preOrder(root);
cout node->key) {
remove(node, node->right, key); // go to the right child
} else {
// Node to delete is found.
if (node->count > 1) {
node->count--; // Duplicate keys, decrement count
} else {
Node* replacement = node->left ? node->left : node->right;
// Case 1: Node has one or no children.
if (!node->left || !node->right) {
if (!parent) {
root = replacement; // Node is root, replace root
} else if (parent->left == node) {
parent->left = replacement; // Node is left child
} else {
parent->right = replacement; // Node is right child
}
delete node;
} else {
// Case 2: Node has two children.
// Find the maximum node in the left subtree
Node* maxLeft = node->left;
Node* maxLeftParent = node;
while (maxLeft->right) {
maxLeftParent = maxLeft;
maxLeft = maxLeft->right;
}
// replace node's keys and count with maxleft's values
node->key = maxLeft->key;
node->count = maxLeft->count;
// Recursively remove maxLeft node, which is now a duplicate.
if (maxLeftParent->left == maxLeft) {
maxLeftParent->left = maxLeft->left;
} else {
maxLeftParent->right = maxLeft->left;
}
delete maxLeft; // Delete maxLeft to free memory
}
}
}
}

int BSTree::height_of(Node* tree) const {
if (!tree) return -1; // Base case: null tree has height -1
return 1 + max(height_of(tree->left), height_of(tree->right)); // Return max height of children + 1
}

void BSTree::preOrder(Node* tree) const {
if (!tree) return; // Base case: null node
cout key right); // Traverse right subtree
}

void BSTree::postOrder(Node* tree) const {
if (!tree) return; // Base case: null node
postOrder(tree->left); // Traverse left subtree
postOrder(tree->right); // Traverse right subtree
cout key

Подробнее здесь: https://stackoverflow.com/questions/791 ... thms-class