Я работаю над простой программой для домашней работы на Hackerrank, которая играет с бинарными деревьями и отображает их в порядке следования, предварительного заказа и в порядке наряду с другими функциями. Вот примерный прогон:
15
9
append 10
append 50
isBST
preOrder
append 45
height
levelOrder
deleteLastNode
postOrder
Correct Output:
true
15 10 50
2
15 10 50 45
10 50 15
2-я часть: первая строка (= 15 в примере) указывает, что вы должны построить двоичное дерево со значением root 15. Вторая строка (= 9 в примере) указывает количество команд, которые вы должны выполнить для двоичного дерева. Команды включают «append» (= добавить новый номер в конце дерева), «isBST» (= проверка, является ли двоичное дерево бинарным деревом поиска или нет), «preOrder», «height», «levelOrder» (= посещение дерева по уровням из root), «deleteLastNode» и «postOrder».
Из того, что я понял, когда мой учитель объяснил это: функция добавления является просто просто порядок вставки узлов в дерево. Команда высоты - это просто уровни или глубина дерева (0 это просто root, а -1 вообще не дерево). и deleteLastNode - это последний узел, добавленный в дерево, который я использую в стеке для отслеживания порядка вставленных узлов. Функции заказа просто отображают дерево по порядку, по порядку и т. Д. c.
Теперь я передаю почти все мои тестовые задания по заданию Hackerrank, кроме 2 скрытых, которые приводят к ошибкам сегментации. Один из тестовых примеров, который я пробовал, состоял в том, что сначала нужно было удалить узел root, а затем добавить другой узел / номер, но это, как представляется, не вызвало ошибку сегментации. Затем я попробовал случай, когда вы запускаете функцию deleteLastNode, когда больше нет узлов, но, похоже, это не тот случай, который вызывает ошибку сегментации. Я предполагаю, что ошибки сегментации имеют какое-то отношение к функции deleteLastNode, но я могу ошибаться, и я не могу думать о другом тестовом примере, который действительно вызывает ошибку. Я спрашиваю о том, какие другие возможные тестовые случаи следует знать о том, что может вызвать ошибку сегментации?
Если вам нужно это увидеть, вот мой код:
#include <iostream>
#include<string>
#include <climits>
#include <queue>
#include <string>
#include <stack>
using namespace std;
//struct and node stuff from Dr. Byun
struct Node
{
// Data part for a node.
int data;
Node* left;
Node* right;
// Constructor for a new node.
Node(int d)
{
data = d;
left = nullptr;
right = nullptr;
}
};
Node* mkTree(int data, Node* left, Node* right)
{
Node* root = new Node(data);
root->left = left;
root->right = right;
return root;
}
void inorder(Node* root)
{
if (root) // Or simply "if (root)"
{
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
}
void preOrder(Node* root){
if (root){
cout << root->data << " ";
preOrder(root->left);
preOrder(root->right);
}
}
void postOrder(Node* root){
if(root){
postOrder(root->left);
postOrder(root->right);
cout << root->data << " ";
}
}
//source: https://www.geeksforgeeks.org/insertion-in-a-binary-tree-in-level-order/
void insert(struct Node* temp, int key)
{
queue<struct Node*> q;
q.push(temp);
// Do level order traversal until we find
// an empty place.
while (!q.empty()) {
struct Node* temp = q.front();
q.pop();
if (!temp->left) {
temp->left = new Node(key);
break;
} else
q.push(temp->left);
if (!temp->right) {
temp->right = new Node(key);
break;
} else
q.push(temp->right);
}
}
//source: https://www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/
int isBSTUtil(Node* node, int min, int max)
{
/* an empty tree is BST */
if (node==NULL)
return 1;
/* false if this node violates
the min/max constraint */
if (node->data < min || node->data > max)
return 0;
/* otherwise check the subtrees recursively,
tightening the min or max constraint */
return
isBSTUtil(node->left, min, node->data-1) && // Allow only distinct values
isBSTUtil(node->right, node->data+1, max); // Allow only distinct values
}
void isBST(Node* node)
{
if(isBSTUtil(node, INT_MIN, INT_MAX) == 0){
cout << "false" << endl;
} else{
cout << "true" << endl;
}
}
//source: https://www.geeksforgeeks.org/write-a-c-program-to-find-the-maximum-depth-or-height-of-a-tree/
int height(Node* root)
{
if (!root)
return -1;
else
{
/* compute the depth of each subtree */
int lDepth = height(root->left);
int rDepth = height(root->right);
/* use the larger one */
if (lDepth > rDepth)
return(lDepth + 1);
else
return(rDepth + 1);
}
}
//source: https://www.geeksforgeeks.org/level-order-tree-traversal/
void printGivenLevel(Node* root, int level)
{
if (root == NULL)
return;
if (level == 1)
cout << root->data << " ";
else if (level > 1)
{
printGivenLevel(root->left, level-1);
printGivenLevel(root->right, level-1);
}
}
void levelOrder(Node* root)
{
int h = height(root) + 1;
int i;
for (i = 1; i <= h; i++)
printGivenLevel(root, i);
}
//source: https://www.geeksforgeeks.org/deletion-binary-tree/
void deleteUtil(struct Node* root,
struct Node* d_node)
{
queue<struct Node*> q;
q.push(root);
// Do level order traversal until last node
struct Node* temp;
while (!q.empty()) {
temp = q.front();
q.pop();
if (temp == d_node) {
temp = NULL;
delete (d_node);
return;
}
if (temp->right) {
if (temp->right == d_node) {
temp->right = NULL;
delete (d_node);
return;
}
else
q.push(temp->right);
}
if (temp->left) {
if (temp->left == d_node) {
temp->left = NULL;
delete (d_node);
return;
}
else
q.push(temp->left);
}
}
}
Node* deletion(struct Node* root, int key)
{
if (root == NULL)
return NULL;
if (root->left == NULL && root->right == NULL) {
if (root->data == key)
return NULL;
else
return root;
}
queue<struct Node*> q;
q.push(root);
struct Node* temp;
struct Node* key_node = NULL;
// Do level order traversal to find deepest
// node(temp) and node to be deleted (key_node)
while (!q.empty()) {
temp = q.front();
q.pop();
if (temp->data == key)
key_node = temp;
if (temp->left)
q.push(temp->left);
if (temp->right)
q.push(temp->right);
}
if (key_node != NULL) {
int x = temp->data;
deleteUtil(root, temp);
key_node->data= x;
}
return root;
}
// A sample main to create a binary tree like below.
// 5
// / \
// 3 4
// / \
// 1 2
//
int main()
{
// Node* n1 = new Node(1);
// Node* n2 = new Node(2);
// Node* n3 = mkTree(3, n1, n2);
// Node* n4 = new Node(4);
// Node* n5 = mkTree(5, n3, n4);
//inorder(n5);
//preOrder(n5);
//append(10, n5);
//deletion(n5, 2);
//inorder(n5);
// cout << height(n5);
int start_node;
int loop;
cin >> start_node;
cin >> loop;
Node* n1 = new Node(start_node);
stack<int> s;
s.push(start_node);
//cout << s.top() << endl;
for(int i = 0; i < loop; i++){
string command = "";
cin >> command;
//cout << "Loop number " << i + 1 << " and the command is " << command << endl;
if(command == "append"){
//cout << "reached\n";
if(!s.empty()){
int tempNum;
cin >> tempNum;
s.push(tempNum);
insert(n1, tempNum);
//cout << "Still here?\n";
}else{
int tempNum;
cin >> tempNum;
s.push(tempNum);
n1 = new Node(tempNum);
}
}else if(command == "isBST"){
isBST(n1);
}else if(command == "preOrder"){
preOrder(n1);
cout << endl;
}else if(command == "postOrder"){
postOrder(n1);
cout << endl;
}else if(command == "height"){
cout << height(n1) << endl;
}else if(command == "deleteLastNode"){
//cout << "Is stack empty?: " << s.empty() << endl;
if(s.empty()){
continue;
}else{
int selectedNode = s.top();
n1 = deletion(n1, selectedNode);
//cout << "Tree by lvlorder\n";
//levelOrder(n1); cout << endl;
s.pop();
//cout << "Is stack empty?: " << s.empty() << endl;
}
}else if(command == "levelOrder"){
levelOrder(n1);
cout << endl;
}else if(command == "inOrder"){
inorder(n1);
cout << endl;
}
}
// cout << "Current height: " << height(n1) << endl;
// inorder(n1);
return 0;
}
/**
other sample inputs:
50
7
height
append 5
height
deleteLastNode
height
deleteLastNode
height
30
14
isBST
append 10
append 50
append 5
append 20
append 40
append 70
isBST
append 80
isBST
deleteLastNode
deleteLastNode
isBST
levelOrder
15
9
append 10
append 50
isBST
preOrder
append 45
height
levelOrder
deleteLastNode
postOrder
30
5
deleteLastNode
height
append 10
height
inOrder
40
4
deleteLastNode
deleteLastNode
deleteLastNode
deleteLastNode
30
5
deleteLastNode
deleteLastNode
deleteLastNode
append 12
inOrder
40
5
append 40
append 40
append 40
append 40
inOrder
20
6
deleteLastNode
append 10
append 8
append 30
isBST
inOrder
**/
Я прошу прощения, если это не то место, где можно обратиться за помощью по домашнему заданию.
Редактировать: Теперь я знаю тестовые случаи, которые приводят к неудаче. Это не удается, если вы попытаетесь выполнить функцию добавления более одного раза после запуска функции deleteLastNode. Пример тестового примера для этого:
20
8
append 10
append 10
append 23
deleteLastNode
deleteLastNode
append 33
append 40
inOrder
Программа завершается сбоем всякий раз, когда вы пытаетесь добавить 40. Я не уверен, почему это не удается. Если кто-то хотя бы может объяснить, почему он это делает, я был бы признателен.