c++ - 二叉搜索树后继函数

Question

我正在研究一个二叉搜索树程序，我正在尝试找到给定数据的节点的后继节点。我正在遵循伪代码并感觉我做的是正确的，但显然我不是因为它不工作。

这是我的:

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;
 }


}

每个节点都包含城市和州的数据。因此，如果用户输入 Phoenix 和 Arizona 作为城市和州，该函数应该在 BST 中找到该节点的后继者。

Answer 1

代码似乎期望该行:

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

将找到指向数据匹配城市和州数据的节点的指针。这不会发生，因为它会将指针返回到新创建的节点。您需要首先找到与数据实际匹配的现有节点(如果存在这样的节点)。然后从该节点开始遍历树。