C++二进制搜索树删除问题

我是C++新手。我的背景是PHP和C#。我在Visual Studio 2005 中用VC++实现二进制搜索树

所有操作都很好，我在一个特定的场景中面临删除问题，即当我尝试删除头部两次或多次时。

建议的策略是

在右侧子树中查找最小值

用最小值替换要删除的节点

删除最小值

在我的代码中，8在顶部，当我第一次删除顶部时，超过11从右侧子树变为顶部，如果我删除任何其他节点，代码运行良好，但如果我再次删除顶部(删除8之后现在是11)，我得到以下错误

Windows在BinarySearchTreeByList.exe中触发了断点。

这可能是由于堆损坏，表明>BinarySearchTreeByList.exe或其加载的任何DLL中存在错误。

输出窗口可能有更多的诊断信息

以下是完整的代码

#include "stdafx.h"
#include <stdio.h>
#include <tchar.h>
#include <list>
#include <iostream>
typedef struct node
{
node* left;
node* right;
node* parent;
int val;
};
using namespace std;
void insert_node(node** iterate, int newVal, node* newParent);
void traverse(node* iterate);
void del(node** iterate, int newVal, char direction);

void traverse(node* iterate)
{
if(iterate != NULL)
{
traverse(iterate->left);
printf("%d ",iterate->val);
traverse(iterate->right);
}
}

void del(node** iterate, int newVal, char direction)
{
if((*iterate) == NULL)
return;
if((*iterate)->val == newVal)
{
if((*iterate)->left == NULL && (*iterate)->right == NULL)
{
if(direction == 't')
{
node* deleted = *iterate;
*iterate = NULL;
free(deleted);
}
if(direction == 'l')
{
node* deleted = (*iterate)->parent->left;
(*iterate)->parent->left = NULL;
free(deleted);
}
if(direction == 'r')
{
node* deleted = (*iterate)->parent->right;
(*iterate)->parent->right = NULL;
free(deleted);
}
return;
}
if((*iterate)->left == NULL)
{
if(direction == 't')
{
node* deleted = *iterate;
*iterate = (*iterate)->right;
(*iterate)->parent = NULL;
free(deleted);
}
if(direction == 'l')
{
node* deleted = *iterate;
(*iterate)->parent->left = (*iterate)->right;
free(deleted);
}
if(direction == 'r')
{
node* deleted = *iterate;
(*iterate)->parent->right = (*iterate)->right;
free(deleted);
}
return;
}
if((*iterate)->right == NULL)
{
if(direction == 't')
{
node* deleted = *iterate;
*iterate = (*iterate)->left;
(*iterate)->parent = NULL;
free(deleted);
}
if(direction == 'l')
{
node* deleted = *iterate;
(*iterate)->parent->left = (*iterate)->left;
free(deleted);
}
if(direction == 'r')
{
node* deleted = *iterate;
(*iterate)->parent->right = (*iterate)->left;
free(deleted);
}
return;
}
node* findmin = (*iterate)->right;
int minVal = 0;
while(findmin != NULL)
{
minVal = findmin->val;
findmin = findmin->left;
}
(*iterate)->val = minVal;
del(&((*iterate)->right), minVal, 'r');
return;
}
if(newVal < (*iterate)->val)
del(&((*iterate)->left) ,newVal, 'l');
else
del(&((*iterate)->right) ,newVal, 'r');
}

void insert_node(node** iterate, int newVal, node* newParent)
{
if(*iterate == NULL)
{
node* newNode = (node*)malloc(sizeof(node));
newNode->val = newVal;
newNode->left = NULL;
newNode->right = NULL;
newNode->parent = newParent;
*iterate = newNode;
return;
}
if(newVal < (*iterate)->val)
insert_node(&((*iterate)->left) , newVal, *iterate);
else
insert_node(&((*iterate)->right) , newVal, *iterate);
}
int main()
{
node* iterate = NULL;
insert_node(&iterate, 8, NULL);
insert_node(&iterate, 15, NULL);
insert_node(&iterate, 4, NULL);
insert_node(&iterate, 2, NULL);
insert_node(&iterate, 1, NULL);
insert_node(&iterate, 3, NULL);
insert_node(&iterate, 7, NULL);
insert_node(&iterate, 6, NULL);
insert_node(&iterate, 11, NULL);
insert_node(&iterate, 22, NULL);
insert_node(&iterate, 12, NULL);
insert_node(&iterate, 13, NULL);    

traverse(iterate);
printf("nn");
del(&iterate, 8, 't');
del(&iterate, 22, 't');
del(&iterate, 7, 't');
del(&iterate, 11, 't');
printf("nn");
traverse(iterate);
cin.clear();
cin.ignore(255, 'n');
cin.get(); 
}

感谢您的帮助

您的问题是，当您删除一个节点时，您将被删除的父节点的子节点指针设置为被删除节点的子级，但您没有将被删除父节点的父节点指针设置为子级。

例如：

if(direction == 'l')
{
node* deleted = *iterate;
(*iterate)->parent->left = (*iterate)->right;
deleted->right->parent = deleted->parent;
free(deleted);
}

你漏掉了deleted->right->parent = deleted->parent;行，我加了它。代码中还有一些地方应该以相同的方式进行修复。

您的问题是，在删除带有子节点的节点时，不会更新父节点。parent字段仅在插入节点时指定，因此您有一个定义良好的树。在某些情况下也可以设置它，例如，当只有一个子项并且方向为't'时。

在'l'和'r'的情况下，如果开始在节点周围抖动而不更新已删除节点的子节点的父节点，则会破坏树。

相关内容

最新更新

热门标签：