字符串c的二叉树 [英] Binary tree for strings c

问题描述

我正在尝试实现一个能够在c中保存字符串的二叉树.在使代码可用于int之后，我尝试对其进行一些更改以处理char数组.现在，我似乎已经完全破坏了代码，不知道怎么做.任何帮助表示赞赏.

I'm trying to implement a binary tree capable of holding strings in c. After having the code to work for ints, I tried altering it slightly to handle char arrays. Now I seem to have totally broke the code and don't know how. Any help appreciated.

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

//struct for node
struct node {
    void *value;
    struct node *p_left;
    struct node *p_right;
};

//use typedef to make calling the compare function easier
typedef int (*Compare)(const void *, const void *);

//inserts elements into the tree
void insert(void* key, struct node** leaf, Compare cmp)
{
    if( *leaf == NULL )
    {
        *leaf = (struct node*) malloc( sizeof( struct node ) );
        (*leaf)->value = key;
        (*leaf)->p_left = NULL;
        (*leaf)->p_right = NULL;
        printf(  "\nnew node " );
    }
    else if( cmp(key, (*leaf)->value) < 0)
    {
        printf(  "\ngoing left " );
        insert( key, &(*leaf)->p_left, cmp);
    }
    else if( cmp(key, (*leaf)->value) > 0)
    {
        printf(  "\ngoing right " );
        insert( key, &(*leaf)->p_right, cmp);
    }
    //else {free(key);}
}

//compares value of the new node against the previous node
int CmpInt(const int *a, const int *b)
{
    if(*a < *b){return -1;}
    else if(*a > *b){return 1;}
    else return 0;
}

char *input( void )
{
    char line[10];
    printf("Please enter a string : ");
    if( fgets( line, sizeof line, stdin ) )
    {
        char *ret;
        ret = line;
        return ret;

    }
    return NULL;
}

//recursive function to print out the tree inorder
void in_order(struct node *root)
{
    if( root != NULL )
    {
        in_order(root->p_left);
        printf("%d ", *(char*)root->value);
        in_order(root->p_right);
    }
}

//searches elements in the tree
void search(void* key, struct node** leaf, Compare cmp)
{
    if( *leaf != NULL )
    {
        if( cmp(key, (*leaf)->value) == 0)
        {
            printf("\n%d found!\n", *(char*)key);
        }
        //else if( cmp(key, (*leaf)->value ) < 0)
        else if( key < (*leaf)->value )
        {
            //printf(  "\nnot here \n" );
            search( key, &(*leaf)->p_left, cmp);
        }
        else if( cmp(key, (*leaf)->value) > 0)
        {
            //printf(  "\nor here \n" );
            search( key, &(*leaf)->p_right, cmp);
        }
    }
    else printf("\nNot in tree\n");
    return;
}

void delete_tree(struct node** leaf)
{
    if( *leaf != NULL )
    {
        delete_tree(&(*leaf)->p_left);
        delete_tree(&(*leaf)->p_right);
        free( (*leaf) );
    }
}

//displays menu for user
void menu()
{
    printf("\nPress 'i' to insert an element\n");
    printf("Press 's' to search for an element\n");
    printf("Press 'p' to print the tree inorder\n");
    printf("Press 'f' to destroy current tree\n");
    printf("Press 'q' to quit\n");
}

int main(void)
{
    struct node *p_root = NULL;
    void *value;
    char option = 'x';

    while( option != 'q' )
    {
        //displays menu for program
        menu();

        //gets the char input to drive menu
        option = getchar();
        getchar();

        if( option == 'i') //if 'i' then get an integer input
        {
            value = input();
            insert(value,  &p_root, (Compare)CmpInt);
        }
        else if( option == 's' ) //if 's' then get input value and call the search function
        {
            value = input();
            search(value, &p_root, (Compare)CmpInt);
        }
        else if( option == 'p' ) //if 'p' then call the print table function
        {
            in_order(p_root);
        }
        else if( option == 'f' ) //if 'f' destroy the tree and initailse new one
        {
            delete_tree(&p_root);
            printf("Tree destroyed");
            p_root = NULL;
        }
        else if( option == 'q' )
        {
            printf("Quitting");
        }
    }

    return 0;
}

推荐答案

OP仅完成了一半的转换为字符串键的工作.我已经评论了更改的地方，但是有两个要点:a)输入字符串是input()函数的局部变量，因此在其他地方不可用，b)将所有void*指针更改为char*，绝对没有理由使用void指针.

OP only did half a job converting to string keys. I have commented where changed, but two main points are a) the input string was local to the input() function and so not available elsewhere, b) changed all the void* pointers to char*, there is absloutely no reason to work with void pointers.

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>

#define MAXLEN 9

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

//use typedef to make calling the compare function easier
typedef int (*Compare)(const char *, const char *);

//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);
    }
}

//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
}

char *input( void )
{
    static char line[MAXLEN+1];       // where to place key    
    printf("Please enter a string : ");
    fgets( line, sizeof line, stdin );
    return ( strtok(line, "\n" ));    // remove trailing newline
}

//recursive function to print out the tree inorder
void in_order(struct node *root)
{
    if( root != NULL ) {
        in_order(root->p_left);
        printf("   %s\n", root->value);     // string type
        in_order(root->p_right);
    }
}

//searches elements in the tree
void search(char* key, struct node* leaf, Compare cmp)  // no need for **
{
    int res;
    if( leaf != NULL ) {
        res = cmp(key, leaf->value);
        if( res < 0)
            search( key, leaf->p_left, cmp);
        else if( res > 0)
            search( key, leaf->p_right, cmp);
        else
            printf("\n'%s' found!\n", key);     // string type
    }
    else printf("\nNot in tree\n");
    return;
}

void delete_tree(struct node** leaf)
{
    if( *leaf != NULL ) {
        delete_tree(&(*leaf)->p_left);
        delete_tree(&(*leaf)->p_right);
        free( (*leaf)->value );         // free the key
        free( (*leaf) );
    }
}

//displays menu for user
void menu()
{
    printf("\nPress 'i' to insert an element\n");
    printf("Press 's' to search for an element\n");
    printf("Press 'p' to print the tree inorder\n");
    printf("Press 'f' to destroy current tree\n");
    printf("Press 'q' to quit\n");
}

int main()
{
    struct node *p_root = NULL;
    char *value;
    char option = 'x';

    while( option != 'q' ) {
        //displays menu for program
        menu();

        //gets the char input to drive menu
        option = getch();           // instead of two getchar() calls

        if( option == 'i') {
            value = input();
            printf ("Inserting %s\n", value);
            insert(value,  &p_root, (Compare)CmpStr);
        }
        else if( option == 's' ) {
            value = input();
            search(value, p_root, (Compare)CmpStr);     // no need for **
        }
        else if( option == 'p' ) {
            in_order(p_root);
        }
        else if( option == 'f' ) {
            delete_tree(&p_root);
            printf("Tree destroyed");
            p_root = NULL;
        }
        else if( option == 'q' ) {
            printf("Quitting");
        }
    }
return 0;

}

这篇关于字符串c的二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！