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++二進制搜索樹刪除問題

回答

相關問題