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

我是C++新手。我的背景是来自PHP和C＃。我在Visual Studio 2005中使用VC++实现二进制搜索树C++二进制搜索树删除问题

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

建议的策略是

最小的右子树

替换要删除最小

删除最小

在我的代码节点查找8在顶部，当我删除顶部，第一次，比11从右子树成为顶部，如果我删除一个Y以外的节点，代码工作正常，但如果我再删除顶部（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("\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(); 

}

谢谢您的帮助

来源

2014-01-14 Hassan

你确实需要实现它吗？你可以使用'std :: map'或'std :: set'代替吗？ – juanchopanza

无关，你的'typedef struct node'的decl不是函数C++。你声明一个没有正式别名的'typedef'，即它没有声明任何东西。丢失'typedef'如果这是C++（除了'cin'用法在底部，它不是） – WhozCraig

@juanchopanza其实这是实现它的一种要求像这样 – Hassan

你的问题是当你删除一个节点时，你将删除的父节点的子节点指针设置为被删除的节点的子节点，但是你不会将已删除父节点的子节点指针设置为已删除节点的子节点。

例如：

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

你失踪行deleted->right->parent = deleted->parent;，我加入吧。代码中还有几个地方应该以相同的方式修复。

来源

2014-01-14 09:15:16

非常感谢。你的帮助解决了我的问题。 – Hassan

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

当您开始在节点周围摇摆时，您会破坏树，而不会更新'l'和'r'个案中已删除节点的子项的父项。

来源

2014-01-14 08:29:48

谢谢。你的帮助解决了我的问题。 – Hassan

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

回答

相关问题