具有插入功能問題的二叉搜索樹

我正在使用遞歸函數將節點插入到二叉搜索樹中。該程序通過創建根節點（如果沒有根節點）來工作。 Root是一個指向節點struct的指針。如果root已經存在，我會調用worker函數。具有插入功能問題的二叉搜索樹

注：鍵是int，Item是一個字符串。

當調用worker函數時，current->key(-858993460)和current->item(Error reading characters of string)不是他們期望的values (1, "Harrold")。

遞歸繼續，直到這個發生異常：

"Exception thrown: read access violation. current was 0xCCCCCCCC."

Key k和Item i是他們的期望值。這只是爲什麼我試圖從Node*訪問他們，他們改變了根，我不確定爲什麼會發生這種情況。

任何幫助表示讚賞

void BST::insert(Key k, Item i) 
{ 
    if (root == nullptr) { 
     root = &Node(k, i); 
    } 
    else insertRec(k, i, root); 
} 

void BST::insertRec(Key k, Item i, Node* current) 
{ 

    if (current->key == k)//if the key of the inserted node is = to an existing key, change the item. 
    { 
     current->item = i; 
    } 
    else if (current->key > k)//if the key of the current node is larger than key inserted traverse leftchild recursively calling function 
    { 
     if (current->leftChild != nullptr) 
      insertRec(k, i, current->leftChild); 
     else 
      current->leftChild = &Node(k, i); 
    } 
    else if (current->key < k) 
    { 
     if (current->rightChild != nullptr) 
      insertRec(k, i, current->rightChild); 
     else 
      current->rightChild = &Node(k, i); 
    } 
}

來源

2017-11-11 JohnDoe

'current-> leftChild =＆Node（k，i）;' - 解釋這個奇怪的線條是幹什麼的。將指針存儲到臨時目錄（註定失敗）的原因是什麼？其次，請發佈[mcve] – PaulMcKenzie

節點是一個結構體。它包含Int鍵，String項，Node * leftChild和Node * rightChild。 struct BST ::節點我在這裏要做的是; 1 - 創建一個新節點。 2-將其創建爲當前節點的右側或左側子節點，以便它具有父節點。 – JohnDoe

你試圖做的是創建一個新的節點？你的書和許多例子展示瞭如何創建新對象？你正在做的是創建一個臨時的。在C++中聽說過'new'，或者更好的是'std :: unique_ptr <>'和'make_unique'？如果不是，那麼在調用'insert'之前，您的整個現有BST不會正確構建。 – PaulMcKenzie

什麼你在樹中創建新的節點現在做的是，你實例化一個臨時Node對象，然後存儲該對象的地址。這就是&Node(k, i)正在做的事情。

問題是臨時將超出範圍，並且您的BST現在包含指向不存在的東西的指針Node。這很可能是您的程序因無效地址錯誤而停止的原因。

所以不是

&Node(k,i)，

使用

new Node(k, i)。

這動態分配一個新的Node，使指向此Node「指針」，而不是暫時的。

當然，當你需要銷燬樹時，你有責任爲BST釋放內存。那時你需要通過樹節點並在每個Node上調用delete。

來源

2017-11-11 12:33:24 PaulMcKenzie

具有插入功能問題的二叉搜索樹

回答

相關問題