C standard binary trees

binary-tree, c, data-structures, tree

Solution

Several problems:

You haven't shown us the definition of type `nodeBT`, but you've declared `aux`, `root`, and `parent` to be pointers to that type.

You then assign `aux` to point to a `BinaryTree` even though it's declared to point to a `nodeBT`.

You assign to `aux->dr`, which isn't part of `BinaryTree`, so I can't just assume you typed `nodeBT` where you meant `BinaryTree`. You assign to `nodeBT->st`, that is not a part of `BinaryTree` either.

You try to return the parsed tree by assigning `nodeBT=root`. The problem is that C is a “call-by-value” language. This implies that when your `create` function assigns to `nodeBT`, it is only changing its local variable's value. The caller of `create` doesn't see that change. So the caller doesn't receive the root node. That's probably why you're getting your “memory unreadable” error; the caller is accessing some random memory, not the memory containing the root node.

Your code will actually be much easier to understand if you write your parser using a standard technique called “recursive descent”. Here's how.

Let's write a function that parses one node from the expression string. Naively, it should have a signature like this:

BinaryTree *nodeFromExpression(char const *expression) {

To parse a node, we first need to get the node's `info`:

    char info = expression[0];

Next, we need to see if the node should have children.

    BinaryTree *leftChild = NULL;
    BinaryTree *rightChild = NULL;
    if (expression[1] == '(') {

If it should have children, we need to parse them. This is where we put the “recursive” in “recursive descent”: we just call `nodeFromExpression` again to parse each child. To parse the left child, we need to skip the first two characters in `expression`, since those were the info and the `(` of the current node:

        leftChild = nodeFromExpression(expression + 2);

But how much do we skip to parse the right child? We need to skip all the characters that we used while parsing the left child…

        rightChild = nodeFromExpression(expression + ??? 

We don't know how many characters that was! It turns out we need to make `nodeFromExpression` return not just the node it parsed, but also some indication of how many characters it consumed. So we need to change the signature of `nodeFromExpression` to allow that. And what if we run into an error while parsing? Let's define a structure that `nodeFromExpression` can use to return the node it parsed, the number of characters it consumed, and the error it encountered (if there was one):

typedef struct {
    BinaryTree *node;
    char const *error;
    int offset;
} ParseResult;

We'll say that if `error` is non-null, then `node` is null and `offset` is the offset in the string where we found the error. Otherwise, `offset` is just past the last character consumed to parse `node`.

So, starting over, we'll make `nodeFromExpression` return a `ParseResult`. It will take the entire expression string as input, and it will take the offset in that string at which to start parsing:

ParseResult nodeFromExpression(char const *expression, int offset) {

Now that we have a way to report errors, let's do some error checking:

    if (!expression[offset]) {
        return (ParseResult){
            .error = "end of string where info expected",
            .offset = offset
        };
    }
    char info = expression[offset++];

I didn't mention this the first time through, but we should handle your `$` token for NULL here:

    if (info == '$') {
        return (ParseResult){  
            .node = NULL,
            .offset = offset   
        };
    }

Now we can get back to parsing the children.

    BinaryTree *leftChild = NULL;
    BinaryTree *rightChild = NULL;
    if (expression[offset] == '(') {

So, to parse the left child, we just call ourselves recursively again. If the recursive call gets an error, we return the same result:

        ParseResult leftResult = nodeFromExpression(expression, offset);
        if (leftResult->error)
            return leftResult;

OK, we parsed the left child successfully. Now we need to check for, and consume, the comma between the children:

        offset = leftResult.offset;
        if (expression[offset] != ',') {
            return (ParseResult){
                .error = "comma expected",
                .offset = offset
            };
        }
        ++offset;

Now we can recursively call `nodeFromExpression` to parse the right child:

        ParseResult rightResult = nodeFromExpression(expression, offset);

The error case now is a bit more complex if we don't want to leak memory. We need to free the left child before returning the error:

        if (rightResult.error) {
            free(leftResult.node);
            return rightResult;
        }

Note that `free` does nothing if you pass it `NULL`, so we don't need to check for that explicitly.

Now we need to check for, and consume, the `)` after the children:

        offset = rightResult.offset;
        if (expression[offset] != ')') {
            free(leftResult.node);
            free(rightResult.node);
            return (ParseResult){
                .error = "right parenthesis expected",
                .offset = offset
            };
        }
        ++offset;

We need to set our local `leftChild` and `rightChild` variables while the `leftResult` and `rightResult` variables are still in scope:

        leftChild = leftResult.node;
        rightChild = rightResult.node;
    }

We've parsed both children, if we needed to, so now we're ready to construct the node we need to return:

    BinaryTree *node = (BinaryTree *)calloc(1, sizeof *node);
    node->info = info;
    node->left = leftChild;
    node->right = rightChild;

We have one last thing to do: we need to set the `father` pointers of the children:

    if (leftChild) {
        leftChild->father = node;
    }
    if (rightChild) {
        rightChild->father = node;
    }

Finally, we can return a successful `ParseResult`:

    return (ParseResult){
        .node = node,
        .offset = offset
    };
}

I've put all the code in this gist for easy copy'n'paste.

UPDATE

If your compiler doesn't like the `(ParseResult){ ... }` syntax, you should look for a better compiler. That syntax has been standard since 1999 (§6.5.2.5 Compound Literals). While you're looking for a better compiler, you can work around it like this.

First, add two static functions:

static ParseResult ParseResultMakeWithNode(BinaryTree *node, int offset) {
    ParseResult result;
    memset(&result, 0, sizeof result);
    result.node = node;
    result.offset = offset;
    return result;
}

static ParseResult ParseResultMakeWithError(char const *error, int offset) {
    ParseResult result;
    memset(&result, 0, sizeof result);
    result.error = error;
    result.offset = offset;
    return result;
}

Then, replace the problematic syntax with calls to these functions. Examples:

    if (!expression[offset]) {
        return ParseResultMakeWithError("end of string where info expected",
            offset);
    }

    if (info == '$') {
        return ParseResultMakeWithNode(NULL, offset);
    }

Problem

Original source