我在將一些值插入到一個線程化的二叉樹中時遇到了問題。在我的主要功能,如果我嘗試插入這些值 a.Insert(10); a.Insert(27); a.Insert(20); a.Insert(20); (5); a.Insert(18); a.Insert(4); (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]
請使用調試器併發布說明您的問題的最小工作示例。我們不喜歡這裏的代碼。 – 2013-04-24 19:05:27
你從不檢查你的''left'或''''成員是否爲NULL,然後在你的Display函數中對它們進行解引用。我會以此開始。然後,我可能會修復樹實現本身,因爲它現在是相當破碎的。 – WhozCraig 2013-04-24 20:51:44