0
У меня возникли проблемы с введением некоторых значений в потоковое двоичное дерево. В моей основной функции, если я попытаюсь вставить эти значения a.Insert (10); a.Insert (27); a.Insert (20); a.Insert (20); a.Insert (5); a.Insert (18); a.Insert (4); a.Insert (19);Вставка в резьбовое двоичное дерево в C++
Все работает нормально, но если я переключу 27 и 20, я получаю ошибку сегментации.
Вот мой код и рабочий выход.
struct bstNode{
int data;
bool lthread;
bool rthread;
bstNode *left;
bstNode *right;
bstNode(int value){
lthread = false;
rthread = false;
data = value;
left = NULL;
right = NULL;
};
int GetData() {return data;}
void SetLeft(bstNode *l){ left = l;}
bstNode *GetLeft() {return left;}
bstNode *GetRight() {return right;}
void SetRight(bstNode *r){ right = r;}
void SetLeftThread(bool value){lthread = value;}
void SetRightThread(bool value){rthread = value;}
bool GetLeftThread() {return lthread;}
bool GetRightThread() {return rthread;}
bool IsLeft(){
if(left == NULL)
return false;
else
return true;
}
bool IsRight(){
if(right == NULL)
return false;
return true;
}
};
class BinarySearchTree{
public:
BinarySearchTree(){root = NULL;};
void Insert(int);
void Display();
bstNode* search(int key);
bstNode* root;
bstNode* current;
};
void BinarySearchTree::Insert(int value){
bstNode *node = new bstNode(value);
if (root == NULL){
root = node;
return;
}
bstNode *ptr = root, *parent = NULL;
while (ptr !=NULL){
if(value == ptr->GetData()){
cout << "Attempted to insert duplicate value: " << value <<" -- Ignored." << endl;
delete node;
return;
}
parent = ptr;
if(value < ptr->GetData()){
if(ptr->GetLeftThread())
break;
else
ptr = ptr->GetLeft();}
else{
if(ptr->GetRightThread())
break;
else{
ptr = ptr->GetRight();}
}
}
if (ptr == NULL)
{
if(value < parent->GetData())
{
parent->SetLeft(node);
node->SetRight(parent);
node->SetRightThread(true);
}
else
{
parent->SetRight(node);
node->SetLeft(parent);
node->SetLeftThread(true);
}
}
else
{
if(value < ptr->GetData())
{
node->SetLeft(ptr->GetLeft());
node->SetLeftThread(true);
node->SetRight(ptr);
node->SetRightThread(true);
ptr->SetLeft(node);
ptr->SetLeftThread(false);
}
else
{
node->SetRight(ptr->GetRight());
node->SetRightThread(true);
node->SetLeft(ptr);
node->SetLeftThread(true);
ptr->SetRight(node);
ptr->SetRightThread(false);
}
}
return;
}
void BinarySearchTree::Display(){
if(root == NULL){
cout << "Empty" << endl;
return;
}
bstNode *p, *q;
p = root;
do
{
while(p != NULL){
q = p;
if(p->GetLeftThread())
break;
else
p = p->GetLeft();
}
cout << q->data << "'s right thread is "<< q->right->data << "\n";
p = q->GetRight();
while(q->GetRightThread()){
cout << p->data << "'s left thread is " << p->left->data << "\n";
q = p;
p = q->GetRight();
}
} while(p != NULL);
}
bstNode* BinarySearchTree::search(int value){
bstNode* current = root;
while (current) {
if(current->data == value){
cout << current->data << " does exist!" << endl;
return current;
}
else if (value < current->data){
current = current->left;
}
else current = current->right;
}
cout << "No "<< value << endl;
return NULL;
}
main(){
BinarySearchTree a;
a.Insert(10);
a.Insert(20);
a.Insert(27);
a.Insert(20);
a.Insert(5);
a.Insert(18);
a.Insert(4);
a.Insert(19);
a.Display();
a.search(19);
cout << "\n" <<endl;
return 0;
}
И выход:
Attempted to insert duplicate value: 20 -- Ignored.
4's right thread is 5
5's left thread is 4
10's left thread is 5
18's right thread is 19
19's right thread is 20
20's left thread is 18
27's left thread is 20
19 does exist!
[Finished in 0.3s]
нефункционирующих выход:
Attempted to insert duplicate value: 20 -- Ignored.
bash: line 1: 26586 Segmentation fault: 11 '/Users/Gnedelka/Desktop/Assignment 6/new/selfcopy'
[Finished in 0.5s with exit code 139]
Пожалуйста, используйте отладчик и разместите минимальный рабочий пример, иллюстрирующий вашу проблему. Здесь нам не нравятся коды кода. –
Вы никогда не проверяете свои члены 'left' или' right' для NULL перед разыменованием их в вашей функции отображения. Я бы начал с этого. Тогда я, вероятно, буду работать над исправлением самой реализации дерева, так как он довольно сломан как есть. – WhozCraig