二进制搜索树 - 访问冲突

Question

该方法发现BST中的最大节点返回其值并删除它。我在prev->rightLink = cur->leftLink;处遇到访问冲突。我对C++相对不熟悉，无法找到原因。

int CTree::popLargest(TreeNode* tr) 
{ 
    int largest; 
    TreeNode* prev = NULL; 
    TreeNode* cur = tr; 

    while (cur->rightLink != NULL) 
    { 
     prev = cur; 
     cur = cur->rightLink; 
     largest = cur->info; 
     //DeleteAttemptTwo(tr, largest);//DeleteItem(largest);  
    } 

    if (cur->leftLink != NULL) 
    { 
     prev->rightLink = cur->leftLink; 
    } 
    else 
    { 
     prev->rightLink = NULL; 
    } 

    return largest; 
} 

Answer 1

这是否和别的没有什么意义 -

if (cur->leftLink != NULL) 
{ 
    prev->rightLink = cur->leftLink; 
} 
else 
{ 
    prev->rightLink = NULL; 
} 

什么你正在尝试做的，可以通过刚刚做 - prev->rightLink = cur->leftLink;

而你这句话让访问冲突的原因是prev没有指向一个有效的节点，这是当它是NULL（如初始化）。

Answer 2

你没有考虑到其中tr无权元素（tr->rightLink = NULL，cur = tr），因此while循环永远不会执行内容的案件。在这种情况下，prev仍然为NULL，这表示您在尝试访问元素prev时尝试取消NULL。

试图取消引用NULL将导致某种访问冲突错误。

Answer 3

在情况下，当树不会有任何权利的孩子，沪指仍将空，而执行

prev->rightLink = cur->leftLink; 

您尝试访问空变量的性质，因此是“访问Voilation”。

Answer 4

原因是prev仍然是NULL。在解引用它时，你应该验证指针是否为NULL。BTW，这个问题很容易通过调试找到。

const int INVALID_VALUE = -1; // change it by yourself. 
int CTree::popLargest(TreeNode* tr) 
{ 
    int largest = INVALID_VALUE; 
    if (tr != NULL) 
    { 
     TreeNode* prev = NULL; 
     TreeNode* cur = tr; 
     while (cur->rightLink != NULL) 
     { 
      prev = cur; 
      cur = cur->rightLink; 
      largest = cur->info; 
      //DeleteAttemptTwo(tr, largest);//DeleteItem(largest);  
     } 
     if (prev != NULL) 
     { 
      if (cur->leftLink != NULL) 
      { 
       prev->rightLink = cur->leftLink; 
      } 
      else 
      { 
       prev->rightLink = NULL; 
      } 
     } 
    } 
    return largest; 
}