C++二叉搜索树删除问题

Question

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

所有操作都很好，我在一种特定情况下遇到删除问题，即当我尝试删除 head 两次或更多次时。

建议的策略是

1. Find minimum in the right sub tree
2. Replace the node you want to delete with minimum
3. delete minimum

在我的代码中 8 在顶部，当我第一次删除顶部时，比 11 从右子树成为顶部，如果我删除任何其他节点，代码工作正常，但如果我再次删除顶部(删除后8 现在是 11) 我得到以下错误

Windows has triggered a breakpoint in BinarySearchTreeByList.exe.

This may be due to a corruption of the heap, and indicates a bug in >BinarySearchTreeByList.exe or any of the DLLs it has loaded.

The output window may have more diagnostic information

完整代码如下

#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("\n\n");

    del(&iterate, 8, 't');
    del(&iterate, 22, 't');
    del(&iterate, 7, 't');
    del(&iterate, 11, 't');

    printf("\n\n");
    traverse(iterate);

    cin.clear();
    cin.ignore(255, '\n');
    cin.get(); 

}

谢谢你的帮助

Answer 1

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

例如:

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

你错过了 deleted->right->parent = deleted->parent; 行，我添加了它。 您应该以相同的方式修复代码中的其他几个地方。