如何刪除BST C語言中的子樹？

我想讓pop函數刪除節點的節點和子樹。這是我的代碼如何刪除BST C語言中的子樹？

void pop(struct data *node,int num) 
{ 
    if(node) 
    { 
     if(node->num==num) 
     { 
      pop(node->left,num); 
      pop(node->right,num); 
      free(node); 
      node=NULL; 
     } 
     else 
     { 
      if(num> node->num) 
       pop(node->right,num); 
      else if (num< node->num) 
       pop(node->left,num); 
     } 
    } 
} 
void pre(struct data *node) 
{ 
    if(node) 
    { 
     printf("%d ",node->num); 
     pre(node->left); 
     pre(node->right); 
    } 
} 
void main() 
{ 
    push(&root,37); 
    push(&root,20); 
    push(&root,45); 
    push(&root,5); 
    push(&root,15); 
    push(&root,40); 
    push(&root,50); 
    pre(root); 
    pop(root,5); 
    pre(root); 
    getchar(); 
}

在我使用pop之前，Pre函數工作得很好。但是在我使用彈出功能之後，它會中斷。誰能知道錯誤在哪裏？

來源

2012-06-10 greenthunder

在pop，你在做：node=NULL; - 但這隻影響傳遞給函數的指針的副本，而不影響原始樹中的指針。你的樹保留了你現在釋放的數據的指針。下一次你用這個樹做了很多事情時，你會試圖去掉那個指針，然後事情就會崩潰並開始繁榮（至少你希望它們會這樣做 - 更糟糕的是，有時候它們似乎有效）。解決這個問題

一種方法是雙指針傳遞給pop：

void pop(struct data **node, int num) { 

    if ((*node)->num == num) 
     // ... 
     free(*node); 
     *node = NULL; 
    } 
}

現在你改變指針樹而不是改變它的副本收到您的功能。

雖然這仍然不能正常工作 - 您將根據pop(child, num);銷燬當前節點的子樹，但除非它們的num設置爲相同的值，否則它們不會刪除任何內容，只是在樹下行駛，尋找匹配的節點num。

您可能需要一個函數來遍歷樹，找到您關心的節點，然後第二個函數從指定節點開始走樹，並（無條件地）銷燬該節點及其子樹。

來源

2012-06-10 06:57:43

好吧，我會嘗試：D – greenthunder

@greenthunder：按照你的要求編輯它。 –

謝謝老兄，它工作。我想我應該通過你的建議修復我的代碼:) – greenthunder

嗯，你的流行音樂功能應該是這樣的：

struct data* pop(struct data *node,int num) 
{ 
    struct data* temp=null; 
if(node) 
{ 
    if(node->num==num) 
    { 
     if(node->left) 
     pop(node->left,node->left->num); 
     if(node->right) 
     pop(node->right,node->right->num); 
     free(node); 
    } 
    else 
    { 
     if(num> node->num) 
      temp=pop(node->right,num); 
     else if (num< node->num) 
      temp=pop(node->left,num); 

     if(node->right==temp) 
     node->right=null; 
     else if(node->left==temp) 
     node->left=null; 
     return temp; 
    } 
} 
return node; 
}

這將作爲你要廢了樹從它被稱爲根源在哪裏的邏輯，如果所需的節點調出據工作成爲樹的根。

來源

2012-06-10 08:44:50 mawia

如何刪除BST C語言中的子樹？

回答

相關問題