使用父指針從二叉搜索樹中刪除節點

Question

我正在研究從二叉搜索樹中刪除具有給定密鑰的節點的算法。到目前爲止，我已經能夠想出下面的代碼：

#include <stdio.h> 
#include <stdlib.h> 
#include <malloc.h> 
#include <time.h> 

typedef int ElType; 

typedef struct Tree { 
    ElType key; 
    struct Tree *left; 
    struct Tree *right; 
    struct Tree *parent; 
} Tree; 

Tree* InsertBST(Tree* t, int k) 
{ 
    if (t == NULL) { 
     Tree* w = (Tree*) malloc(sizeof(Tree)); 
     w->key = k; 
     w->left = NULL; 
     w->right = NULL; 
     w->parent = NULL; 
     return w; 
    } 

    if (k <= t->key) { 
     t->left = InsertBST(t->left, k); 
     t->left->parent = t; 
    } 
    else { 
     t->right = InsertBST(t->right, k); 
     t->right->parent = t; 
    } 

    return t; 
} 

Tree* DeleteMaxOfBST(Tree* t, ElType *deleted_value) 
{ 
    if (t == NULL) { 
     *deleted_value = -1; 
     return NULL; 
    } 

    if (t->right == NULL) { 
     *deleted_value = t->key; 
     Tree* w = t->left; 
     w->parent = t->parent; 
     free(t); 
     return w; 
    } 

    t->right = DeleteMaxOfBST(t->right, deleted_value); 
    return t; 
} 

Tree* DeleteNodeOfBST(Tree* t, int k) 
{ 
    if (t == NULL) return NULL; 

    if (k < t->key) { 
     t->left = DeleteNodeOfBST(t->left, k); 
     return t; 
    } 
    else if (k > t->key) { 
     t->right = DeleteNodeOfBST(t->right, k); 
     return t; 
    } 
    else if (t->left == NULL) { 
     Tree* w = t->right; 
     w->parent = t->parent; 
     free(t); 
     return w; 
    } 
    else { 
     ElType max_left; 
     t->left = DeleteMaxOfBST(t->left, &max_left); 
     t->key = max_left; 
     return t; 
    } 
} 

總的想法是，我想用指針與BST合作，父節點，並能刪除與哪個鍵我的一個節點指定的同時保留BST的結構。

我的代碼適用於某些樹中的某些鍵，但是對於沒有任何明顯模式的其他鍵會崩潰。然後我得到了以下錯誤：

Segmentation fault (core dumped) 

我傾向於認爲我已經搞砸指針指向父節點，但不能完全準確判斷故障。我對C相對來說比較陌生，所以我很感激任何評論，指針是否實際上是這裏的問題，以及如何解決這個問題。

Answer 1

這裏是C程序在二叉搜索樹遞歸插入和刪除源代碼..................

/* C Program for Insertion and Deletion in Binary Search Tree Recursive */ 

#include<stdio.h> 
#include<stdlib.h> 

struct node 
{ 
    struct node *lchild; 
    int info; 
    struct node *rchild; 
}; 

struct node *insert(struct node *ptr, int ikey); 
void display(struct node *ptr,int level); 
struct node *del(struct node *ptr, int dkey); 

int main() 
{ 
    struct node *root=NULL,*ptr; 
    int choice,k; 
    while(1) 
    { 
     printf("\n"); 
     printf("1.Insert\n"); 
     printf("2.Delete\n"); 
     printf("3.Display\n"); 
     printf("4.Quit\n"); 
     printf("\nEnter your choice : "); 
     scanf("%d",&choice); 

     switch(choice) 
     { 
     case 1: 
      printf("Enter the key to be inserted : "); 
      scanf("%d",&k); 
      root = insert(root, k); 
      break; 
     case 2: 
      printf("Enter the key to be deleted : "); 
      scanf("%d",&k); 
      root = del(root,k); 
      break; 
     case 3: 
      display(root,0); 
      break; 
     case 4: 
      exit(1); 
     default: 
      printf("\nWrong choice\n"); 
     }/*End of switch */ 
    }/*End of while */ 

    return 0; 

}/*End of main()*/ 

struct node *insert(struct node *ptr, int ikey) 
{ 
    if(ptr==NULL) 
    { 
     ptr = (struct node *) malloc(sizeof(struct node)); 
     ptr->info = ikey; 
     ptr->lchild = NULL; 
     ptr->rchild = NULL; 
    } 
    else if(ikey < ptr->info) /*Insertion in left subtree*/ 
     ptr->lchild = insert(ptr->lchild, ikey); 
    else if(ikey > ptr->info) /*Insertion in right subtree */ 
     ptr->rchild = insert(ptr->rchild, ikey); 
    else 
     printf("\nDuplicate key\n"); 
    return ptr; 
}/*End of insert()*/ 

void display(struct node *ptr,int level) 
{ 
    int i; 
    if(ptr == NULL)/*Base Case*/ 
     return; 
    else 
    { 
     display(ptr->rchild, level+1); 
     printf("\n"); 
     for (i=0; i<level; i++) 
      printf(" "); 
     printf("%d", ptr->info); 
     display(ptr->lchild, level+1); 
    } 

     printf("\n"); 

}/*End of display()*/ 


struct node *del(struct node *ptr, int dkey) 
{ 
    struct node *tmp, *succ; 

    if(ptr == NULL) 
    { 
     printf("dkey not found\n"); 
     return(ptr); 
    } 
    if(dkey < ptr->info)/*delete from left subtree*/ 
     ptr->lchild = del(ptr->lchild, dkey); 
    else if(dkey > ptr->info)/*delete from right subtree*/ 
     ptr->rchild = del(ptr->rchild, dkey); 
    else 
    { 
     /*key to be deleted is found*/ 
     if(ptr->lchild!=NULL && ptr->rchild!=NULL) /*2 children*/ 
     { 
      succ=ptr->rchild; 
      while(succ->lchild) 
       succ=succ->lchild; 
      ptr->info=succ->info; 
      ptr->rchild = del(ptr->rchild, succ->info); 
     } 
     else 
     { 
      tmp = ptr; 
      if(ptr->lchild != NULL) /*only left child*/ 
       ptr = ptr->lchild; 
      else if(ptr->rchild != NULL) /*only right child*/ 
       ptr = ptr->rchild; 
      else /* no child */ 
       ptr = NULL; 
      free(tmp); 
     } 
    } 
    return ptr; 
}/*End of del()*/ 

希望它可以幫助您。欲瞭解更多詳情，請訪問這裏瞭解更多關於操作二叉搜索樹--->C Program for Insertion and Deletion in Binary Search Tree Recursive

和C Program for binary search tree deletion without recursion

Answer 2

所以，沒有怎麼你的代碼運行它很難說究竟在何處分割故障時發生的任何實例你的程序正在運行。當程序遇到分段錯誤時，意味着程序試圖訪問內存，無論出於何種原因它都無法訪問。這通常意味着你的指針試圖指向他們不應該在內存中的地址。

我的建議是逐步運行代碼，看看問題出在哪裏。或者找到一個調試器，可以顯示您的程序正在使用的內存問題。我知道Valgrind程序存在於Ubuntu和其他Linux最好的機器上，但我不確定其他操作系統可以使用哪些程序。你可以在這裏閱讀關於Valgrind的更多信息：http://valgrind.org/。每當我需要檢查我的程序中潛在的內存處理問題時，我都會使用它。

除此之外，只要密切關注您使用malloc創建的空間以及指針指向的位置即可。確保在刪除給定節點時正確重新連接樹。手動處理記憶可能是一種痛苦，但你會得到它的訣竅。