-2
Ich bin versucht, ein Programm auf Binary Tree.Es gibt ein Problem in deleteValue(). Wenn ich deleteValue() nicht aufrufen, läuft das Programm tadellos. Aber wenn ich deleteValue() rufe, zeigt es, dass binaryTree.exe funktioniert nicht mehr.C++ - Programm für Binary Tree
deletevalue() Funktion
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;
}
Der Ausgang I
bin immer20 30 50 100 400
100 20 30 50 400
Segmentation fault (core dumped)
Nach dem Debuggen ich Störung erhalte
Program received signal SIGSEGV, Segmentation fault.
0x08048c4e in BinaryTree<int>::deleteValue (this=0xbfffed04, val=20) at bt1.cpp:206
206 parent->right = node->right;