c - 如何为字符串而不是整数创建二叉搜索树？

Question

我的 C 书中有一段代码解释了 BST 如何适用于整数，但我的作业是关于字符串的 BST。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct node
{
    char data;
    struct node *left;
    struct node *right;
};

struct node *root;
struct node *newnode(char name);
struct node *find(char key);
struct node *insert(char name);
void display(struct node *ptr);
bool rm(char key);
struct node *find_left_most(struct node *rt);
struct node *find_right_most(struct node *rt);

int main(void)
{
    char ch;
    char *a;
    a=malloc(100*sizeof(char));
    struct node *new;
    root=NULL;
    while(1)
    {
        printf("0->EXIT 1->Add name : 2->Search name : ");
        printf("3->Delete name : 4->BST display :\n");

        ch=getch();
        switch(ch)
        {
            case '0':
                    exit(0);
            case '1':
                    printf("name:");
                    scanf("%s",&a);
                    new=insert(a);
                    if (root==NULL) root=new;
                    if(new==NULL)
                        puts("There is no memory available");
                    break;
            case '2':
                    printf("name:");
                    scanf("%s",&a);
                    new=find(a);
                    if(new!=NULL)
                        printf("It has been found\n");
                    else
                        printf("There is no such name\n");
                    break;
            case '3':
                    printf("name:");
                    scanf("%s",&a);
                    rm(a);
                    break;
            case '4':
                    display(root);
                    puts("");
                    break;
            default:
                    puts("Wrong key");
                    break;
        }
    }
    free(a);
    return 0;
}

struct node *newnode(char name)
{
    struct node *neos;
    neos=malloc(sizeof(struct node));
    neos->data = name;
    neos->left = NULL;
    neos->right = NULL;
    return(neos);
}

void display(struct node *ptr)
{
    if (ptr == NULL) return;
    display(ptr->left);
    printf("%s ", ptr->data);
    display(ptr->right);
}

struct node *find(char key)
{
    struct node *current;
    current=root;
    while(current->data != key)
    {
        if(key < current->data)
            current = current->left;
        else
            current = current->right;
        if(current == NULL)
            return NULL;
    }
    return current;
}

struct node *insert(char name)
{
    struct node *next,*current,*ptr;
    bool isleft;
    next=current=root;
    ptr=newnode(name);
    if (root == NULL)
    {
        return ptr;
    }
    while(1)
    {
        if(name < current->data)
        {
            next = current->left;
            isleft=true;
        }
        else
        {
            next = current->right;
            isleft=false;
        }
        if(next == NULL)
        {
            if(isleft)
                current->left=ptr;
            else
                current->right=ptr;
            return ptr;
        }
        current=next;
    }
}

bool rm(char key)
{
    struct node *current;
    struct node *parent;
    bool isLeftChild = true;
    current=parent=root;
    while(current->data != key)
    {
        parent = current;
        if(key < current->data)
        {
            isLeftChild = true;
            current = current->left;
        }
        else
        {
            isLeftChild = false;
            current = current->right;
        }
        if(current == NULL)
            return false;
    }

    if(current->left==NULL && current->right==NULL)
    {
        if(current == root)        
            root = NULL;           
        else if(isLeftChild)
            parent->left = NULL;   
        else                       
            parent->right = NULL;
    }

    else if(current->right==NULL)
        if(current == root)
            root = current->left;
        else if(isLeftChild)
            parent->left = current->left;
        else
            parent->right = current->left;

    else if(current->left==NULL)
        if(current == root)
            root = current->right;
        else if(isLeftChild)
            parent->left = current->right;
        else
            parent->right = current->right;
    else
    {
        struct node *successor,*temp,*old_root;
        if(current == root)
        {
            temp=root->left;
            successor=find_left_most(root->right);
            root=root->right;
            successor->left=temp;
        }

        else if(isLeftChild)
        {
            successor=find_left_most(current->right);
            successor->left=current->left;
            parent->left = current->right;
        }
        else
        {
            successor=find_right_most(current->left);
            successor->right=current->right;
            parent->right = current->left;
        }
    }
    free(current);
    return true;
}

//εντόπισε τον τελευταίο αριστερά κόμβο του υποδένρδου
struct node *find_left_most(struct node *rt)
{
    if(rt==NULL) return NULL;
    while(rt->left!=NULL)
    {
        rt=rt->left;
    }
    return rt;
}

//εντόπισε τον τελευταίο δεξιά κόμβο του υποδένρδου
struct node *find_right_most(struct node *rt)
{
    if(rt==NULL) return NULL;
    while(rt->right!=NULL)
    {
        rt=rt->right;
    }
    return rt;
}

我很确定我搞砸了内存管理，这是当我尝试显示 Tree 时程序崩溃的主要原因。更具体地说，我认为我对待“a”变量的方式是错误的，但我不知道该怎么办......

Answer 1

您需要使用以下结构

//struct for node
struct node {
    char *value;            // all void* types replaced by char*
    struct node *p_left;
    struct node *p_right;
};

下面的插入函数用于比较并在适当的位置添加数据。

//compares value of the new node against the previous node
int CmpStr(const char *a, const char *b)
{
    return (strcmp (a, b));     // string comparison instead of pointer comparison
}

//inserts elements into the tree
void insert(char* key, struct node** leaf, Compare cmp)
{
    int res;
    if( *leaf == NULL ) {
        *leaf = (struct node*) malloc( sizeof( struct node ) );
        (*leaf)->value = malloc( strlen (key) +1 );     // memory for key
        strcpy ((*leaf)->value, key);                   // copy the key
        (*leaf)->p_left = NULL;
        (*leaf)->p_right = NULL;
        //printf(  "\nnew node for %s" , key);
    } else {
        res = cmp (key, (*leaf)->value);
        if( res < 0)
            insert( key, &(*leaf)->p_left, cmp);
        else if( res > 0)
            insert( key, &(*leaf)->p_right, cmp);
        else                                            // key already exists
            printf ("Key '%s' already in tree\n", key);
    }
}

看看here详细代码。