如何将字符插入二叉树？

Question

我正在使用二叉树在 C 中制作摩尔斯电码解码器，我设法按字母顺序插入所有字符，但我希望它们按照我在 char *characters[] 中使用的顺序排列，所以它将是：

树的字符怎么插入成这样？

    
typedef struct BTree {

    char value[100];
    struct BTree *dot, *dash;

} BTree, *tree_ptr;

BTree *insert(BTree *root, char morse[200]) {

    int j;

    char *code[100];


    if (root == NULL) {

        BTree *new_node = (BTree*) malloc(sizeof(BTree));
        new_node->dot = NULL;
        new_node->dash = NULL;
        strcpy(new_node ->value, morse);
        root = new_node;

    }

    else if (strcmp(morse, root->value) < 0) {

        root ->dot = insert(root->dot, morse);

    } else if (strcmp(morse, root->value) > 0){

        root ->dash = insert(root->dash, morse);

    } else {


    }

    return root;
}

void inorder ( tree_ptr root )
 {
    if ( root == NULL ){
        return ;
    } else {
        inorder ( root ->dot );
        printf ("%s ", root ->value ) ;
        inorder ( root ->dash ) ;
    }

}
void preorder ( tree_ptr root )
 {
    if ( root == NULL )
    return ;
    printf ("%s ", root ->value ) ;
    preorder ( root ->dot );
    preorder ( root ->dash ) ;
 }

 void postorder ( tree_ptr root )
 {
    if ( root == NULL )
    return ;
    postorder ( root ->dot ) ;
    postorder ( root ->dash ) ;
    printf ("%s ", root ->value ) ;
 }


int main(void) {

    int i;

    BTree *root = NULL;

    char *characters[] = {"E", "T", "I", "A", "N", "M", "S", "U", "R", "W", "D", "K", "G", "O", "H", "V", "F", "L", "P", "J", "B", "X", "C", "Y", "Z", "Q" ,"[=11=]"};

    char *morsecode[] = {".", "-", "..", ".-", "-.", "--","...","..-",".-.",".--", "-..","-.-","--.","--- 
                          ","....","...-","..-.", ".-..",".--.",".---","-...", "-..-","-.-.","-.--","- 
                          -..","--.-", "[=11=]"};



    for (i = 0; strcmp( characters[i], "[=11=]") != 0; i++){

        root = insert(root, characters[i]);

    }

    /*inorder(root);*/

    preorder(root);

    /*postorder(root);*/


    return 0;

}

最后我会用一个点向左移动，一个破折号向右移动来遍历树，如果我做得不正确，请

Answer 1

您当前的代码实际上在字符上使用了字典编码，因此您通常会获得排序的字母表。如果要构建与每个字母的摩尔斯电码一致的二叉树，必须将摩尔斯电码传递给插入函数并使用它。

这是一个可能的函数：

// Insert letter *c (as a C string) having morse code morse into root
BTree *insert(BTree *root, const char *c, const char *morse) {

    if (root == NULL) {    // Node does not exist

        BTree *new_node = (BTree*) malloc(sizeof(BTree));
        new_node->dot = NULL;
        new_node->dash = NULL;
        new_node->value[0] = '[=10=]';    // initialize as an empty letter
        root = new_node;

    }

    if (*morse == '[=10=]') {       // reached the end of the morse code
        strncpy(root->value, c, sizeof (root->value));   // current root receives the letter
    }
    else if (*morse == '.') {   // process for a dot

        root ->dot = insert(root->dot, c, morse + 1);    // step in the morse code

    } else if (*morse == '-') {

        root ->dash = insert(root->dash, c, morse + 1);

    } else {
        fprintf(stderr, "Wrong character in morse: %c\n", *morse);
    }

    return root;
}

当然，你必须相应地调用它：

for (i = 0; strcmp( characters[i], "[=11=]") != 0; i++){

    root = insert(root, characters[i], morsecode[i]);

}

Answer 2

我会略有不同：

#include <stdlib.h>                                                                
#include <stdio.h>                                                                 
#include <assert.h>                                                                
                                                                                   
void * xcalloc(size_t count, size_t size);                                         
                                                                                   
struct btree {                                                                     
        char v;                                                                    
        struct btree *dot, *dash;                                                  
} btree, *tree_ptr;                                                                
                                                                                   
struct btree *                                                                     
insert(struct btree **root, char *morse, char v)                                   
{                                                                                  
        struct btree *b = *root;                                                   
                                                                                   
        if( b == NULL ){                                                           
                b = *root = xcalloc(1, sizeof **root);                             
        }                                                                          
        if( *morse ){                                                              
                assert( morse[0] == '-' || morse[0] == '.' );                      
                b = insert( *morse == '-' ? &(*root)->dash : &(*root)->dot,        
                        morse + 1, v);                                             
        }                                                                          
        if( *morse == '[=10=]' ){                                                      
                b->v = v;                                                          
        }                                                                          
        return b;                                                                  
}                                                                                  
void                                                                               
preorder(struct btree *root)                                                       
{                                                                                  
        if( root ){                                                                
                printf("%c", root->v) ;                                            
                preorder(root->dot);                                               
                preorder(root->dash);                                              
        }                                                                          
}                                                                                  
char *alphamorse[] = {                                                             
        ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", /* A - H */       
        "..", ".---", "-.-", ".-..", "--", "-.", /* I - M */                       
        "---", ".--.", "--.-", ".-.", "...", "-", /* N - T */                      
        "..-", "...-", ".--", "-..-", "-.--", "--.." /* W - Z */                   
};                                                                                 
char *nummorse[]={                                                                 
        "-----", ".----", "..---", "...--", "....-",                               
        ".....", "-....", "--...", "---..", "----."                                
};  

int                                                                                
main(void)                                                                         
{                                                                                  
        int i;                                                                     
        struct btree *root = NULL;                                                 
        /* char characters[] = "ETIANMSURWDKGOHVFLPJBXCYZQ"; */                    
                                                                                   
        insert(&root, alphamorse[4], 'A' + 4);                                     
        for(i = 0; i < 26; i++ ){                                                  
                insert(&root, alphamorse[i], 'A' + i);                             
        }                                                                          
        for(i = 0; i < 10; i++ ){                                                  
                insert(&root, nummorse[i], '0' + i);                               
        }                                                                          
        preorder(root);                                                            
        putchar('\n');                                                             
        return 0;                                                                  
                                                                                   
}                                                                                  
                                                                                   
void *                                                                             
xcalloc(size_t count, size_t size)                                                 
{                                                                                  
        void *r = calloc(count, size);                                             
        if( r == NULL ){                                                           
                perror("calloc");                                                  
                exit(EXIT_FAILURE);                                                
        }                                                                          
        return r;                                                                  
}

如何将字符插入二叉树？

How do I insert characters into a binary tree?

c

binary-tree

morse-code