Программа вставки/удаления BST не проходит некоторые тесты. Нужна помощь в исправлении выходных данных тестового примера

Программа вставки/удаления BST не проходит некоторые тесты. Нужна помощь в исправлении выходных данных тестового примера ⇐ C++

1 сообщение • Страница 1 из 1

Anonymous

Программа вставки/удаления BST не проходит некоторые тесты. Нужна помощь в исправлении выходных данных тестового примера

Цитата

Сообщение Anonymous » 09 ноя 2024, 15:55

Проблема:
Я реализую двоичное дерево поиска (BST) на C++ для задания курса по структурам данных. Программа должна обрабатывать вставку, удаление и обход дерева по порядку. Однако он не проходит некоторые простые тестовые случаи, особенно при удалении последнего узла.
Основные требования:
Код должен быть написан на C++.
Используйте только стандартные библиотеки для ввода/вывода, выделения/освобождения памяти и удаления узлов.
Программа не должна аварийно завершать работу (нет ошибок сегментации, двойного освобождения и т. д.).
/>Кучная память должна правильно управляться без утечки.
После каждой вставки и удаления выведите порядок обхода дерева в формате:

Выводит сообщение об ошибке, если:
Ключ уже существует во время вставки: i {key}: ключ уже существует
Ключ не существует во время удаления: d {key}: ключ не существует
Проблема:
Вставка работает нормально во всех случаях.
Удалить работает, но когда дерево становится пустым после удаления последнего узла, программа не печатает новую строку ( что требуется для постановки задачи).
В чем мне нужна помощь:
Как исправить вывод при удалении последнего узла, чтобы обеспечить правильную печать новой строки.
Проблема с выводом теста:
Для следующий ввод:

Код: Выделить всё

Правильный вывод должен быть следующим:

Код: Выделить всё

< 25 >
< 25 < 500 >>
i 25: The key already exists
< 25  500 >>
< 25 > 500 >>
 25 > 500 >>
 25 >> 500 >>
 25 >> 500 >>
 25 >> 500 >>
 25 >> 500 >>
 25 >> 500 >>
 25  403 >>> 500 >>
 25  49 > 403 >>> 500 >>
> 25  49 > 403 >>> 500 >>
> 25  49 > 403 < 441 >>>> 500 >>
> 25  49 >> 403 < 441 >>>> 500 >>
> 25  49 >> 403 < 441 >>>> 500 >>
> 25  49  105 < 305 < 390 >>> 403 < 441 >>>> 500 >>
> 25  49  105 < 305 < 390 >>> 403 < 441 >>>> 500 >>
> 25  49 > 105 < 305 < 390 >>> 403 < 441 >>>> 500 >>
> 25  49 > 105 < 305 < 390 >>> 403 < 441 >>>> 500 < 999 >>
> 29  49 > 105 < 305 < 390 >>> 403 < 441 >>>> 500 < 999 >>
> 29  49 > 105 < 305 < 390 >>> 403 < 441 >>>> 500 < 999 >>
> 29  49 > 105 < 305 < 390 >>> 403 >>> 441 < 999 >>>
d 25: The key does not exist
> 29  49 > 105 < 305 < 390 >>> 403 >> 441 <  999 >>>
> 29  50 > 105 < 305 < 390 >>> 403 >> 441 < 999 >>>
> 29  50 > 105 < 305 < 390 >>> 403 >> 441 < 999 >>>
> 29  50 >> 105 < 305 < 390 >>>> 441 < 999 >>>
> 39 > 105 < 305 < 390 >>>> 441 < 999 >>>
> 39  100 < 305 < 390 >>>> 441 < 999 >>>
> 44  100 < 305 < 390 >>>> 441 < 999 >>>
> 44 >>> 441 < 999 >>>
> 44 >> 441 < 999 >>>
> 50 > 441 < 999 >>>
 50 > 441 < 999 >>>
 50  390 < 999 >>>
 50  100 < 999 >>>
< 50  100 < 999 >>
< 50 < 100 < 999 >>
< 100 < 999 >>
< 999 >
// This line has no in-order traversal output of the tree since the last node was deleted, and only the opening occurred.

В моем случае оно было напечатано без нижней строки.

Код: Выделить всё

< 25 >
< 25 < 500 >>
i 25: The key already exists
< 25  500 >>
< 25 > 500 >>
 25 > 500 >>
 25 >> 500 >>
 25 >> 500 >>
 25 >> 500 >>
 25 >> 500 >>
 25 >> 500 >>
 25  403 >>> 500 >>
 25  49 > 403 >>> 500 >>
> 25  49 > 403 >>> 500 >>
> 25  49 > 403 < 441 >>>> 500 >>
> 25  49 >> 403 < 441 >>>> 500 >>
> 25  49 >> 403 < 441 >>>> 500 >>
> 25  49  105 < 305 < 390 >>> 403 < 441 >>>> 500 >>
> 25  49  105 < 305 < 390 >>> 403 < 441 >>>> 500 >>
> 25  49 > 105 < 305 < 390 >>> 403 < 441 >>>> 500 >>
> 25  49 > 105 < 305 < 390 >>> 403 < 441 >>>> 500 < 999 >>>
> 29  49 > 105 < 305 < 390 >>> 403 < 441 >>>> 500 <  999 >>>
> 29  49 > 105 < 305 < 390 >>> 403 >>> 441 < 999 >>>
d 25: The key does not exist
> 29  49 > 105 < 305 < 390 >>> 403 >> 441 < 999 >>>
> 29  50 > 105 < 305 < 390 >>> 403 >> 441 < 999 >>>
> 29  50 > 105 < 305 < 390 >>> 403 >> 441 < 999 >>>
> 29  50 >> 105 < 305 < 390 >>>> 441 < 999 >>>
> 39 > 105 < 305 < 390 >>>> 441 < 999 >>>
> 39  100 < 305 < 390 >>>> 441 < 999 >>>
> 44  100 < 305 < 390 >>>> 441 < 999 >>>
> 44 >>> 441 < 999 >>>
> 44 >> 441 < 999 >>>
> 50 > 441 < 999 >>>
 50 > 441 < 999 >>>
 50  390 < 999 >>>
 50  100 < 999 >>>
< 50  100 < 999 >>>
< 50 < 100 < 999 >>>
< 100 < 999 >>
< 999 >

Вопросы:
Почему моя программа не справляется с этими конкретными простыми тестовыми примерами?
Что я могу изменить в своем коде, чтобы гарантировать, что программа выводит правильный формат, особенно после окончательного удаления?
Это мой исходный код. main.cpp

Код: Выделить всё

#include 
#include 

using namespace std;

// =============================================================
//                        # Requirements #
// 1. Implement a class or structure representing each node in the BST.
// 2. Implement the insertion algorithm for the BST.
// 3. Implement the insertion algorithm for the BST (duplicated requirement, possibly for deletion or other).
// 4. Implement an inorder traversal algorithm to print the tree.
// 5. Implement the deletion algorithm for the BST.
// 6. Implement the clear algorithm for the BST.
// =============================================================

// The class or structure should be named "Node".
// The node should contain the members: key, left, right, height, and size.  (No additions, deletions, or modifications allowed)

struct Node {

int key;          // key: the key value of the node

Node* left;       // left: the address of the left child node

Node* right;      // right: the address of the right child node

int height;       // height: the height of the node
int size;         // size: the size of the subtree

Node(int k) : key(k), left(nullptr), right(nullptr), height(1), size(1) {}
};

// Implement the function getNodeBST() as explained in the lecture slides
// The function should follow the prototype (template) as given -> insertBST(T, key)
Node* getNodeBST(int key) {
// Allocate new node
return new Node(key);
}

// Function to return the height of a node
int height(Node* node) {
// If node is nullptr, return 0; otherwise, return the height
return node ? node->height : 0;
}

// Function to return the size of a node
int size(Node* node) {
// If node is nullptr, return 0; otherwise, return the size
return node ? node->size : 0;
}

// Function to update the height and size of a node
void updateNode(Node* node) {
if (node) {
// Do not use std::max!!! Calculate the maximum manually using comparison!
int leftHeight = height(node->left);
int rightHeight = height(node->right);

node->height = 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);  // Update height
node->size = 1 + size(node->left) + size(node->right);                     // Update size
}
}

// The following functions are explained in the lecture slides and should be used:
// height(T), size(T), minNode(T), maxNode(T)
// However, if the logic works correctly without making them separate functions, you may integrate them directly and comment accordingly.

// Insert the new key into the BST, and print the tree using inorder traversal
bool insertBST(Node*& T, int newKey) {
Node* p = T;
Node* q = nullptr;
stack stac;                                                    // Stack to track parent nodes

// Search for the insertion position and store parent nodes in the stack
while (p != nullptr) {
if (newKey == p->key) {
cerr key) q->left = newNode;                          // Insert as the left child
else q->right = newNode;                                              // Insert as the right child

// Update the height and size of parent nodes
while (!stac.empty()) {
q = stac.top();
stac.pop();
q->height = 1 + (height(q->left) > height(q->right) ? height(q->left) : height(q->right));
q->size = 1 + size(q->left) + size(q->right);
}
return false;                                                         // Insertion successful
}

// Inorder traversal function based on the prototype
void inorder(Node* T) {
if (T == nullptr) {
return;                                                           // If the tree is empty, return without printing
}
cout left);                                                     // Traverse the left subtree
cout key) {
q = p;
stac.push(q);                                                     // Store parent node in stack
if (deleteKey < p->key) p = p->left;                              // Search left subtree
else p = p->right;                                                // Search right subtree
}

if (p == nullptr) {
cerr right) ||
(height(p->left) == height(p->right) && size(p->left) < size(p->right))) {
p = p->right;
while (p->left != nullptr) {
stac.push(p);
p = p->left;
}
} else {
p = p->left;
while (p->right != nullptr) {
stac.push(p);
p = p->right;
}
}

tempNode->key = p->key;
q = stac.top();
}

// Case when the node has no children
if (p->left == nullptr && p->right == nullptr) {
if (q == nullptr) T = nullptr;                                    // If the node is the root
else if (q->left == p) q->left = nullptr;                         // If the node is the left child of parent
else q->right = nullptr;                                          // If the node is the right child of parent
}

// Case when the node has one child
else {
Node* child = (p->left != nullptr) ? p->left : p->right;          // Choose the child node
if (q == nullptr) T = child;                                      // If the node is the root
else if (q->left == p) q->left = child;                           // If the node is the left child of parent
else q->right = child;                                            // If the node is the right child of parent
}

delete p;                                                             // Delete the node and free memory

// Update the height and size of parent nodes
while (!stac.empty()) {
q = stac.top();
stac.pop();
q->height = 1 + (height(q->left) > height(q->right) ? height(q->left) : height(q->right));
q->size = 1 + size(q->left) + size(q->right);
}

return T;                                                             // Return the updated tree
}

// Clear algorithm to free memory of all nodes in the BST
void clear(Node* T) {
if (T == nullptr) return;                                             // Return if the tree is empty
clear(T->left);                                                       // Clear the left subtree
clear(T->right);                                                      // Clear the right subtree
delete T;                                                             // Delete the current node
}

// main function!
int main() {
Node* root = nullptr;
char op;
int key;

while (cin >> op >> key) {
if (op == 'i') {                                                  // Handle insert command
if (!insertBST(root, key)) {
if (root != nullptr) {                                    // Add newline only if the tree is not empty
inorder(root);
cout  date
Sat Nov  9 12:06:05 UTC 2024

$> clang --version
Apple clang version 16.0.0 (clang-1600.0.26.3)
Target: arm64-apple-darwin23.6.0
Thread model: posix
InstalledDir: /Library/Developer/CommandLineTools/usr/bin

$> clang++ --version
Apple clang version 16.0.0 (clang-1600.0.26.3)
Target: arm64-apple-darwin23.6.0
Thread model: posix
InstalledDir: /Library/Developer/CommandLineTools/usr/bin

= Compiling ====================================================================
$> clang++ -Wall -Wextra -Werror -g3 /Users/runner/work/test/test/submit/main.cpp -o user_exe

= TEST CASE - simple00 =======================================================
$> ./user_exe < simple00
$> diff -u user_output_simple00 test_output_simple00
--- /Users/runner/work/test/test/output/__bstree/user_output_simple00   2024-11-09 12:06:17$
+++ /Users/runner/work/test/test/output/__bstree/test_output_simple00   2024-11-09 12:06:17$
@@ -39,3 +39,4 @@$
< 50 < 100 < 999 >>>$
< 100 < 999 >>$
< 999 >$
+$

Diff KO :(

= TEST CASE - simple01 =======================================================
$> ./user_exe < simple01
$> diff -u user_output_simple01 test_output_simple01
--- /Users/runner/work/test/test/output/__bstree/user_output_simple01   2024-11-09 12:06:18$
+++ /Users/runner/work/test/test/output/__bstree/test_output_simple01   2024-11-09 12:06:18$
@@ -17,3 +17,4 @@$
< 8 < 9 < 10 >>>$
< 9 < 10 >>$
< 10 >$
+$

Diff KO :(

= TEST CASE - simple02 =======================================================
$> ./user_exe < simple02
$> diff -u user_output_simple02 test_output_simple02
--- /Users/runner/work/test/test/output/__bstree/user_output_simple02   2024-11-09 12:06:19$
+++ /Users/runner/work/test/test/output/__bstree/test_output_simple02   2024-11-09 12:06:19$
@@ -17,3 +17,4 @@$
 10 >$
 10 >$
< 10 >$
+$

Diff KO :(

= TEST CASE - random00 =======================================================
$> ./user_exe < random00
$> diff -u user_output_random00 test_output_random00

Diff OK :D

= TEST CASE - random01 =======================================================
$> ./user_exe < random01
$> diff -u user_output_random01 test_output_random01

Diff OK :D

= TEST CASE - random02 =======================================================
$> ./user_exe < random02
$> diff -u user_output_random02 test_output_random02

Diff OK :D

= TEST CASE - random03 =======================================================
$> ./user_exe < random03
$> diff -u user_output_random03 test_output_random03

Diff OK :D

= TEST CASE - random04 =======================================================
$> ./user_exe < random04
$>  diff -u user_output_random04 test_output_random04

Diff OK :D

Что я пробовал:
Я реализовал функции вставки, удаления и упорядочения в соответствии с требованиями назначения.
Я использовал некоторое время цикл для обработки входных команд и вставки или удаления узлов по запросу.
После каждой операции я печатал порядок обхода дерева, как указано.
Что я ожидал:
После каждой операции вставки и удаления я ожидал, что программа чтобы правильно напечатать обход дерева по порядку.
В частности, при удалении последнего узла и создании пустого дерева я ожидал, что программа напечатает новую строку без каких-либо узлов дерева.
Что на самом деле произошло:
Программа работала нормально для большинства операций, корректно печатая дерево после вставок и удалений.
Однако при удалении последнего узла программа не печатала новую строку, как требовалось, а вместо этого уходила вывод неполный.

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

1731156921

Anonymous

[b]Проблема:[/b]
Я реализую двоичное дерево поиска (BST) на C++ для задания курса по структурам данных. Программа должна обрабатывать вставку, удаление и обход дерева по порядку. Однако он не проходит некоторые простые тестовые случаи, особенно при удалении последнего узла.
[b]Основные требования:[/b]
Код должен быть написан на C++.
Используйте только стандартные библиотеки для ввода/вывода, выделения/освобождения памяти и удаления узлов.
Программа не должна аварийно завершать работу (нет ошибок сегментации, двойного освобождения и т.  д.).
/>Кучная память должна правильно управляться без утечки.
После каждой вставки и удаления выведите порядок обхода дерева в формате:

Выводит сообщение об ошибке, если:
Ключ уже существует во время вставки: i {key}: ключ уже существует
Ключ не существует во время удаления: d {key}: ключ не существует
Проблема:
Вставка работает нормально во всех случаях.
Удалить работает, но когда дерево становится пустым после удаления последнего узла, программа не печатает новую строку ( что требуется для постановки задачи).
В чем мне нужна помощь:
Как исправить вывод при удалении последнего узла, чтобы обеспечить правильную печать новой строки.
Проблема с выводом теста:
Для следующий ввод:
[code]i 25
i 500
i 25
i 33
i 49
i 17
i 403
i 29
i 105
i 39
i 66
i 305
i 44
i 19
i 441
i 390
i 12
i 81
i 50
i 100
i 999
d 25
d 500
d 25
d 33
d 49
d 17
d 403
d 29
d 105
d 39
d 66
d 305
d 44
d 19
d 441
d 390
d 12
d 81
d 50
d 100
d 999
[/code]
Правильный вывод должен быть следующим:
[code]< 25 >
< 25 < 500 >>
i 25: The key already exists
< 25  500 >>
< 25 > 500 >>
 25 > 500 >>
 25 >> 500 >>
 25 >> 500 >>
 25 >> 500 >>
 25 >> 500 >>
 25 >> 500 >>
 25  403 >>> 500 >>
 25  49 > 403 >>> 500 >>
> 25  49 > 403 >>> 500 >>
> 25  49 > 403 < 441 >>>> 500 >>
> 25  49 >> 403 < 441 >>>> 500 >>
> 25  49 >> 403 < 441 >>>> 500 >>
> 25  49  105 < 305 < 390 >>> 403 < 441 >>>> 500 >>
> 25  49  105 < 305 < 390 >>> 403 < 441 >>>> 500 >>
> 25  49 > 105 < 305 < 390 >>> 403 < 441 >>>> 500 >>
> 25  49 > 105 < 305 < 390 >>> 403 < 441 >>>> 500 < 999 >>
> 29  49 > 105 < 305 < 390 >>> 403 < 441 >>>> 500 < 999 >>
> 29  49 > 105 < 305 < 390 >>> 403 < 441 >>>> 500 < 999 >>
> 29  49 > 105 < 305 < 390 >>> 403 >>> 441 < 999 >>>
d 25: The key does not exist
> 29  49 > 105 < 305 < 390 >>> 403 >> 441 <  999 >>>
> 29  50 > 105 < 305 < 390 >>> 403 >> 441 < 999 >>>
> 29  50 > 105 < 305 < 390 >>> 403 >> 441 < 999 >>>
> 29  50 >> 105 < 305 < 390 >>>> 441 < 999 >>>
> 39 > 105 < 305 < 390 >>>> 441 < 999 >>>
> 39  100 < 305 < 390 >>>> 441 < 999 >>>
> 44  100 < 305 < 390 >>>> 441 < 999 >>>
> 44 >>> 441 < 999 >>>
> 44 >> 441 < 999 >>>
> 50 > 441 < 999 >>>
 50 > 441 < 999 >>>
 50  390 < 999 >>>
 50  100 < 999 >>>
< 50  100 < 999 >>
< 50 < 100 < 999 >>
< 100 < 999 >>
< 999 >
// This line has no in-order traversal output of the tree since the last node was deleted, and only the opening occurred.
[/code]
В моем случае оно было напечатано без нижней строки.
[code]< 25 >
< 25 < 500 >>
i 25: The key already exists
< 25  500 >>
< 25 > 500 >>
 25 > 500 >>
 25 >> 500 >>
 25 >> 500 >>
 25 >> 500 >>
 25 >> 500 >>
 25 >> 500 >>
 25  403 >>> 500 >>
 25  49 > 403 >>> 500 >>
> 25  49 > 403 >>> 500 >>
> 25  49 > 403 < 441 >>>> 500 >>
> 25  49 >> 403 < 441 >>>> 500 >>
> 25  49 >> 403 < 441 >>>> 500 >>
> 25  49  105 < 305 < 390 >>> 403 < 441 >>>> 500 >>
> 25  49  105 < 305 < 390 >>> 403 < 441 >>>> 500 >>
> 25  49 > 105 < 305 < 390 >>> 403 < 441 >>>> 500 >>
> 25  49 > 105 < 305 < 390 >>> 403 < 441 >>>> 500 < 999 >>>
> 29  49 > 105 < 305 < 390 >>> 403 < 441 >>>> 500 <  999 >>>
> 29  49 > 105 < 305 < 390 >>> 403 >>> 441 < 999 >>>
d 25: The key does not exist
> 29  49 > 105 < 305 < 390 >>> 403 >> 441 < 999 >>>
> 29  50 > 105 < 305 < 390 >>> 403 >> 441 < 999 >>>
> 29  50 > 105 < 305 < 390 >>> 403 >> 441 < 999 >>>
> 29  50 >> 105 < 305 < 390 >>>> 441 < 999 >>>
> 39 > 105 < 305 < 390 >>>> 441 < 999 >>>
> 39  100 < 305 < 390 >>>> 441 < 999 >>>
> 44  100 < 305 < 390 >>>> 441 < 999 >>>
> 44 >>> 441 < 999 >>>
> 44 >> 441 < 999 >>>
> 50 > 441 < 999 >>>
 50 > 441 < 999 >>>
 50  390 < 999 >>>
 50  100 < 999 >>>
< 50  100 < 999 >>>
< 50 < 100 < 999 >>>
< 100 < 999 >>
< 999 >
[/code]
Вопросы:
Почему моя программа не справляется с этими конкретными простыми тестовыми примерами?
Что я могу изменить в своем коде, чтобы гарантировать, что программа выводит правильный формат, особенно после окончательного удаления?
Это мой исходный код. main.cpp
[code]#include 
#include 

using namespace std;

// =============================================================
//                        # Requirements #
// 1. Implement a class or structure representing each node in the BST.
// 2. Implement the insertion algorithm for the BST.
// 3. Implement the insertion algorithm for the BST (duplicated requirement, possibly for deletion or other).
// 4. Implement an inorder traversal algorithm to print the tree.
// 5. Implement the deletion algorithm for the BST.
// 6. Implement the clear algorithm for the BST.
// =============================================================

// The class or structure should be named "Node".
// The node should contain the members: key, left, right, height, and size.  (No additions, deletions, or modifications allowed)

struct Node {

int key;          // key: the key value of the node

Node* left;       // left: the address of the left child node

Node* right;      // right: the address of the right child node

int height;       // height: the height of the node
int size;         // size: the size of the subtree

Node(int k) : key(k), left(nullptr), right(nullptr), height(1), size(1) {}
};

// Implement the function getNodeBST() as explained in the lecture slides
// The function should follow the prototype (template) as given -> insertBST(T, key)
Node* getNodeBST(int key) {
// Allocate new node
return new Node(key);
}

// Function to return the height of a node
int height(Node* node) {
// If node is nullptr, return 0; otherwise, return the height
return node ? node->height : 0;
}

// Function to return the size of a node
int size(Node* node) {
// If node is nullptr, return 0; otherwise, return the size
return node ? node->size : 0;
}

// Function to update the height and size of a node
void updateNode(Node* node) {
if (node) {
// Do not use std::max!!! Calculate the maximum manually using comparison!
int leftHeight = height(node->left);
int rightHeight = height(node->right);

node->height = 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);  // Update height
node->size = 1 + size(node->left) + size(node->right);                     // Update size
}
}

// The following functions are explained in the lecture slides and should be used:
// height(T), size(T), minNode(T), maxNode(T)
// However, if the logic works correctly without making them separate functions, you may integrate them directly and comment accordingly.

// Insert the new key into the BST, and print the tree using inorder traversal
bool insertBST(Node*& T, int newKey) {
Node* p = T;
Node* q = nullptr;
stack stac;                                                    // Stack to track parent nodes

// Search for the insertion position and store parent nodes in the stack
while (p != nullptr) {
if (newKey == p->key) {
cerr key) q->left = newNode;                          // Insert as the left child
else q->right = newNode;                                              // Insert as the right child

// Update the height and size of parent nodes
while (!stac.empty()) {
q = stac.top();
stac.pop();
q->height = 1 + (height(q->left) > height(q->right) ? height(q->left) : height(q->right));
q->size = 1 + size(q->left) + size(q->right);
}
return false;                                                         // Insertion successful
}

// Inorder traversal function based on the prototype
void inorder(Node* T) {
if (T == nullptr) {
return;                                                           // If the tree is empty, return without printing
}
cout left);                                                     // Traverse the left subtree
cout key) {
q = p;
stac.push(q);                                                     // Store parent node in stack
if (deleteKey < p->key) p = p->left;                              // Search left subtree
else p = p->right;                                                // Search right subtree
}

if (p == nullptr) {
cerr right) ||
(height(p->left) == height(p->right) && size(p->left) < size(p->right))) {
p = p->right;
while (p->left != nullptr) {
stac.push(p);
p = p->left;
}
} else {
p = p->left;
while (p->right != nullptr) {
stac.push(p);
p = p->right;
}
}

tempNode->key = p->key;
q = stac.top();
}

// Case when the node has no children
if (p->left == nullptr && p->right == nullptr) {
if (q == nullptr) T = nullptr;                                    // If the node is the root
else if (q->left == p) q->left = nullptr;                         // If the node is the left child of parent
else q->right = nullptr;                                          // If the node is the right child of parent
}

// Case when the node has one child
else {
Node* child = (p->left != nullptr) ? p->left : p->right;          // Choose the child node
if (q == nullptr) T = child;                                      // If the node is the root
else if (q->left == p) q->left = child;                           // If the node is the left child of parent
else q->right = child;                                            // If the node is the right child of parent
}

delete p;                                                             // Delete the node and free memory

// Update the height and size of parent nodes
while (!stac.empty()) {
q = stac.top();
stac.pop();
q->height = 1 + (height(q->left) > height(q->right) ? height(q->left) : height(q->right));
q->size = 1 + size(q->left) + size(q->right);
}

return T;                                                             // Return the updated tree
}

// Clear algorithm to free memory of all nodes in the BST
void clear(Node* T) {
if (T == nullptr) return;                                             // Return if the tree is empty
clear(T->left);                                                       // Clear the left subtree
clear(T->right);                                                      // Clear the right subtree
delete T;                                                             // Delete the current node
}

// main function!
int main() {
Node* root = nullptr;
char op;
int key;

while (cin >> op >> key) {
if (op == 'i') {                                                  // Handle insert command
if (!insertBST(root, key)) {
if (root != nullptr) {                                    // Add newline only if the tree is not empty
inorder(root);
cout  date
Sat Nov  9 12:06:05 UTC 2024

$> clang --version
Apple clang version 16.0.0 (clang-1600.0.26.3)
Target: arm64-apple-darwin23.6.0
Thread model: posix
InstalledDir: /Library/Developer/CommandLineTools/usr/bin

$> clang++ --version
Apple clang version 16.0.0 (clang-1600.0.26.3)
Target: arm64-apple-darwin23.6.0
Thread model: posix
InstalledDir: /Library/Developer/CommandLineTools/usr/bin

= Compiling ====================================================================
$> clang++ -Wall -Wextra -Werror -g3 /Users/runner/work/test/test/submit/main.cpp -o user_exe

= TEST CASE - simple00 =======================================================
$> ./user_exe < simple00
$> diff -u user_output_simple00 test_output_simple00
--- /Users/runner/work/test/test/output/__bstree/user_output_simple00   2024-11-09 12:06:17$
+++ /Users/runner/work/test/test/output/__bstree/test_output_simple00   2024-11-09 12:06:17$
@@ -39,3 +39,4 @@$
< 50 < 100 < 999 >>>$
< 100 < 999 >>$
< 999 >$
+$

Diff KO :(

= TEST CASE - simple01 =======================================================
$> ./user_exe < simple01
$> diff -u user_output_simple01 test_output_simple01
--- /Users/runner/work/test/test/output/__bstree/user_output_simple01   2024-11-09 12:06:18$
+++ /Users/runner/work/test/test/output/__bstree/test_output_simple01   2024-11-09 12:06:18$
@@ -17,3 +17,4 @@$
< 8 < 9 < 10 >>>$
< 9 < 10 >>$
< 10 >$
+$

Diff KO :(

= TEST CASE - simple02 =======================================================
$> ./user_exe < simple02
$> diff -u user_output_simple02 test_output_simple02
--- /Users/runner/work/test/test/output/__bstree/user_output_simple02   2024-11-09 12:06:19$
+++ /Users/runner/work/test/test/output/__bstree/test_output_simple02   2024-11-09 12:06:19$
@@ -17,3 +17,4 @@$
 10 >$
 10 >$
< 10 >$
+$

Diff KO :(

= TEST CASE - random00 =======================================================
$> ./user_exe < random00
$> diff -u user_output_random00 test_output_random00

Diff OK :D

= TEST CASE - random01 =======================================================
$> ./user_exe < random01
$> diff -u user_output_random01 test_output_random01

Diff OK :D

= TEST CASE - random02 =======================================================
$> ./user_exe < random02
$> diff -u user_output_random02 test_output_random02

Diff OK :D

= TEST CASE - random03 =======================================================
$> ./user_exe < random03
$> diff -u user_output_random03 test_output_random03

Diff OK :D

= TEST CASE - random04 =======================================================
$> ./user_exe < random04
$>  diff -u user_output_random04 test_output_random04

Diff OK :D
[/code]
Что я пробовал:
Я реализовал функции вставки, удаления и упорядочения в соответствии с требованиями назначения.
Я использовал некоторое время цикл для обработки входных команд и вставки или удаления узлов по запросу.
После каждой операции я печатал порядок обхода дерева, как указано.
Что я ожидал:
После каждой операции вставки и удаления я ожидал, что программа чтобы правильно напечатать обход дерева по порядку.
В частности, при удалении последнего узла и создании пустого дерева я ожидал, что программа напечатает новую строку без каких-либо узлов дерева.
Что на самом деле произошло:
Программа работала нормально для большинства операций, корректно печатая дерево после вставок и удалений.
Однако при удалении последнего узла программа не печатала новую строку, как требовалось, а вместо этого уходила вывод неполный. 

Подробнее здесь: [url]https://stackoverflow.com/questions/79172811/bst-insert-delete-program-fails-some-tests-need-help-fixing-test-case-outputs[/url]

Ответить Пред. тема След. тема

1 сообщение • Страница 1 из 1

Быстрый ответ

Заголовок:

Имя пользователя:

Изменение регистра текста:

Смайлики

Ещё смайлики…

К этому ответу прикреплено по крайней мере одно вложение.

Если вы не хотите добавлять вложения, оставьте поля пустыми. Можно прикреплять файлы, перетаскивая их в окно сообщения.

Максимально разрешённый размер вложения: 15 МБ.

Имя файла:

Комментарий к файлу:

Имя файла	Комментарий к файлу	Размер	Статус

Похожие темы

Ответы

Просмотры

Последнее сообщение

Нужна помощь в коде Java. Проходит 3 тестового примера.

Последнее сообщение Anonymous « 28 июн 2025, 17:54
Добавлено в форуме JAVA

Anonymous » 28 июн 2025, 17:54 » в форуме JAVA

Zig-ZAG-массив чередуется между элементами меньше, чем и больше, чем их соседние элементы. Преобразовать массив целых чисел в Zig-ZAG-массив с минимальным количеством замен. Ваша задача - определить минимальное количество необходимых замен.
public...

0 Ответы

2 Просмотры

Последнее сообщение Anonymous
28 июн 2025, 17:54
Тесты не найдены — пустой набор тестов при запуске тестового примера jUnit 5 в простом проекте Spring Boot Maven.

Последнее сообщение Anonymous « 06 дек 2024, 13:05
Добавлено в форуме JAVA

Anonymous » 06 дек 2024, 13:05 » в форуме JAVA

Итак, мы поняли суть

Process finished with exit code 0
Empty test suite.

При попытке запустить тестовые сценарии Junit5 в нашем многомодульном проекте, чтобы проверить источники проблемы, я решил попробовать новый проект с нуля (я использую...

0 Ответы

20 Просмотры

Последнее сообщение Anonymous
06 дек 2024, 13:05
Как разрешить определенные различия в текстовом утверждении для тестового примера, который имеет некоторые ожидаемые изм

Последнее сообщение Anonymous « 07 май 2025, 18:00
Добавлено в форуме Php

Anonymous » 07 май 2025, 18:00 » в форуме Php

Я настраиваю тестовый пример золотого мастера, однако результат может быть выключен в определенные моменты из-за побочных эффектов, изменяющих некоторые строки в известных местах.$this->assertSame($expected, $actual);

Сбой сейчас каждый раз.
Как...

0 Ответы

9 Просмотры

Последнее сообщение Anonymous
07 май 2025, 18:00
Как разрешить определенные различия в текстовом утверждении для тестового примера, который имеет некоторые ожидаемые изм

Последнее сообщение Anonymous « 07 май 2025, 22:58
Добавлено в форуме Php

Anonymous » 07 май 2025, 22:58 » в форуме Php

Я настраиваю тестовый пример золотого мастера, однако результат может быть выключен в определенные моменты из-за побочных эффектов, изменяющих некоторые строки в известных местах.$this->assertSame($expected, $actual);

Сбой сейчас каждый раз.
Как...

0 Ответы

8 Просмотры

Последнее сообщение Anonymous
07 май 2025, 22:58
VSCode Test Explorer зависает, несмотря на отсутствие ошибок в выходных данных и сбор всех тестов (в выходных данных)

Последнее сообщение Anonymous « 07 янв 2025, 13:12
Добавлено в форуме Python

Anonymous » 07 янв 2025, 13:12 » в форуме Python

У меня было много проблем с Test Explorer в VSCode. До прошлой недели все работало нормально. Я писал новые тесты и нажимал «Обновить тесты», а потом он внезапно (и довольно случайно) перестал работать — в частности, он «обнаруживает» тесты...

0 Ответы

25 Просмотры

Последнее сообщение Anonymous
07 янв 2025, 13:12

Вернуться в «C++»