Standard binary trees C

Question

Standard binary trees C

I like programming a lot in C.

For several days I tried to create a binary tree from form expressions:

A(B,C(D,$))

Where each letter is nodes.

'(' goes down at the level of my tree (right).

',' goes to the left branch of my tree

'$' inserts a NULL node.

')' means level increase.

This is what I came up with after 2-3 days of coding:

 #define SUCCESS 0 typedef struct BinaryTree { char info; BinaryTree *left,*right,*father; }BinaryTree; int create(BinaryTree*nodeBT, const char *expression) { nodeBT *aux; nodeBT *root; nodeBT *parent; nodeBT=(BinaryTree*) malloc (sizeof(BinaryTree)); nodeBT->info=*expression; nodeBT->right=nodeBT->left=NULL; nodeBT->father = NULL; ++expression; parent=nodeBT; root=nodeBT; while (*expression) {if (isalpha (*expression)) {aux=(BinaryTree*) malloc (sizeof(BinaryTree)); aux->info=*expression; aux->dr=nodeBT->st=NULL; aux->father= parent; nodeBT=aux;} if (*expression== '(') {parent=nodeBT; nodeBT=nodeBT->dr;} if (*expression== ',') {nodeBT=nodeBT->father; nodeBT=nodeBT->dr;} if (*expression== ')') {nodeBT=nodeBT->father; parent= nodeBT->nodeBT;} if (*expression== '$') ++expression; ++expression; } nodeBT=root; return SUCCESS; }

In the end, trying to access the newly created tree, I keep getting "unreadable memory 0xCCCCCC". And I don't have the slightest hint that I'm wrong.

Any idea?

+4

c data-structures binary-tree tree

Shoshinsha purogurama Dec 29 '12 at 20:24

source share

1 answer

rob mayoff · Answer 1 · 2012-12-29T20:56:09+0000

A few problems:

You did not specify a nodeBT type definition for us, but you specified aux , root and parent as pointers to this type.
Then you assign aux to point to BinaryTree , even if you declare it to point to nodeBT .
You assign aux->dr , which is not part of BinaryTree , so I can’t just assume that you typed nodeBT where you meant BinaryTree . You assign nodeBT->st , which is not part of BinaryTree .
You are trying to return the processed tree by assigning nodeBT=root . The problem is that C is a "per value" language. This means that when your create function assigns a value to nodeBT , it only changes the local value of the variable. The create caller does not see this change. Thus, the caller does not receive the root node. This is probably why you get an "unreadable memory" error; the caller accesses some random memory, not memory containing the root node.

Your code will be much easier to understand if you write your parser using a standard technique called "recursive descent." Here is how.

Let him write a function that parses one node from an expression string. Naively, he should have this signature:

 BinaryTree *nodeFromExpression(char const *expression) {

To parse a node, you first need to get the node info :

  char info = expression[0];

Next, we need to see if node has children.

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

If he should have children, we need to take them apart. Here we put the "recursive" into the "recursive descent": we simply call nodeFromExpression again to parse each child. To parse the left child, we need to skip the first two characters in expression , as these were information and ( current node:

  leftChild = nodeFromExpression(expression + 2);

But how much will we miss to analyze the right child? We need to skip all the characters that we used when parsing the left child ...

  rightChild = nodeFromExpression(expression + ???

We do not know how many characters there were! It turns out that we need to make nodeFromExpression return not only to the node that it analyzed, but also some indication of the number of characters it consumes. Therefore, we need to change the signature of nodeFromExpression to allow this. And what if we run into a parsing error? Let it determine the structure that nodeFromExpression can use to return the processed node, the number of characters consumed, and the error it encountered (if it was):

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

We will say that if error not null, then node is null, and offset is the offset in the line where we found the error. Otherwise, offset is located behind the last character consumed to parse the node .

So, starting, we will make nodeFromExpression return a ParseResult . It will take the entire line of the expression as input and accept the offset in the line at which the parsing starts:

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

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

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

I did not mention this for the first time, but we must process your $ token for NULL:

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

Now we can return to the analysis of children.

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

So, to parse the left child, we simply 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 successfully analyzed the left child. Now we need to check and use a 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 correct child:

  ParseResult rightResult = nodeFromExpression(expression, offset);

The error case is now a little more complicated if we do not want a memory leak. We need to free the left child before returning an 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 explicitly check this.

Now we need to check and use ) 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 variables leftChild and rightChild , while the variables leftResult and rightResult are still in scope:

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

We analyzed both children if we need, so now we are ready to build the node that 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: we need to set father pointers for 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 put all the code in that sense to facilitate copying.

UPDATE

If your compiler does not like the syntax (ParseResult){ ... } , you should look for a better compiler. This syntax has been standard since 1999 (§6.5.2.5. Combined literals). Although you are 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); }

Standard binary trees C

UPDATE

More articles: