BST的Seg-Fault remove（）函数

Question

基本上，程序由一个BST类组成，该类指向二叉树的第一个节点，节点也是它们自己的类。

的BST调用这个成员函数：

void remove(const T& x) 
{ 
    removeNode(m_root, x); 
    return; 
} 

这是删除节点的递归部分，它运行到完成：

template <typename T> 
void removeNode(TreeNode<T>* &p, const T& x) 
{ 
    if(p == NULL) 
     return; 

    if(x < p -> m_data) 
     removeNode(p -> m_left, x); 
    else if(x > p -> m_data) 
     removeNode(p -> m_right, x); 

    else 
    { 
     TreeNode<T>* tmp = new TreeNode<T>; 

     if(p -> m_left == NULL) 
     { 
      tmp = p -> m_right; 
      delete p; 
      p = tmp; 
     } 
     else if(p -> m_right == NULL) 
     { 
      tmp = p -> m_left; 
      delete p; 
      p = tmp; 
     } 
     else 
     { 
      tmp = p -> m_right; 
      TreeNode<T>* tmp2 = new TreeNode<T>; 

      while(tmp -> m_left != NULL) 
      { 
       tmp2 = tmp; 
       tmp = tmp -> m_left; 
      } 

      p -> m_data = tmp -> m_data; 

      if(tmp2 != NULL) 
       removeNode(tmp2 -> m_left, tmp -> m_left -> m_data); 
      else 
       removeNode(p -> m_right, p -> m_right -> m_data); 
     } 
    } 

    return; 
} 

我右SEG-断层为删除（）函数返回，我想知道为什么？

Answer 1

用户@WhozCraig在代码中指出，最重要的错误：你分配你从来没有使用对象（永不灭！）：

TreeNode<T>* tmp = new TreeNode<T>; 

TreeNode<T>* tmp2 = new TreeNode<T>; 

后者转让导致病情

if(tmp2 != NULL) 

是总是满意，这可以防止您执行

else 
    removeNode(p -> m_right, ...) 

分支。

编辑

假设你有一个键2，5和7的三节点树让我们表示节点node2，分别node5和node7。假设node5是一个树根。假设还你拔出钥匙5
然后：

• *p == node5;
• 前三个if s不满意，控制权转移到else分支;
• tmp被分配p->m_right即&node7;
• tmp2被分配一个新的'空'对象 - 我们称之为nodeEmpty;
• node7没有孩子，所以tmp->m_left是NULL和while循环跳过没有迭代;
• 赋值指令p->m_data = tmp->m_data导致node5得到密钥7;
• 作为tmp2 == &nodeEmpty不是NULL，你叫
  • removeNode(tmp2 -> m_left, tmp -> m_left -> m_data)

这显然是要自nodeEmpty（？！）的不存在左子树删除的东西，BUT。 ..
但是tmp == &node7在这一点和node7没有孩子，所以tmp->m_left == NULL。因此访问tmp->m_left->m_data会触发内存访问错误，并在递归调用removeNode之前进程崩溃。