AVL找到接班人

Question

这是我的我的继任者FUNC：

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() 

我的老师给了我们充满了随机数据的文件。我将所有这些数据放入树中，插入方法起作用，但一旦remove方法启动，某个点的后继函数将返回我正在寻找继任者的节点的相同值。这应该无法正确发生？我的继任者功能是否正确？如果你想看到删除方法只是提及它。

Answer 1

您对继任者的定义已经存在缺陷：如果节点没有正确的节点，则继承者是其祖先之一：第一个节点的左子节点或其祖先之一。只有当没有这样的祖先存在时，才有莫继承者。就个人而言，我会返回一个迭代器到节点，否则代码似乎是好的。