BST插入C++

我正在學習C++並編寫一個二叉搜索樹。以下是我爲插入方法編寫的代碼。BST插入C++

BSTNode * BST::Insert(const std::string & v) { 
    BSTNode *n = !root ? root = new BSTNode(v) : Insert_Helper(v,root); 
    if(n) size++; 
    return n; 
} 

BSTNode * BST::Insert_Helper(const std::string & v, BSTNode *n) { 
    if(!n->value.compare(v)) 
     return NULL; // already have v 
    else if(n->value.compare(v) > 0) // v goes to the left 
     if(n->left) return Insert_Helper(v,n->left); 
     else return n->left = new BSTNode(v); 
    else // v goes to the right 
     if(n->right) Insert_Helper(v,n->right); 
     else return n->right = new BSTNode(v); 
}

我得到的錯誤是這樣的：它一切工作正常和丹迪，直到我嘗試插入重複節點。它不會添加新節點，但會增加計數。

通過觀察GDB，我發現當我嘗試添加已有的字符串時，Insert_Helper可正常工作並返回NULL。然而，這個值（在我的機器上）是類似於0x6的東西，當然是超出範圍，但不像我想象的那樣是0x0。我認爲這在我有if（n）語句的地方引發了一個問題。在這種情況下，n的計算結果爲true，因此將大小增加一倍。此外，在我的程序中的這一點，節點繼續正確添加，但我的插入函數繼續返回0x6作爲地址，即使它們確實在我可以訪問的內存中的有效位置。

任何人都可以給我任何指針，我可能會做錯什麼？

來源

2009-10-01 Jarsen

僅供參考，如果你有一個單一的出口和更多的空白，你會有一個更容易的時間。 – 2009-10-01 19:43:07

你的編譯器可能應該看準了這一點，但是這條線附近助手的結尾：

if(n->right) Insert_Helper(v,n->right);

你或許應該返回任何Insert_Helper回報：

if(n->right) return Insert_Helper(v,n->right);

來源

2009-10-01 19:34:37 hrnt

經典。哇。我的一個小時過去了。但是，本來可能會更糟 - 非常感謝。 – Jarsen 2009-10-01 19:37:07

你可以將if(n) size++更改爲if (n != NULL) size++

來源

2009-10-01 19:35:40

這將如何幫助？ – Amok 2009-10-01 19:36:46

它看起來像是評估一樣的東西。不管怎麼說，還是要謝謝你。 – Jarsen 2009-10-01 19:41:47

從原始文章「Insert_Helper ...返回NULL，然而這個值（在我的機器上）是類似於0x6的東西，當然這是超出界限的，但不是像我想象的那樣是0x0。」它看起來像NULL實際上定義爲0，並且Insert_Helper在一個代碼路徑上沒有正確返回。但是，如果NULL不是0，那麼if（n）意味着if（n！= NULL）之外的其他值。 – 2009-10-02 06:22:39

回答

相關問題