c++ - AVL 寻找继任者

Question

这是我的继任者功能：

int 
BalancedTree::successor( TreeNode *node ) // successor is the left-most child of its right subtree,
{ 
  TreeNode *tmp = node;
  int successorVal = -1;
  tmp = tmp->m_RChild;

  if( NULL != tmp )
  {
    while( NULL != tmp->m_LChild )
      tmp = tmp->m_LChild;

    // now at left most child of right subtree
    successorVal = tmp->m_nodeData;
  }

  return successorVal;

} // successor()

我的导师给了我们一个充满随机数据的文件。我将所有这些数据放入树中，insert 方法有效，但是一旦 remove 方法启动，后继函数在某个时候返回与我正在寻找后继节点的节点相同的值。这不应该发生正确吗？我的后继功能正确吗？如果您想查看删除方法，只需提及它。

Answer 1

您对后继者的定义已经存在缺陷：如果节点没有右节点，则后继者是其祖先之一：第一个其左孩子是节点或其祖先之一的节点。只有没有这样的祖先存在，才有后继者。就我个人而言，我会将迭代器返回到节点，但否则代码似乎没问题。