從二叉樹刪除錯誤

我寫了一個小代碼來檢測二叉樹中的最大數字，它工作得很好，它的工作很簡單，它遠遠落在最後一個正確的節點（以防萬一），然後我只是cout < <它現在我想刪除它，我查看了一些類似的問題，但我只需要刪除我從搜索中找回的數字，但是我的編程只是在我運行後崩潰列表樹得到數字，刪除並嘗試再次列出它。從二叉樹刪除錯誤

這裏是我的搜索：

T Remove(Node* theRoot) 
     { 
     if (root == NULL) 
     { 
      cout<<"There is no tree"; 
      return -1; 
     } 

     if (theRoot->rChildptr != NULL) 
      return Largest(theRoot->rChildptr); 
     else 
      delete theRoot; 
      return theRoot->data; 

    }

下面是完整的代碼：

#include <iostream> 
#include <string> 
#include <cstdlib> 


using namespace std; 


template<class T> 
class BinaryTree 
{ 

struct Node 
    { 
     T data; 
     Node* lChildptr; 
     Node* rChildptr; 

     Node(T dataNew) 
     { 
      data = dataNew; 
      lChildptr = NULL; 
      rChildptr = NULL; 

     } 
    }; 
private: 
    Node* root; 

     void Insert(T newData, Node* &theRoot) 
     { 
      if(theRoot == NULL) 
      { 
       theRoot = new Node(newData); 
       return; 
      } 

      if(newData < theRoot->data) 
       Insert(newData, theRoot->lChildptr); 
      else 
       Insert(newData, theRoot->rChildptr); 
     } 

     void PrintTree(Node* theRoot) 
     { 
      if(theRoot != NULL) 
      { 
       PrintTree(theRoot->lChildptr); 
       cout<< theRoot->data<<" \n"; 
       PrintTree(theRoot->rChildptr); 
      } 
     } 
     T Largest(Node* theRoot) 
      { 
      if (root == NULL) 
      { 
       cout<<"There is no tree"; 
       return -1; 
      } 

      if (theRoot->rChildptr != NULL) 
       return Largest(theRoot->rChildptr); 
      else 
       delete theRoot; 
       return theRoot->data; 

     } 
     T Remove(Node* theRoot) 
     { 
      if (root == NULL) 
      { 
       cout<<"There is no tree"; 
       return -1; 
      } 

      if (theRoot->rChildptr != NULL) 
       return Largest(theRoot->rChildptr); 
      else 
       delete theRoot; 
       return ; 
     }; 

    public: 
     BinaryTree() 
     { 
      root = NULL; 
     } 

     void AddItem(T newData) 
     { 
      Insert(newData, root); 
     } 

     void PrintTree() 
     { 
      PrintTree(root); 
     } 
     T Largest() 
     { 
      return Largest(root); 
     } 
     //void Remove() 
     //{ 
     // Remove(root); 
     //} 

    }; 

    int main() 
    { 
     BinaryTree<int> *myBT = new BinaryTree<int>(); 
     myBT->AddItem(2); 
     myBT->AddItem(20); 
     myBT->AddItem(5); 
     myBT->AddItem(1); 
     myBT->AddItem(10); 
     myBT->AddItem(15); 
      //for(int i = 0; i < 10; i++)   //randommal tolti fel 
       //myBT->AddItem(rand() % 100); 
     cout << "BinaryTree:" << endl;    //kilistazaa a fat 
     myBT->PrintTree(); 
     cout << "Largest element: " << myBT->Largest() << endl; //visszaadja a legnagyobb elemet 
     //myBT->Remove(); 
     myBT->PrintTree(); 
    }

實際刪除功能是//評論，所以我可以運行在PROG。

來源

2011-11-19 Barta Tamás

什麼刪除在做什麼？你確定你沒有調用空對象上的數據嗎？ –

不知道，但是當我看着藥谷它類似的問題，並在googeld幾乎所有情況下刪除被用來擺脫節點。 –

你看不到？你刪除了根，它指向沒有。 – nullpotent

您不能簡單delete您不想要的對象 - 您還必須刪除您用於的對象找到您正在刪除的節點。而且，如果節點有子節點，則必須將子節點重新連接到樹的其他位置，以便它們保持可達狀態。

這使得它非常棘手的事情是，你必須正確更新：家長對被刪除節點的引用;刪除節點的子節點之一的「子」指針之一;以及來自被刪除節點的兩個子節點的父鏈接。如果您亂序執行更新，您將讀取一個陳舊的指針並可能損壞內存，因此您必須等待刪除節點，直到您不需要節點內的任何更多引用，並且已將引用來自別處的節點。

更新

不要忘了，「最後的右節點」其實可以是你的樹的根：

5是最大的，最右邊的節點你的樹，如果你刪除它，你已經失去了你的整個樹。

除非你正在做的，我們沒有在這裏看到了一些重新平衡;如果你是，請確保您還處理這種情況：

2 
1

我們在Wikipedia朋友們一直非常客氣，分析如何從二叉搜索樹刪除節點：

刪除葉子（無子節點）：刪除葉子很容易，因爲我們可以簡單地將它從樹中移除。

刪除一個節點有一個孩子：刪除節點和其子替換它。

刪除了兩個孩子的節點：呼叫被刪除N.不要刪除N.相反，選擇使用其順序後繼節點或其階前代節點的節點上，R.替換N個與價值R的值，然後刪除R.

你刪除代碼必須處理所有這三種情況。不要忘記，您正在刪除的節點可能是樹的根，並且沒有父節點。

來源

2011-11-19 10:04:43 sarnold

我不認爲我想刪除的節點被認爲有任何子節點導致其最後一個正確的節點。 –

我試圖做一個樹1,2,3,4,5號，然後固定的方式嗶BLOOP建議，仍然會崩潰，而現在當我嘗試列出的第二次，甚至不會給我1號。也許是我把整棵樹都刪掉了，但不知道我必須指出'theRoot'。 –

哦，這個看起來很辛苦，我開始與二叉樹，昨天，想到這一點，但我很喜歡，也許我可以去容易，只是刪除我發現的最大的，但似乎我必須走這，方式。 ..不知道我是否可以這樣做，無論如何謝謝你的答案。 –

你可以發佈整個程序，以便它可以被編譯。但基本上問題是，當Root-> rChildptr爲NULL時，您將刪除根，然後您的返回語句嘗試返回指向無處的Root->數據。

來源

2011-11-19 09:57:45

有完整的代碼 –

您正在刪除theRoot，然後試圖解引用它。如果你想返回存儲在節點中的價值，你需要做一個本地副本第一這樣的：

T value = theRoot->data; 
delete theRoot; 
return value;

是在return thetRoot->data;行意在else語句的一部分？如果是這樣，你需要添加括號這樣的：

if (theRoot->rChildptr != NULL) 
{ 
    return Largest(theRoot->rChildptr); 
} 
else 
{ 
    T value = theRoot->data; 
    delete theRoot; 
    return value; 
}

或者乾脆完全消除其他情況下（因爲你總是返回，如果孩子指針爲空）：

if (theRoot->rChildptr != NULL) 
{ 
    return Largest(theRoot->rChildptr); 
} 

T value = theRoot->data; 
delete theRoot; 
return value;

您還需要以確保父節點不會指向已刪除的子節點（很難看到發生了什麼，因爲您沒有發佈太多的代碼）。

來源

2011-11-19 10:03:45

從二叉樹刪除錯誤

回答

相關問題