从C++二进制搜索树中删除一个节点(类不是结构体)
我试图在C++中管理BST以达到我的学术目的。从C++二进制搜索树中删除一个节点(类不是结构体)
我并没有问题,除了DeleteNode
函数的任何位置,也 我选择来实现与class
,而不是用struct
这个数据结构。
问题是,我无法弄清楚如何使删除功能正常工作,通常我得到0xDDDDDDDDD
错误我的调试器说,有时我可以删除节点,有时我的程序崩溃。
我认为这是指针的一个可能的问题,但我无法弄清楚我做错了什么地方。
这是我删除节点的功能,一个我得到约很大的麻烦:
编辑:没有儿子删除的情况下工作完美,一个我越来越生气的就是单子案删除。
//function that delete a selected node
void DeleteNode(TreeNode* root,int key) {
/*we got three case here:*/
//until we find the right node with value in the tree
if (root->getValue() != key && root != nullptr) {
if (root->getValue() > key) {
DeleteNode(root->Left, key);
}
else if (root->getValue() < key) {
DeleteNode(root->Right, key);
}
}
else { //when we found the right node, then operate
/* THIS WORKS PERFECTLY! */
//first case: our node got no right and left son
if (!root->Left && !root->Right) {
TreeNode* tmp = root->Father;
if (tmp->Left == root) { //if the son is a left son
tmp->Left = nullptr;
delete root;
}
else if (tmp->Right == root) { //if the son is a right son
tmp->Right = nullptr;
delete root;
}
}
//second case: our node got a left but no right son
/* THIS ONE DOESN'T WORK. */
else if (!root->Right) {
TreeNode *tmp = root;
root = root->Left; //new root is the left son of the root
root->Father = tmp->Father; //linking the father to the new son
tmp->Father->Left = root; //linking the son to the new father
delete tmp;
std::cout << "Erased!" << std::endl;
}
else if (!root->Left) {
TreeNode *tmp = root;
root = root->Right; //new root is the right son of the root
root->Father = tmp->Father; //linking the father to the new son
tmp->Father->Right = root; //linking the son to the new father
delete tmp;
std::cout << "Erased!" << std::endl;
}
}
}
我尝试了很多组合的,但结果是相同的,每次:它崩溃上InOrder
显示功能的第一次出现。 (当它不,该功能只删除第一个节点,然后崩溃当我尝试删除一个新的)
这里有一个简单的主那里我试图采取行动删除:
int main()
{
TreeNode root;
root.insertNode(&root,50);
root.insertNode(&root,30);
root.insertNode(&root,20);
root.insertNode(&root,40);
root.insertNode(&root,70);
root.insertNode(&root,60);
root.insertNode(&root,80);
for (int i = 0; i < 5; i++) {
int n;
cin >> n;
root.DeleteNode(&root, n);
cout << "In-Order: "; root.inOrder(&root);
cout << endl;
cout << "Pre-Order: "; root.preOrder(&root);
cout << endl;
cout << "Post-Order: "; root.postOrder(&root);
cout << endl;
}
}
这里是我的全BST代码(除删除一个,我之前递交,仅仅因为是在我的代码的理解更完整)
class TreeNode {
private:
int value;
TreeNode* Left;
TreeNode* Right;
TreeNode* Father;
public:
//constructor
TreeNode() {
this->Right = nullptr;
this->Left = nullptr;
this->Father = nullptr;
}
TreeNode(int value) {
this->value = value;
this->Right = nullptr;
this->Left = nullptr;
this->Father = nullptr;
}
//functions
int getValue() { return value; }
void setValue(int value) { this->value = value; }
//function to create a new node and insert a value into it
TreeNode* insertNode(TreeNode* root, int value) {
if (root->getValue() == NULL) {
root->setValue(value);
root->Father = nullptr;
}
else {
if (value > root->getValue()) {
if (root->Right) {
insertNode(root->Right, value);
}
else
root->Right = new TreeNode(value);
root->Right->Father = root;
}
else if (value < root->getValue()) {
if (root->Left) {
insertNode(root->Left, value);
}
else
root->Left = new TreeNode(value);
root->Left->Father = root;
}
}
return root;
}
//function to search a value into a BST
TreeNode* SearchNode(TreeNode* root, int key) {
if (root->getValue() == key) {
return root;
}
else if (root->getValue() < key) {
if (root->Right) {
SearchNode(root->Right, key);
}
else return nullptr;
}
else if (root->getValue() > key) {
if (root->Left) {
SearchNode(root->Left, key);
}
else return nullptr;
}
}
//function that return the height of the tree
int TreeHeigth(TreeNode* root) {
int heigth;
if (root == nullptr) {
return 0;
}
else {
return heigth = 1 + max(TreeHeigth(root->Left), TreeHeigth(root->Right));
}
}
//function that returns the number of the nodes
int CountTreeNode(TreeNode* root) {
if (root == nullptr) {
return 0;
}
else {
return CountTreeNode(root->Left) + CountTreeNode(root->Right) + 1;
}
}
//function that returns the minimum values into the tree
TreeNode* MinimumNode(TreeNode* root) {
if (root == nullptr) {
return nullptr;
}
while (root->Left != nullptr) {
root = root->Left;
}
return root;
}
//function that returns the maximum value into the tree
TreeNode* MaximumNode(TreeNode* root) {
if (root == nullptr) {
return nullptr;
}
while (root->Right != nullptr) {
root = root->Right;
}
return root;
}
//function that returns a successor of a given nodeb
TreeNode* SuccessorNode(TreeNode* node) {
//first case: our node got a rigth subtree:
if (node->Right != nullptr) {
return MinimumNode(node->Right);
}
//second case: our node doesnt got a right subtree: lets get
//upper in the tree until our node isn't a left child.
TreeNode* Ancestor = node->Father;
while (Ancestor != nullptr && node == Ancestor->Right) {
node = Ancestor;
Ancestor = Ancestor->Father;
}
}
//function tht returns a predecessor of a given node
TreeNode* PredecessorNode(TreeNode* node) {
//first case: (inverse to successor) our node got a left subtree:
if (node->Left != nullptr) {
return MaximumNode(node->Left);
}
TreeNode* Ancestor;
if (node->Father == nullptr)
return nullptr;
else
Ancestor = node->Father;
while (Ancestor != nullptr && node == Ancestor->Left) {
node = Ancestor;
Ancestor = Ancestor->Father;
}
return Ancestor;
}
//function that prints information about nodes
void InfoNode(TreeNode *root) {
root != nullptr ? std::cout << "Nodo corrente: " << root->getValue() << std::endl
: std::cout << "Nodo corrente: " << "NULL" << std::endl;
root->Father != nullptr? std::cout << "Padre: " << root->Father->getValue() << std::endl
: std::cout << "Padre: " << "NULL" << std::endl;
root->Left != nullptr ? std::cout << "Figlio SX: " << root->Left->getValue() << std::endl
: std::cout << "Figlio SX: " << "NULL" << std::endl;
root->Right!= nullptr ? std::cout << "Figlio DX: " << (root->Right)->getValue() << std::endl
: std::cout << "Figlio DX: " << "NULL" << std::endl;
}
//visits of a tree
void preOrder(TreeNode* root) {
if (root != nullptr) {
std::cout << root->getValue() << " ";
preOrder(root->Left);
preOrder(root->Right);
}
}
void inOrder(TreeNode* root) {
if (root != nullptr) {
inOrder(root->Left);
std::cout << root->getValue() << " ";
inOrder(root->Right);
}
}
void postOrder(TreeNode *root) {
if (root != nullptr) {
postOrder(root->Left);
postOrder(root->Right);
std::cout << root->getValue() << " ";
}
}
//max between 2 numbers
int max(int a, int b) {
return a > b ? a : b;
}
};
还有就是我努力工作,在树的表示:
50
/ \
30 70
/\ /\
20 40 60 80
我在哪里做错了?
看这个条件:root->getValue() != key && root != nullptr
,这首先调用getValue
,之后检查root
有合法的价值。交换他们(root != nullptr && root->getValue() != key
)。
最后我想你必须改变最后一行到tmp->Father->Left = root;
来修复崩溃问题。
TreeNode *tmp = root;
root = root->Right; //new root is the right son of the root
root->Father = tmp->Father; //linking the father to the new son
tmp->Father->Right = root; //linking the son to the new father
PS:也这样做换来对方...
注:这是真的,直到root
留给他的父亲的孩子,否则你的代码是正确的。正是你必须检查root
是左边的孩子,如果他的父亲做tmp->Father->Left = root;
其他tmp->Father->Right = root;
注:正如你提到你的代码不处理节点的缺失有两个子女。
感谢您的注意,只是调整了。但仍然崩溃! – Asynchronousx
@Asynchronousx将'this-> value = NULL'添加到您的TreeNode构造函数中。首先root拥有不是'NULL'的垃圾值。 –
完成,谢谢你的附加说明。 – Asynchronousx
前面已经有一个答案给你方向纠正特定的错误,我会尽量把重点放在一个建议,这将有助于你避免类似的错误都在一起:
试试你的当前功能分离成两块:
一,搜索特定关键字的节点,例如:
Node* search(int key)
函数返回要么指向与通缉键或nullptr
节点,或使用你已经有了一个。一个删除(并重新连接)作为指针传递的节点并返回:next,previous等:
Node* delete(Node* n)
。
然后调用search
,测试针对nulltpr
,并且如果不同,通过返回的指针如在delete
输入参数。
通过这种方式,您可以轻松检测到您在哪个阶段出现问题:搜索或删除。
P.S .:计算出重新布线的错误通常是通过图表(方框和箭头)完成的。决定你应该做什么,将其分成若干步骤并实施。
我用visual studio调试我的程序,一步一步地检查指针值和每一步的值本身。 看来,搜索代码行效果很好,因为它找到了我想要的节点,我得到麻烦的是删除节点,当我的节点只有一个儿子。 – Asynchronousx
@Asynchronousx确切地说,如果问题只与'delete'部分有关,那么你和其他人都可能会阅读你的代码,这会更容易阅读和最终检测。 – Ziezi
但问题仅与删除有关,因为其他一切都像魅力一样。导致我头痛的唯一部分是删除单节点子情况。 (左侧或右侧) – Asynchronousx
那么,一旦有人知道DEBUG版本使用定点值,在代码中发现问题变得更加微不足道。
0xDD是死的记忆。这是已被删除的内存。因此,当调试器停止并且它告诉您指针不正确且数据包含大量0xDD时,您知道数据已被删除。此时,您应该检查包含数据的类以查看它们是否被删除,以便知道哪些对象被嵌入到另一个中时会被删除。
请注意,如果某些操作使用删除内存,某些时候可能会有一些数据在类的一部分中进行了更改。查看内存模式还有助于查找未初始化的内存和其他类似问题。
其他一些环节:
- Why does the not allocated memory is marked like 0xCC?
- https://msdn.microsoft.com/en-us/library/974tc9t1.aspx
- https://www.codeguru.com/cpp/w-p/win32/tutorials/article.php/c9535/Inside-CRT-Debug-Heap-Management.htm
- http://www.nobugs.org/developer/win32/debug_crt_heap.html
在你们这样的情况下,如果你遵循的编写单元测试的很好的做法,那么发现问题甚至会更加微不足道。事实上,如果您进行了适当的测试,那么您将测试所有可能的案例,以便您知道哪些案例会失败,并帮助您找到可能出错的地方。
非常感谢您提供有用的信息。 – Asynchronousx
我想补充一些@Bonje Fir的答案。 当然,这是一个正确的答案,但部分:我会解释为什么。
他建议互换的最后一块代码,我写道:
案例:我们在右子树,我们想抹去70(因为我们没有了叶子节点60) :由于代码是说,一旦你与他的儿子更新了新的根
TreeNode *tmp = root;
root = root->Right; //new root is the right son of the root
root->Father = tmp->Father; //linking the father to the new son
tmp->Father->Left (instead of Right) = root; //linking the son to the new father
:
50
/ \
30 70
/\ \
20 40 80
现在,与@Bonje冷杉建议我们的代码,我们将有一个问题在这里,链接th父亲与他的左儿子之前的根(我们保存在一个tmp变量中)的父亲。然后我们会协助这样的事情:
50
/ x
80 80
/\
20 40
而且这是不一致的。
现在采取的另一边一看,用相同的代码,无叶节点20:
50
/ \
30 70
\ /\
40 60 80
代码适合在这里,因为我们是在右子树。 所以一旦更新30 40(root = root -> right
)的情况会是这样:
50
x \
40 70
/\
60 80
那么一块代码@Bonje杉木给我们来信,会伏贴:
tmp->Father->Left = root
,因为肯定的,我们将40分配给原始根的父亲的左儿子。 (因为我们在左子树)。
50
/ \
40 70
/\
60 80
所以我做了一点改变来纠正这个逻辑问题,并使其在左,右子树工作两者。
else if (!root->Left) {
TreeNode *tmp = root;
root = tmp->Right;
root->Father = tmp->Father; //linking the father to the new son
//we need also to connect the son with the father, but first
//we need to know in which subtree we're in.
if (root->Father->Right == tmp) //if we're in the right subtree
tmp->Father->Right = root;
else ////if we're in the left subtree
tmp->Father->Left = root;
delete tmp;
std::cout << "Erased!" << std::endl;
}
我注意到这一事实,我没有抹去我的根的优势,一旦分配了新的,所以根的父亲仍然指向旧的根。
(对于相反的情况相同的语音)。
注意:类和结构之间没有根本的区别。一个结构默认情况下所有成员都是'public',而一个类有'private'。 – Darhuuk
我也尝试设置所有的指针,父亲,左,右儿子公共,但这根本没有帮助。 – Asynchronousx
另一个边节点:这看起来像是从二叉树中删除节点的代码,而不是二叉搜索树(它需要在删除内部节点后重新排序节点)。 – Darhuuk