How do I insert characters into a binary tree?

Question

I am making a Morse code decoder in C using a binary tree, I have managed to insert all the characters in an alphabetic order but I want them to be in the order I used in char *characters[] so it would be:

       *      
      / \      
     E   T    
    / \ / \    
   I  A N  M    
     ...
 

how could I insert the characters for the tree to be like this?

    
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" ,"\0"};

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



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

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

    }

    /*inorder(root);*/

    preorder(root);

    /*postorder(root);*/


    return 0;

}

in the end I'd traverse the tree using a dot to move left and a dash to move right, if im not doing it correctly please

Answer 1

Your current code actually uses a lexicographic code on the characters, so you normally obtain a sorted alphabet. If you want to build a binary tree consistant with the morse code of each letter, you must pass the morse code to the insert function and use it.

Here is a possible function:

// 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] = '\0';    // initialize as an empty letter
        root = new_node;

    }

    if (*morse == '\0') {       // 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;
}

Of course, you must call it accordingly:

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

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

}

Answer 2

I would do it slightly differently:

#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 == '\0' ){                                                      
                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;                                                                  
}