c递归二进制

Question

我了解插入的“规则”

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

}

Answer 1

在createExp中，右节点可能是用左节点已经解析的一些字符构建的。每次左节点解析一个以上的字符时都会发生。

为防止这种情况，createExp 应该 return 提供解析结束位置的信息。像这样：

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

如果您需要保留 createExpTree 签名，您可以将递归扁平化为这样的循环：

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

c递归二进制

c recursive binary

c

algorithm

binary-tree

prefix-tree