CODEWITHSUNDEEP
clinuxwindowsdata-structuresbinary-tree
Sinan Pasic
Sinan Pasic

Reputation: 41

Binary tree code works on Linux but not on Windows 10

The code I have works on Linux with no memory errors and the tree builds correctly when run on Linux, but when I run it on Windows with it gets stuck and terminates.

struct node {
    char letter;
    char *string;
    int last_node;
    struct node *left;
    struct node *right;
};

static struct node nodes[] =
{
    {'\0', ""},
    {'E', "."},
    {'T', "-"},
    {'I', ".."},
    {'A', ".-"},
    {'N', "-."},
    {'M', "--"},
    {'S', "..."},
    {'U', "..-"},
    {'R', ".-."},
    {'W', ".--"},
    {'D', "-.."},
    {'K', "-.-"},
    {'G', "--."},
    {'O', "---"},
    {'H', "...."},
    {'V', "...-"},
    {'F', "..-."},
    {'\0', "..--"},
    {'L', ".-.."},
    {'\0', ".-..-"},
    {'P', ".--."},
    {'J', ".---"},
    {'B', "-..."},
    {'X', "-..-"},
    {'C', "-.-."},
    {'Y', "-.--"},
    {'Z', "--.."},
    {'Q', "--.-"},
    {'\0', "---."},
    {'\0', "----"},
    {'5', "....."},
    {'4', "....-"},
    {'\0', "...-."},
    {'3', "...--"},
    {'\0', "..-.."},
    {'\0', "..-.-"},
    {'\0', "..--."},
    {'2', "..---"},
    {'\0', ".-..."},
    {'\0', ".-..-"},
    {'\0', ".-.-."},
    {'\0', ".-.--"},
    {'\0', ".--.."},
    {'\0', ".--.-"},
    {'\0', ".---."},
    {'1', ".----"},
    {'6', "-...."},
    {'\0', "-...-"},
    {'/', "-..-."},
    {'\0', "-..--"},
    {'\0', "-.-.."},
    {'\0', "-.-.-"},
    {'\0', "-.--."},
    {'\0', "-.---"},
    {'7', "--..."},
    {'\0', "--..-"},
    {'\0', "--.-."},
    {'\0', "--.--"},
    {'8', "---.."},
    {'\0', "---.-"},
    {'9', "----."},
    {'0', "-----"},
    {.last_node = 1}
};

struct node *
tree_insert(struct node *root, struct node *selnode_addr, char *string)
{
    if (string[0] == '.')
    {
        if (string[1] == 0)
        {
            return root -> left = selnode_addr;
        }
        return tree_insert(root -> left, selnode_addr, string + 1);
    }

    if (string[1] == 0)
    {
        return root -> right = selnode_addr;
    }
    return tree_insert(root -> right, selnode_addr, string + 1);
}

int
main(void)
{
    // constructs the binary tree.
    for (struct node *nodeptr = nodes + 1; !nodeptr -> last_node; nodeptr++)
    {
        tree_insert(nodes, nodeptr, nodeptr -> string);
    }

    puts("test");
    return 0;
}

On Linux it runs and prints 'test' and passes valgrind with no memory errors and I've verified in GDB that the tree builds correctly, but on Windows it hangs for a short time and then seemingly crashes. I have no idea why.

Updates

New array:

static struct node nodes[] =
{
    {'\0', ""},
    {'E', "."},
    {'T', "-"},
    {'I', ".."},
    {'A', ".-"},
    {'N', "-."},
    {'M', "--"},
    {'S', "..."},
    {'U', "..-"},
    {'R', ".-."},
    {'W', ".--"},
    {'D', "-.."},
    {'K', "-.-"},
    {'G', "--."},
    {'O', "---"},
    {'H', "...."},
    {'V', "...-"},
    {'F', "..-."},
    {'\0', "..--"},
    {'L', ".-.."},
    {'P', ".--."},
    {'J', ".---"},
    {'B', "-..."},
    {'X', "-..-"},
    {'C', "-.-."},
    {'Y', "-.--"},
    {'Z', "--.."},
    {'Q', "--.-"},
    {'\0', "---."},
    {'\0', "----"},
    {'5', "....."},
    {'4', "....-"},
    {'3', "...--"},
    {'2', "..---"},
    {'1', ".----"},
    {'6', "-...."},
    {'/', "-..-."},
    {'7', "--..."},
    {'8', "---.."},
    {'9', "----."},
    {'0', "-----"},
    {.last_node = 1}
};

Upvotes: 2

Views: 103

Answers (1)

interjay
interjay

Reputation: 110146

When inserting a string to the tree, your code assumes that every prefix of that string has already been inserted. This mostly works because the strings are sorted by length.

However, the strings .-.-. and .-.-- are inserted to the tree while their prefix .-.- is never inserted. This causes a recursive call to tree_insert with root == NULL. I'm surprised this doesn't crash for you on Linux, as it did for me.

In your fixed code you removed the .-.-. and .-.-- strings so it works.

Upvotes: 1

Related Questions