二進制搜索樹後繼函數

Question

我正在一個二叉搜索樹程序，我試圖找到一個節點的後繼給定其數據。我跟隨psuedocode，覺得我正在做的正確，但顯然我不是因爲它不工作。

以下是我有：

ZipInfo * BinarySearchTree::treeSuccessor(string city, string state) 
{ 

ZipInfo *successor = new ZipInfo(city, state); 

ZipInfo *y = successor->getRight(); 
ZipInfo *yx = new ZipInfo(); 
if(successor->getRight() != NULL) 
{ 
    while(y->getLeft() != NULL) 
    { 
     y = y->getLeft(); 
    } 
    return y; 
} 

else 
{ 
    yx = successor->getParent(); 
    while((yx != NULL) && (successor == yx->getRight())) 
    { 
     successor = yx; 
     yx = yx->getParent(); 

    } 
    return yx; 
} 


} 

每個節點擁有它們是城市和國家的數據。因此，如果用戶進入菲尼克斯和亞利桑那州作爲城市和州，該功能應該在BST中找到該節點的後繼者。

Answer 1

代碼似乎預期該行：

ZipInfo *successor = new ZipInfo(city, state); 

會發現指針相匹配的城市和國家數據數據的節點。這不會發生，因爲它會將指針返回到新創建的節點。您需要先找到實際上與數據匹配的現有節點（如果這樣的節點存在）。然後你遍歷從該節點開始的樹。