如何設置指針無效？

Question

我編寫了一個二叉搜索樹，並創建了一個刪除節點的函數。 通常它有兩個輸入參數，第一個是指向需要刪除的對象的指針，第二個指向二叉搜索樹根。

基本上，我所有的情況下工作，除了「最簡單」的節點是葉。

我的代碼將應該刪除的節點的內容設置爲0，但是仍然有對此的引用，並且它顯示在樹中。

* p是應該被刪除的元素。

* pBaum指向樹的根部。

* p-> right和* p-> left指向* p的右和左子樹。

* p-> conten是* p的值。

我的代碼在葉案：

struct tnode *deletenode(struct tnode *p, struct tnode *pBaum) 
{ 
    if (p !=NULL) 
    { 

     if ((p->left == NULL) && (p->right == NULL)) 
     { 
     printf("%d Ist Blatt \n", p->content); 
     free(p); 
     return pBaum; 
     } 

Basicly我「只」需要告訴指針* P，它從現在起無效。但我無法找到一個合適的解決方案。也許你們可以幫忙。

編輯：好吧，我已經嘗試過，我自己將父指針設置爲NULL。

struct tnode* danglingPointerFix (struct tnode *p, int nodtodelete) 
{ 
if((p->right)->content = nodtodelete) 
    { 
     p->right = NULL; 
     return 0; 
    } 
    if((p->left)->content = nodtodelete) 
    { 
     p->left = NULL; 
     return 0; 
    } 
} 

struct tnode *searchnode(struct tnode *p, int nodtodelete) 
{ 
if (p == NULL) 
{ 
    printf("Baum ist leer oder Element nicht vorhanden \n"); 
    return 0; 
} 
if (p -> content == nodtodelete) 
{ 
    return p; 
} 
if (p->content < nodtodelete) 
{ 
    danglingPointerFix(p, nodtodelete); 
    return searchnode (p->right, nodtodelete); 
} 
if (p->content > nodtodelete) 
{ 
    danglingPointerFix(p, nodtodelete); 
    return searchnode(p->left, nodtodelete); 
} 
} 

但即時segfaulting，也許某處可以看到哪裏，因爲在我看來這個解決方案應該工作。

Answer 1

你必須找到指向你想要刪除的葉父節點。找到後，應將父指針對應的left或right指針設置爲NULL。

所以你刪除應該像：

struct tnode *deletenode(struct tnode *p, struct tnode *pBaum) 
{ 
    if (p !=NULL) 
    { 

     if ((p->left == NULL) && (p->right == NULL)) 
     { 
      // This is a leaf --> It may be deleted 
      deleteNodeInParent(pBaum, p); 

      printf("%d Ist Blatt \n", p->content); 
      free(p); 
      return pBaum; 
     } 

然後，你需要實現deleteNodeInParent。它與您當前的搜索功能非常相似，只不過您會檢查是否left == p或right == p以及 - 如果是 - 將值設置爲NULL並返回。

喜歡的東西：

void deleteNodeInParent(struct tnode *p, struct tnode *pDeleted) 
{ 
    if (p == NULL) 
    { 
     printf("Baum ist leer oder Element nicht vorhanden \n"); 
     return; 
    } 
    if (p->left == pDeleted) 
    { 
     p->left = NULL; 
     return; 
    } 
    if (p->rigth == pDeleted) 
    { 
     p->rigth = NULL; 
     return; 
    } 

    if (p -> content == pDeleted->content) 
    { 
     // Can only happen for head - just return 
     return; 
    } 
    if (p->content < pDeleted->content) 
    { 
     deleteNodeInParent(p->right, pDeleted); 
     return; 
    } 
    if (p->content > pDeleted->content) 
    { 
     deleteNodeInParent(p->left, pDeleted); 
     return; 
    } 
} 

這麼說，我認爲這將是容易得多，如果你擴展了一個指向父結構TNODE。

Answer 2

儘管您已經釋放了葉節點，但父節點仍然保留懸掛指針。解決它的

一種方法是增加以下功能：

struct tnode *deleteLeftNode(struct tnode *parent, struct tnode *pBaum) { 

    if (parent) { 
     deletenode(parent->left, pBaum); 
     parent->left = NULL; 
    } 
    return pBaum; 
} 

struct tnode *deleteRightNode(struct tnode *parent, struct tnode *pBaum) { 

    if (parent) { 
     deletenode(parent->right, pBaum); 
     parent->right = NULL; 
    } 
    return pBaum; 
}