我无法将一些值插入到线程二叉树中。在我的主要功能中，如果我尝试插入这些值 a.Insert(10); a.插入（27）；a.插入（20）；a.插入（20）；a.插入（5）；a.插入（18）；a.插入（4）；a.插入（19）；
一切正常，但如果我切换 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]