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]);

}