Ad

Trying To Make Binary Search Tree, But Program Freezes. Can You Check My Code?

- 1 answer

Is there something in this that I don't understand or is this one of those times that I'm going to need to use the alloc functions from stdlib.h that I have never used before.

struct node {
    int value;
    node* left; 
    node* right; 
    node* parent;
};

This is the code that makes the program crash.

    // Is the value > current node?
    // If it is, then go right,
    // If not then go left.
    // Is there a node forward?
    // If not then create a node with the value.
    node currentNode = rootNode;
    bool newNodeCreated = false;
    while (newNodeCreated == false){

        if (value > currentNode.value){                     // If the value is greater than the currents node. 
            if (currentNode.right != NULL){                     // Check the child on the right. 
                currentNode = *currentNode.right;                   // Set the current node to the child and restart the loop. 
            } else {                                                
                currentNode.right->value = value;                   // Set a new node.
                currentNode.right->parent = &currentNode;

                newNodeCreated = true;                      // End loop. 
            }
        } else {                                            // If the value is less than the current node. 
            if (currentNode.left != NULL){                      // Check the child on the left. 
                currentNode = *currentNode.left;                    // Set the current node to the child and restart the loop. 
            } else {                                                
                currentNode.left->value = value;                    // Set a new node. 
                currentNode.left->parent = &currentNode;

                newNodeCreated = true;                      // End loop. 
            }
        }
    }
    return;
Ad

Answer

When you create a node, the values inside are set to nonsense ("garbage values") until you explicitly set them. C doesn't do any initialization for you, so the values are whatever was in RAM before you ran your code.

So when you check if the left/right children are NULL, they may be NULL if the random value happens to be 0, but they also may not and may just point to a random memory address that may or may not be in your program's address space. Regardless, another node doesn't actually exist there until you make one.

Allocating memory is pretty simple. To make a new node, all you have to do is

node* newNode = malloc(sizeof(node));
if (!newNode) {
    // Your program has run out of memory!
    exit(1);
}

and when you want to remove that node, call free on its pointer.

free(newNode);

Once you've actually allocated memory, you can use that pointer to add the new node to the tree.

// ...
} else {  
    currentNode.right = newNode;                                            
    currentNode.right->value = value;
    currentNode.right->parent = currentNode;
    // Explicitly set right and left on the new node to null
    currentNode.right->right = NULL;
    currentNode.right->left = NULL;

    newNodeCreated = true;
}
// ...

You may want to change currentNode to a node* instead of a node to avoid copying nodes in memory, but that's unrelated to the answer here.

Ad
source: stackoverflow.com
Ad