c - 在二叉树删除方法中得到奇怪的结果

Question

我重写了我的二叉树实现，它很接近，但是删除子树仍然缺乏完整功能。

移除一棵没有 child 的树根本不起作用。事实上，当调用方法在树中搜索已移除树的实例时，搜索方法会返回 true(即使该树和树中包含的项目在移除方法结束时已被释放)。我无法解决这个问题，即使使用 gdb。

删除只有一个子节点的树是可行的，即使它是根节点。

移除一棵有两个 child 的树只能部分奏效。被移除树的左树，指针，被设置为指向被移除树的指针，该指针被保存在比被移除树更高的树中。但是，被移除的树的权利将丢失。

树.h

/*-------------------------------Tree.h---------------------------------*/ 

#ifndef TREE
#define TREE

#define MAXLEVEL 4
typedef struct cat{
    char *name; 
    int age; 
}Item;

/*User Comparison Function*/ 
typedef int (*comp)(const Item *, const Item *); 

typedef struct tree{
    int branches; 
    Item *item; 
    struct tree *left, *right; 
}Tree; 


Tree *initializeTree(Tree *); 
int isEmpty(Tree *); 
int isFull(Tree *); 
Tree **searchTree(Tree **, Item *, comp); 
int addToTree(Tree **, Item *, comp);
int removeFromTree(Tree **, Item *, comp); 
void printTree(Tree *, int); 
Tree *copyToTree(Item *); 
int returnCount(Tree *); 
#endif

树.c

/*-------------------------------Tree.c---------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include "Tree.h"
#include <math.h>

Tree *initializeTree(Tree *t){
    if((t = malloc(sizeof(Tree))) == NULL)
            return NULL; 

    t->left = t->right = NULL;
    t->item = NULL;
    t->branches = 0;  
    return t;  
}

int isEmpty(Tree *t){
    return (t->branches == 0) ? 1:0; 
}

int isFull(Tree *root){
    return (root->branches == ((int)pow(2, MAXLEVEL)-1)) ? 1:0;
}

Tree *copyToTree(Item *thing){
    Tree *tmp = initializeTree(tmp); 
    tmp->item = thing; 
    return tmp; 
}

Tree **searchTree(Tree **t, Item *thing, comp f){
    int compare; 

    /*t == NULL || ..*/ 
    if((*t) == NULL || (*t)->item == NULL)
        return NULL; 
    if((compare = f((*t)->item, thing)) == 0)
        return t; 
    else if(compare > 0)
        return searchTree((&((*t)->left)), thing, f);
    else
        return searchTree((&((*t)->right)), thing, f); 
}

int returnCount(Tree *t){
    if(t == NULL)
        return; 
    t->branches = 1 + returnCount(t->left); 
    t->branches += returnCount(t->right);
    return t->branches;  
}

int addToTree(Tree **t, Item *thing, comp f){
    if(*t == NULL || (*t)->item == NULL){
        *t = copyToTree(thing);
        if(*t == NULL)
            return 0;  
        return 1; 
    } 

     if(f((*t)->item, thing) >= 0)
        return addToTree(&((*t)->left), thing, f); 
     else
        return addToTree(&((*t)->right), thing, f); 
}

int removeFromTree(Tree **t, Item *thing, comp f){
    Tree **tmp, *tmp2;
    if((tmp = searchTree(t, thing, f)) == NULL)
        return 0;
    tmp2 = *tmp; 

    if((*tmp)->left == NULL ^ (*tmp)->right == NULL)
        ((*tmp)->right == NULL) ? (*tmp = (*tmp)->left):(*tmp = (*tmp)->right);
    else if((*tmp)->left != NULL && (*tmp)->right != NULL){
        (*tmp) = (*tmp)->left;
        /*tmp3 = *tmp;*/
        while((*tmp)->right != NULL)
            (*tmp) = (*tmp)->right; 
        (*tmp) = tmp2->right; 
    }

    free(tmp2->item);
    free(tmp2);
    return 1;   
}

void printTree(Tree *t, int level){
    if(t == NULL || t->item == NULL)
        return; 

    int spaces = 5*(MAXLEVEL - level); 
    printTree(t->left, level+1);
    while(spaces-- > 0)
        putchar(' '); 
    putchar(level + '0');
    putchar('\n');  
    printTree(t->right, level+1); 
}

主.c

/*-------------------------------Main.c---------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "Tree.h"
#define MAXNAME 20
int itemComp(const Item *, const Item *); 
int promptUser(void); 
Item *createUserItem(); 

int main(){
    Tree *userTree = initializeTree(userTree);  
    Item *userItem; 
    int userInput; 

    do{
        userInput = promptUser(); 

        switch(userInput){
            case 1: 
               if((userItem = createUserItem()) && addToTree(&userTree,userItem,itemComp))
                    puts("Cat successfully added!");
               else
                  puts("Could not add cat!");  
               break;
            case 2:
               if(userItem = createUserItem()){
                  if(removeFromTree(&userTree, userItem, itemComp))
                      puts("Cat successfully removed!"); 
               }
               else
                   puts("Could not remove cat!"); 
               break; 
            case 3: 
               if((userItem =createUserItem()) && searchTree(&userTree,userItem,itemComp))
                   puts("Cat found!");
               else
                   puts("Cat not found!"); 
               break; 
            case 4:
               if(isEmpty(userTree))
                   puts("Tree is empty!");
               else
                   puts("Tree is not empty!"); 
               break; 
            case 5:
               if(isFull(userTree))
                   puts("Tree is full!"); 
               else
                   puts("Tree is not full!"); 
               break; 
            case 6:
               printTree(userTree, 1); 
               break; 
            case 0:
               break;
            default:
               puts("Not an option!"); 
               break;
        }

    }while(userInput);

   return 0;  
}

int promptUser(){
    puts("----------Options Menu-----------");
    puts("1. Add Cat"); 
    puts("2. Remove Cat"); 
    puts("3. Search for cat"); 
    puts("4. Check if Empty"); 
    puts("5. Check if Full"); 
    puts("6. Print Tree"); 
    puts("0. Quit"); 

    int userinput = getchar() - '0'; 
    while(getchar() != '\n')
        ;
    return userinput; 
}

Item *createUserItem(){
    static char nameBuf[MAXNAME];

    puts("Enter cat name: "); 
    if(fgets(nameBuf, MAXNAME, stdin) == NULL)
      return NULL; 

    Item *tmp = malloc(sizeof(Item)); 
    if((tmp->name = malloc(strlen(nameBuf))) == NULL)
      return NULL; 

    strcpy(tmp->name, nameBuf);   

    tmp->age = -1; 
    puts("Enter cat age"); 
    scanf("%d", &tmp->age); 
    while(getchar() != '\n')
        ;

    return tmp;
}

int itemComp(const Item *thing_one, const Item *thing_two){
    int comparison;

    if(comparison = strcmp(thing_one->name, thing_two->name)){
        printf("The comparison is [%d]\n", comparison); 
        return comparison; 
    }

    return thing_one->age - thing_two->age; 
}

计划是:

如果它没有 child ，就释放树的内存；

如果当前树有一个子树，则将当前树指向该子树的指针设置为指向当前树的指针，因为指向当前树的指针包含在当前树的父树中。然后释放当前树的内存。

如果当前树有两个 child ，则将当前树的指针设置为左 child 成为指向当前树的指针(由于上述原因)，然后，遍历左侧child 的右指针直到有空位(NULL 指针)。将当前树的右 child 设置为该空缺。

有什么想法吗？

Answer 1

我不得不从头开始重建您的删除节点功能。不幸的是，我认为您在自己实现时没有正确的想法。从树中删除节点是一项很难实现的功能，尤其是在管理内存时(以避免内存泄漏)。

删除节点时的想法是用要删除的节点的左子树中最右边的节点替换它。如果左子树为空，则完全删除当前节点并替换为右子树。

大概是这样的(未测试——只是掌握了这个的一般概念):

// Purpose: Finds the largest node in the given Tree. Once found, 
//          returns the item and destroys the node.
// PRE: t != NULL, *t != NULL
// POST: - returns a pointer to a Item
//       - Side Effect: Frees the largest node in the Tree. Caller must
//                       free the returned Item.
// TIME: O(n), where n is the height of the Tree.
static Item *largestNode( Tree **t ) {
  assert( t != NULL );
  assert( ( *t ) != NULL );

  if ( ( *t )->right == NULL ) {
    Item *key = ( *t )->item;

    free( *t );

    *t = NULL;

    return key;
  } else {
    return largestNode( &( ( *t )->right ) );
  }
}

Tree *removeFromTree( Tree **t, Item *key, comp f ) {
  // Determines whether we are at an empty node (key is not found).
  if ( ( t == NULL ) || ( ( *t ) == NULL ) )
    return NULL;

  // Defines a temporary Tree pointer, tmp and the result from the 
  // compare function.
  Tree *tmp = *t;
  int const result = f( tmp->item, key );

  // Determines if the result of comparing the current node and the key 
  // is less. If so, recurse on the left subtree. If it is more, recurse 
  // on the right subtree, otherwise we found the node that we want to remove, 
  // remove it.
  if ( result < 0 ) {
    tmp->left = removeFromTree( &( tmp->left ), key, f );
  } else if ( result > 0 ) {
    tmp->right = removeFromTree( &( tmp->right ), key, f );
  } else {
    // Checks if left subtree exists. If not, delete the entire current node 
    // and return the right subtree, otherwise the left subtree exists and we 
    // should find the largest node in the left subtree and replace the current 
    // node item with the item from the largest node in the left subtree then 
    // delete the entirety of the largest node in the right subtree.
    if ( tmp->left == NULL ) {
      Tree *tmp_new = tmp->right;

      free( tmp );
      // @TODO: add free for item.

      return tmp_new;
    } else {
      Item *backup = tmp->item;
      tmp->item = largestNode( &( tmp->left ) );

      // @TODO: add free for backup item.

      return tmp;
    }
  }
}