c/c++语言开发共享删除二叉搜索树中的最小值

让我们来看看你的function。

 struct Node *delMin(struct Node **root) 

您将指向节点指针的指针作为参数并返回新头。 这是不必要的。 只有在没有更新的情况下返回头部才有用。 你的指向节点指针的方法迎合了这一点（好吧，它应该，但它没有），因此返回值对于其他信息是免费的。

  struct Node *b4Current; 

在这里，您定义一个未初始化的指针。 您应该将其初始化为NULL以表示当前节点（头部）没有父节点。 否则，指针将是一个可能导致未定义行为的垃圾值。

  while ((current->m_ls) == NULL) { b4Current = current; current = current->m_ls; } 

在这里，你的情况是错误的：只要有一个指针，你想要向左走，但你做了别的事情：如果没有任何地方可以走了！ 当头部有一个左孩子时， current会留在头部。 否则，它将为NULL ，这将在您稍后尝试取消引用时造成严重破坏。

  if ((current->m_rs) == NULL) { b4Current->m_ls = 0; free(current); } else { b4Current->m_ls = current->m_rs; free(current); } 

如果你想的话，if的两个分支真的是一样的。 这有点像说： if (x == 0) y = 0; else y = x; if (x == 0) y = 0; else y = x; 。

但是你需要一个if ，即区分current是否是头部的情况。 在前一种情况下，你应该更新*head ，后一种情况就是你已经写过的。

您还应该注意到无法从空列表中删除节点的情况。

所以：

 void delMin(struct Node **root) { struct Node *current = *root; struct Node *b4Current = NULL; if (current == NULL) return NULL; while (current->m_ls != NULL) { b4Current = current; current = current->m_ls; } if (b4Current == NULL) { *root = current->m_rs; } else { b4Current->m_ls = current->m_rs; } free(current); } 

但是，由于您无论如何都要将指针传递给头节点，因此可以将函数简化为：

 void delMin(struct Node **root) { if (*root == NULL) return; while ((*root)->m_ls != NULL) { root = &(*root)->m_ls; } struct Node *old = *root; (*root) = (*root)->m_rs; free(old); } 

你可能在这里有一些丑陋的(*root) ，但是你不使用很多辅助变量和if语句。 我们的想法是通过迭代指向节点指针的方法来添加一个间接层。 *root扮演你的b4Current和(*root)->m_ls的角色(*root)->m_ls是你current ，除了*root以一个合理的初始值开始，即根节点。

我相信你的问题是在你的while循环条件下。 您希望在current-> m_ls！= NULL时遍历树的左侧，否则您将删除树的整个左侧。