Мобильная версияНеобходимые открытые функции-члены:
- void insert(const string &): вставьте элемент в дерево двоичного поиска. Обязательно сохраните свойства двоичного дерева поиска. Когда элемент впервые вставляется в дерево, счетчик должен быть установлен на 1. При добавлении повторяющейся строки (с учетом регистра) вместо добавления еще одного узла следует просто увеличить переменную счетчика.
< /li>
bool search(const string &) const: поиск строки в дереве двоичного поиска. Он должен возвращать true, если строка находится в дереве, и false в противном случае. - string largest( ) const: найти и вернуть наибольшее значение в дереве. Возвращает пустую строку, если дерево пусто.
- string smallest( ) const: найти и вернуть наименьшее значение в дереве. Возвращает пустую строку, если дерево пусто.
- int height(const string &) const: вычислить и вернуть высоту определенной строки в дереве. Высота листового узла равна 0 (подсчитайте количество ребер на самом длинном пути). Верните -1, если строка не существует.
- void remove(const string &): удалить указанную строку из дерева. Обязательно сохраните все свойства двоичного дерева поиска. При удалении узла со счетчиком больше 1 просто уменьшите счетчик, в противном случае, если счетчик просто равен 1, удалите узел. Вы ДОЛЖНЫ следовать алгоритму удаления, показанному на слайдах и обсуждаемому в классе, иначе ваша программа не пройдет тестовые функции. При удалении листового узла просто удалите лист. В противном случае, если у удаляемого узла есть левый дочерний элемент, замените удаляемый узел на наибольшее строковое значение, меньшее, чем текущая удаляемая строка (т. е. найдите наибольшее значение в левом поддереве удаляемого узла). Если у узла нет левого дочернего элемента, замените удаляемый узел наименьшим значением, большим, чем текущая удаляемая строка (т. е. найдите наименьшее значение в правом поддереве удаляемого узла).
< /li>
- void preOrder( ): просмотрите и распечатайте дерево в предварительном порядке, следуя приведенным выше рекомендациям по печати.
- void inOrder( ): Пройдитесь по дереву и распечатайте его в порядке записи, следуя приведенным выше рекомендациям по печати.
- void postOrder( ): просмотрите и распечатайте дерево в обратной записи, следуя приведенным выше рекомендациям по печати.
Некоторые из вышеперечисленных функций, используемых для взаимодействия с основным тестовым файлом, не подходят для рекурсивной методологии. Однако функции inOrder(), preOrder(), postOrder(), search() и Remove() необходимо писать рекурсивно (вы потеряете очки, если не сделаете это рекурсивно). Это может потребовать от вас перегрузки одной или нескольких функций. Например, preOrder() вызывается из main(), но ему не передается ни один параметр (у вас не должно быть возможности передать корень из main, поскольку это должна быть частная переменная вашего класса дерева). . Однако вы можете перегрузить функцию preOrder(), чтобы она работала рекурсивно. Например, ваша функция preOrder() должна выглядеть так:
...
и вы напишете код preOrder() внутри рекурсивная функция, которая принимает узел в качестве параметра. Возможно, вам придется сделать что-то подобное для функций inOrder(), postOrder(), search() и/или Remove(), чтобы вы могли написать эти функционирует рекурсивно. Должны ли эти рекурсивные вспомогательные функции быть общедоступными или частными?
Что бы я ни пробовал, я не могу заставить программу пройти тест, чтобы вернуть этот тест. :
Test5:
1
papa
1
quebec
1
alpha
1
hotel
1
india
1
juliet
1
kilo
1
bravo
1
alpha
1
lima
1
charlie
1
alpha
1
india
1
delta
1
epsilon
1
mike
1
nov
1
oscar
1
foxtrot
1
golf
2
alpha
2
bravo
2
oscar
2
epsilon
2
lima
2
alpha
2
hotel
2
alpha
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
