时间戳

首页 > 解决方案 > 从二叉搜索树中删除具有 2 个子节点的节点

c - 从二叉搜索树中删除具有 2 个子节点的节点

问题描述

我正在开发一个 C 程序，该程序以以下格式扫描学生的记录并将其存储到二叉搜索树中。对于我定义的 BS​​T：

struct student
   int id
   char firstname[20]
   char lastname[20]
   float score
   char zipcode[10]

struct node
   struct student data
   struct node* leftChild
   struct node* rightChild

该程序的功能之一应该能够从树中删除记录。该程序要求用户输入将被删除的学生的姓氏。

下面是遍历BST找到要删除的目标姓氏的方法：

void traverse(node* root, student data)
   if(root != NULL)
      traverse(root->leftChild,data)
      if(strcmp(root->data.lastname,data.lastname) == 0)
         root = delete(root,data)
      traverse(root->rightChild,data)

传递给遍历函数的样本学生结构是：

struct student John
   int id = 1000
   char firstname = John
   char lastname = Adams
   float score = 90.00
   char zipcode = 92121

我与 findmin 一起使用的删除函数，因为我知道我需要在根（目标节点）的右子树中找到最小值才能用它替换目标节点：

struct node* findmin(struct node* root)
    while(root->leftChild != NULL)
      root = root->leftChild
    return root

struct node* delete(node* root, student data)
  if(root == NULL) // check if empty tree
    return root

  // traverse towards left if ID is less
  else if(data.iD < root->data.iD)
    root->leftChild = delete(root->leftChild,data)

  // towards right if greater than ID
  else if(data.iD > root->data.iD)
    root->rightChild = delete(root->rightChild,data)

  /* else would mean target last name found */
  else
    /* if found node has no child */
    if(root->leftChild == NULL && root->rightChild == NULL)
      free(root)
      root = NULL

    // 1 child
    else if(root->leftChild == NULL) // if left child is NULL
      struct node* temp = root
      root = root->rightChild
      free(temp)
      temp = NULL

    else if(root->rightChild == NULL) // if right child is NULL
      struct node* temp = root
      root = root->leftChild
      free(temp) 
      temp = NULL

    // 2 children
    else
      struct node* temp = findmin(root->rightChild)
      root->data = temp->data
      root->rightChild = delete(root->rightChild,temp->data)

  return root;

我希望在这里发生的是，student John它将与 BST 的全局根一起传递到 traverse 中，并且在打印 BST 时，student John将被删除并且不再存在。但是，当我传递包含目标姓氏的学生时，该名称仍将存在于树中。此外，当我测试我的代码并传递要删除的记录时，程序有时不会删除目标节点，而是删除具有最大学生 ID 的节点（树中最右边的节点）和/或会用分段来迎接我故障 11. 我没有看到的代码中是否存在缺陷？如果您需要我提供任何进一步的信息来帮助您帮助我，请告诉我。

标签： cbinary-search-treenodes

解决方案

遍历函数存在第一个问题。当你删除一个节点时，你需要更新指向它的指针。你不跟踪它。

下面是使用指向节点指针策略的遍历和删除函数。如您所见，代码变得更简单。

在这段代码pRoot中是一个指向根指针的指针。然后您可以更新它的值。由于删除，您可以将其设置为 NULL 或另一个节点。

void traverse(node** pRoot, student data){
   if(*pRoot != NULL) {
      traverse(&((*pRoot)->leftChild),data);
      if(strcmp((*pRoot)->data.lastname,data.lastname) == 0)
          delete(pRoot,data);
      traverse(&((*pRoot)->rightChild),data);
}


void delete(node* pRoot, student data)
    if(*pRoot == NULL)
        return;

  node *temp = *pRoot;
  if((*pRoot)->leftChild == NULL)
      *pRoot = (*pRoot)->rightChild;
  else if((*pRoot)->rightChild == NULL){
      *pRoot = (*pRoot)->leftChild;
  else {
      // both children are not NULL :
      // we replace *pRoot with the node with 
      // min ID detached from the rightChild.

      // find node with min ID in right child
      node **pNode = &((*pRoot)->rightChild);
      while((*pNode)->leftChild != NULL)
          pNode = &((*pNode)->leftChild);

      // *pNode is the node with minID
      // its left child is NULL, 
      // but its right child may not be NULL

      // we detach the node with min ID
      node *nNode = *pNode;
      *pNode = nNode->rightChild;

      //replace *pRoot with *nNode
      nNode->rightChild = (*pRoot)->rightChild;
      nNode->leftChild = (*pRoot)->leftChild;
      *pRoot = nNode;
  }
  free(temp);
}

将上述遍历和删除函数合二为一，得到

void delete(node** pRoot, student *data){
   if(*pRoot == NULL)
       return;
   delete(&((*pRoot)->leftChild), data);
   detele(&((*pRoot)->rightChild), data);
   if(strcmp((*pRoot)->data.lastname,data->lastname) != 0)
       return;

   // we delete *pRoot

   node *temp = *pRoot;
   if((*pRoot)->leftChild == NULL)
       *pRoot = (*pRoot)->rightChild;
   else if((*pRoot)->rightChild == NULL){
       *pRoot = (*pRoot)->leftChild;
   else {
       // both children are not NULL :
       // we replace *pRoot with the node with 
       // min ID detached from the rightChild.

       // find node with min ID in right child
       node **pNode = &((*pRoot)->rightChild);
       while((*pNode)->leftChild != NULL)
           pNode = &((*pNode)->leftChild);

       // *pNode is the node with minID
       // its left child is NULL, 
       // but its right child may not be NULL

       // we detach the node with min ID
       node *nNode = *pNode;
       *pNode = nNode->rightChild;

       //replace *pRoot with *nNode
       nNode->rightChild = (*pRoot)->rightChild;
       nNode->leftChild = (*pRoot)->leftChild;
       *pRoot = nNode;
   }
   free(temp);
}

推荐阅读