calgorithmbinary-treeprefix-tree

c recursive binary


I understand the "rules" of inserting

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

}

Solution

  • 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;
            }
        }
    }