-1

尝试为二叉搜索树编写删除函数。我知道要考虑三种可能的情况，但我不确定从哪里开始。

我的麻烦主要源于这样一个事实，即一旦我找到需要删除的节点，我需要将它的 PARENT 节点设置为需要删除的节点之后的节点。我应该使用光标来保持父节点还是什么？

我有一个节点结构：

struct bt_node {
  int data;
  bt_node* left;
  bt_node* right;
};

remove 函数的定义是这样设置的：

void remove(bt_node** top_ref, int data);

谢谢你的帮助！

4

3 回答 3

0

一个巧妙的方法是使用递归。您要求删除函数将对当前节点的引用返回给调用函数。这样您就可以轻松地修改父节点。

以下是一些递归代码供您参考：

结构声明：

 typedef struct node {
    int info;
    struct node* lchild;
    struct node* rchild;
}NODE;


删除代码：

NODE* deleteElem(NODE* root, int elem) {
    NODE* save;
    if(root == NULL) {
        printf("Element not in the tree !\n");
        return;
    }
    if(root->info == elem) {
        if(root->rchild == NULL && root->lchild == NULL) {                  // no child
            free(root);
            return NULL;
        }
        else if(root->rchild == NULL || root->lchild == NULL) {             // one child
            if(root->rchild == NULL) {
                save = root->lchild;
                free(root);
                return save;
            }
            else {
                save = root->rchild;
                free(root);
                return save;
            }
        }
        else {                                                             // two children
            save = findPred(root->lchild);
            root->info = save->info;
            root->lchild = deleteElem(root->lchild, root->info);
            return root;
        }
    }
    else if(root->info < elem) {
        root->rchild = deleteElem(root->rchild, elem);
    }
    else if(root->info > elem) {
        root->lchild = deleteElem(root->lchild, elem);
    }
    return root;
}
NODE* findPred(NODE* root) {
    static NODE* pred;
    if(root == NULL) {
        return pred;
    }
    else {
        pred = root;
        return findPred(root->rchild);
    }
}

PS：抱歉，我刚刚注意到您的函数的原型声明。我希望更改此代码以匹配您的原型声明应该不会太困难。

于 2013-08-08T17:44:43.907 回答
0

简单的方法是扩展搜索代码，以便在您沿着树向下移动时在第二个参考中跟踪“最后一个”父级。这个“扩展”搜索然后返回节点和节点的父节点。

然后，您通过删除功能使用该搜索功能，因此您不必在删除逻辑中做任何花哨的事情。

于 2013-08-08T17:01:45.020 回答
0

你可以试试这个： 

void delete_tree(struct tree **ptr,int item) 
{ 
      struct tree *move,*back,*temp; 

      if(*ptr==NULL) 
      { 
               printf("nEmpty tree..............n"); 
               return; 
      } 
      else 
      { 
               move=*ptr; 
               back=move;

               while(move->info!=item) 
               { 
                         back=move;

                         if(item<move->info) 
                         {
                                   move=move->left; 
                         } 
                         else 
                         { 
                                  move=move->right; 
                         } 
               }

               if(move->left!=NULL&&move->right!=NULL) 
               {

                         temp=move->right;

                         while(temp->left!=NULL) 
                         { 
                                  back=temp; 
                                  temp=temp->left; 
                         }

                         move->info=temp->info; 
                         move=temp; 
               }

               if(move->left==NULL&&move->right==NULL) 
               { 
                         if(back->right==move) 
                         { 
                                  back->right=NULL; 
                         } 
                         else 
                         { 
                                  back->left=NULL; 
                         }

                         free(move); 
                         return; 
               }

               if(move->left==NULL && move->right!=NULL) 
               { 
                         if(back->left==move) 
                         { 
                                  back->left=move->right; 
                         } 
                         else 
                         { 
                                  back->right=move->right; 
                         }

                         free(move); 
                         return; 
               }

               if(move->left!=NULL && move->right==NULL) 
               {
                          if(back->left==move) 
                         { 
                                  back->left=move->left; 
                         } 
                         else 
                         { 
                                  back->right=move->left; 
                         }

                         free(move); 
                         return;
于 2016-04-18T10:37:22.343 回答