c recursive binary

Question

I understand the "rules" of inserting

void printTree(BTNode* node) {
    
    if (node == NULL)
        return;
    printTree(node->left);
    printf("%c", node->item);
    printTree(node->right);

}

The signature of createExpTree is wrong. To parse a prefix expression, you need to know where the left operand ends before you start parsing the right operand. Your function doesn't report back the final position of the cursor. — n. m. could be an AI
– n. m. could be an AI, Commented Oct 20, 2020 at 5:20

Joël Hecht · Accepted Answer · 2020-10-21 08:37:13Z

1

in createExp, the right node may be build with some chars already parsed by the left node. It will happened each time the left node parses more than one char.

To prevent this, createExp should return an info to where parsing ends. Something like this :

char *createExpTree(BTNode** root, char* prefix)
{

    if (*prefix) {

       if (!isdigit(*prefix)) {
            *root = malloc(sizeof(BTNode));
            (*root)->item = *prefix;
            (*root)->left = NULL;
            (*root)->right = NULL;

        }
        else {
            *root = malloc(sizeof(BTNode));
            (*root)->item = *prefix;
            (*root)->left = NULL;
            (*root)->right = NULL;
            return prefix;
        }
    }

    prefix = createExpTree(&(*root)->left, ++prefix);
    return createExpTree(&(*root)->right, ++prefix);
}

If you need to keep createExpTree signature, you can flatten the recursion into an loop like that :

void createExpTree(BTNode** root, char* prefix)
{
    BTNode** stack[SIZE];
    int stackPosition = 0;

    while (*prefix) {
        *root = malloc(sizeof(BTNode));
        (*root)->left = NULL;
        (*root)->right = NULL;
        if (isdigit(*prefix)) {
            (*root)->item = *prefix++;
            if (stackPosition == 0) break;
            root = stack[--stackPosition];
        }
        else {
            (*root)->item = *prefix++;
            stack[stackPosition++] = &(*root)->right;
            root = &(*root)->left;
        }
    }
}

edited Oct 21, 2020 at 8:37

answered Oct 20, 2020 at 5:25

Joël Hecht

1,8431 gold badge18 silver badges20 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

relime2543 Over a year ago

Thank you for this. However the signature should not be changed, hence I can't do it your style unfortunately. Do you have any suggestions to do this without changing the signature?

Joël Hecht Over a year ago

You could make the prefix variable global, and pass a dummy second parameter to the createExpTree function to keep the same signature. But many, including me, will see it as a dirty solution...

Joël Hecht Over a year ago

The solution is probably to flatten the recursivity into a loop.

relime2543 Over a year ago

Do you have any hints for me? I switched to recursion because I couldn't do it iteratively. I added Stack Struct to the original post that I may use to help me build the tree

Joël Hecht Over a year ago

Fortunately you have a number digit limitation (200), so you may not need a struct to use a stack and a simple array may be sufficient.

Collectives™ on Stack Overflow

c recursive binary

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related