-2
私はバイナリツリーでプログラムを作成しようとしています。deleteValue()に問題があります。私がdeleteValue()と呼ぶのでなければ、プログラムは完璧に動作します。しかしdeleteValue()と呼ぶと、binaryTree.exeが動作を停止したことを示しています。バイナリツリーのC++プログラム
deleteValue（）関数
void deleteValue(T val)
{
// Node* temp =root;
Node* node = search(root,val);
Node* parent;
Node* child;
//leaf node
if(node->left == nullptr && node->right == nullptr)
{
if(parent->left == node) parent->left == nullptr;
else if(parent->right == node) parent->right == nullptr;
delete node;
return;
}
//node having only one child
//replace it with its child and delete
if((node->left == nullptr && node->right != nullptr)|| (node->left != nullptr && node->right == nullptr))
{
if(node->left == nullptr && node->right != nullptr) //right child present
{
if(parent->left == node) //line 198
{
parent->left = node->right;
delete node;
return;
}
else
{
parent->right = node->right;
delete node;
return;
}
}
else //left child present
{
if(parent->left == node)
{
parent->left = node->left;
delete node;
return;
}
else
{
parent->right = node->left;
delete node;
return;
}
}
}
//Node with 2 children
// replace node with smallest value in right subtree
if (node->left != nullptr && node->right != nullptr)
{
Node* chkr;
chkr = node->right;
if((chkr->left == nullptr) && (chkr->right == nullptr))
{
node = chkr;
delete chkr;
node->right = nullptr;
return;
}
else // right child has children
{
//if the node's right child has a left child
// Move all the way down left to locate smallest element
if((node->right)->left != nullptr)
{
Node* lcurrp = node->right;
Node* lcurr = minimum(lcurrp);
node->data = lcurr->data;
lcurrp->left = nullptr;
delete lcurr;
return;
}
else
{
Node* tmp;
tmp = node->right;
node->data = tmp->data;
node->right = tmp->right;
delete tmp;
return;
}
}
return;
}
}
binaryTree.cpp
#include <iostream>
template<class T>
class BinaryTree
{
struct Node
{
Node* parent;
Node* left;
Node* right;
T data;
Node(T const& val):parent(nullptr),left(nullptr),right(nullptr),data(val) {}
// This is the move constructor
// It moves the content of `val` into the node. For
// types like vectors this is much more efficient as it
// simply means copying three (or so) pointers and thus
// transferring the internal containers without the cost
// of copying all the elements in the vector.
Node(T&& val):parent(nullptr),left(nullptr),right(nullptr),data(std::move(val)) {}
//to enter any number and type of arguments
template<typename... Args>
Node(Args&&... args):parent(nullptr),left(nullptr),right(nullptr),data(std::forward<Args>(args)...) {}
~Node()
{
delete left;
delete right;
}
};
struct Node* root;
public:
BinaryTree():root(nullptr) {}
BinaryTree(BinaryTree const&) = delete;
BinaryTree& operator=(BinaryTree const&) = delete;
~BinaryTree()
{
delete root;
}
bool isEmpty() const
{
return root == nullptr;
}
//returns node of the element
Node* search(Node* root, T val) const
{
if(root == nullptr||val == root->data) return root;
if(val < root->data) return search(root->left,val);
else return search(root->right,val);
}
Node* minimum(Node* root)
{
while(root->left != nullptr)
root = root->left;
return root;
}
Node* maximum(Node* root)
{
while(root->right != nullptr)
root = root->right;
return root;
}
//Successor - a node which has the next higher key
Node* successor(Node* node)
{
if(node->right!=nullptr) return minimum(node->right);
Node* temp = node->parent;
while(temp != nullptr && node == temp->right)
{
node = temp;
temp = temp->parent;
}
return temp;
}
//Predecessor - a node which has the next lower key
Node* predecessor(Node* node)
{
if(node->left != nullptr) return maximum(node->left);
Node* temp = node->parent;
while(temp != nullptr && node == temp->left)
{
node = temp;
temp = temp->parent;
}
return temp;
}
void insertValue(T const& val)
{
Node* node = new Node(val);
Node* parent;
node->left = nullptr;
node->right = nullptr;
parent = nullptr;
if(isEmpty()) root = node;
else
{
Node* curr = root;
while(curr)
{
parent = curr;
if(node->data > curr->data) curr = curr->right;
else curr = curr->left;
}
if(node->data < parent->data) parent->left = node;
else parent->right = node;
}
}
void insertValue(T&& val)
{
Node* node = new Node(std::move(val));
Node* parent;
node->left = nullptr;
node->right = nullptr;
parent = nullptr;
if(isEmpty()) root = node;
else
{
Node* curr = root;
while(curr)
{
parent = curr;
if(node->data > curr->data) curr = curr->right;
else curr = curr->left;
}
if(node->data < parent->data) parent->left = node;
else parent->right = node;
}
}
template<typename... Args>
void insertValue(Args&&... args)
{
Node* node = new Node(std::forward<Args>(args)...);
Node* parent;
node->left = nullptr;
node->right = nullptr;
parent = nullptr;
if(isEmpty()) root = node;
else
{
Node* curr = root;
while(curr)
{
parent = curr;
if(node->data > curr->data) curr = curr->right;
else curr = curr->left;
}
if(node->data < parent->data) parent->left = node;
else parent->right = node;
}
}
void deleteValue(T val)
{
// Node* temp =root;
Node* node = search(root,val);
Node* parent;
Node* child;
//leaf node
if(node->left == nullptr && node->right == nullptr)
{
if(parent->left == node) parent->left == nullptr;
else if(parent->right == node) parent->right == nullptr;
delete node;
return;
}
//node having only one child
//replace it with its child and delete
if((node->left == nullptr && node->right != nullptr)|| (node->left != nullptr && node->right == nullptr))
{
if(node->left == nullptr && node->right != nullptr) //right child present
{
if(parent->left == node) //line 198
{
parent->left = node->right;
delete node;
return;
}
else
{
parent->right = node->right;
delete node;
return;
}
}
else //left child present
{
if(parent->left == node)
{
parent->left = node->left;
delete node;
return;
}
else
{
parent->right = node->left;
delete node;
return;
}
}
}
//Node with 2 children
// replace node with smallest value in right subtree
if (node->left != nullptr && node->right != nullptr)
{
Node* chkr;
chkr = node->right;
if((chkr->left == nullptr) && (chkr->right == nullptr))
{
node = chkr;
delete chkr;
node->right = nullptr;
return;
}
else // right child has children
{
//if the node's right child has a left child
// Move all the way down left to locate smallest element
if((node->right)->left != nullptr)
{
Node* lcurrp = node->right;
Node* lcurr = minimum(lcurrp);
node->data = lcurr->data;
lcurrp->left = nullptr;
delete lcurr;
return;
}
else
{
Node* tmp;
tmp = node->right;
node->data = tmp->data;
node->right = tmp->right;
delete tmp;
return;
}
}
return;
}
}
void inOrder(Node* node)
{
if(node != nullptr)
{
if(node->left) inOrder(node->left);
std::cout<<" "<<node->data;
if(node->right) inOrder(node->right);
}
else return;
}
void print_inOrder()
{
inOrder(root);
}
void preOrder(Node* node)
{
if(node != NULL)
{
std::cout<<" "<<node->data;
if(node->left) preOrder(node->left);
if(node->right) preOrder(node->right);
}
else return;
}
void print_preOrder()
{
preOrder(root);
}
void postOrder(Node* node)
{
if(node != NULL)
{
if(node->left) postOrder(node->left);
if(node->right) postOrder(node->right);
std::cout<<" "<<node->data;
}
else return;
}
void print_postOrder()
{
postOrder(root);
}
};
int main()
{
BinaryTree<int> bt1;
bt1.insertValue(100);
bt1.insertValue(20);
bt1.insertValue(30);
bt1.insertValue(400);
bt1.insertValue(50);
bt1.print_inOrder();
std::cout<<"\n";
bt1.print_preOrder();
std::cout<<"\n";
bt1.print_postOrder();
bt1.deleteValue(20);
std::cout<<"\n";
bt1.print_inOrder();
std::cout<<"\n";
bt1.print_preOrder();
std::cout<<"\n";
bt1.print_postOrder();
return 0;
}
私はエラー
Program received signal SIGSEGV, Segmentation fault.
0x08048c4e in BinaryTree<int>::deleteValue (this=0xbfffed04, val=20) at bt1.cpp:206
206 parent->right = node->right;
20 30 50 100 400
100 20 30 50 400
Segmentation fault (core dumped)
を取得しています出力