C++鏈接的二叉搜索樹（DeleteTree）

我必須使用C++實現一個二叉搜索樹來進行分配。我創建了類，並試圖實現InsertItem，PrintTree，DeleteTree方法類的，我覺得我做的一切都是正確的，但由於某種原因，我的程序總是崩潰:(C++鏈接的二叉搜索樹（DeleteTree）

這裏是我的代碼：

PrintTree方法

template <class TItem> 
void BinarySearchTree<TItem>::PrintTree() 
{ 
    PrintTree(RootNode); 
} 

template <class TItem> 
void BinarySearchTree<TItem>::PrintTree(BinarySearchTreeNode* Node) 
{ 
    if(Node == NULL) 
     return; 

    cout << Node->Data << endl; 
    PrintTree(Node->LeftChild); 
    PrintTree(Node->RightChild); 
}

DeleteTree方法

template <class TItem> 
void BinarySearchTree<TItem>::DeleteTree() 
{ 
    DeleteTree(RootNode); 
} 

template <class TItem> 
void BinarySearchTree<TItem>::DeleteTree(BinarySearchTreeNode* Node) 
{ 
    if(Node == NULL) 
     return; 

    DeleteTree(Node->LeftChild); 
    DeleteTree(Node->RightChild); 

    delete Node; 
}

我的方法的調用序列，直到程序崩潰：

我插入項目F,B,G,A,D,I,C,E,H：正常工作

我打電話PrintTree()：正常工作

我打電話DeleteTree()：正常工作

我再打電話PrintTree()：程序崩潰

出於某種原因，表達if(RootNode == NULL)的DeleteTree()方法被調用後沒有返回true，所以程序嘗試打印的東西，不存在和崩潰。我不知道爲什麼會發生這種情況，我在這裏做錯了什麼？

任何和所有的幫助表示讚賞。

來源

2011-11-07 Saad Imran.

這似乎是一個懸掛的指針：在指針上調用delete p;並不會將它設置爲0.所以最後由'RootNode'指向的內存被最後一次調用delete delete; 。你應該在':: DeleteTree（）' – azf

的末尾添加'RootNode = 0;'嘿，這工作。謝謝！ –

@totem - 這解決了'DeleteTree（）'方法的問題，但是，如果您將不是'RootNode'的特定節點傳遞給'DeleteTree（* Node）' –

調用「delete」不會空指針。你會想做的事：

delete Node; 
Node = nullptr;

編輯：

傳地址的指針，這樣就可以清理懸擺指針，當您去：

void BinarySearchTree<TItem>::DeleteTree(BinarySearchTreeNode *&node);

來源

2011-11-07 22:20:49 Mranz

或'Node = NULL;'如果你沒有C++ 11。 –

不，你不這樣做，因爲這不會在方法外做任何事情;）（這需要一個指針指針） –

@SethCarnegie啊，是的，好點。我非常肯定常見的編譯器支持這個，就像C++ 0x工作草案一樣。無論哪種方式，爲了與你的其他代碼一致NULL可能會更好。 – Mranz

我想刪除功能應被改變爲如下，

template <class TItem> 
void BinarySearchTree<TItem>::DeleteTree(BinarySearchTreeNode** Node) 
{ 
    if((*Node) == NULL) 
     return; 

    DeleteTree(&(*Node)->LeftChild); 
    DeleteTree(&(*Node)->RightChild); 

    delete (*Node); 
    (*Node) = NULL; 
}

請糾正我，如果我WR翁。

來源

2011-11-07 22:28:52 Ajai

這有效，所以我會upvote，但我會接受其他解決方案，只是因爲它對我的口味有點清潔。非常感謝，感謝幫助。 –

請注意，指針在初始回答中仍然沒有被清零 – azf

這仍然是錯誤的，因爲它沒有將'* Node'設置爲'NULL'，並且還因爲'（* Node） - > LeftChild'和' - > RightChild'不是'BinarySearchTreeNode **'（它們只是'BinarySearchTreeNode *'）。你必須傳遞'RightChild'和'LeftChild'的地址。我認爲解決這些問題應該解決這個問題。 –

C++鏈接的二叉搜索樹（DeleteTree）

回答

相關問題