c - C标准二叉树

我对C编程几乎一无所知。
几天来一直试图从以下形式的表达式创建二叉树：

A(B,C(D,$))

每个字母都是节点。
'('在我的树上下降一层（在右边）。
','转到我树的左侧分支
'$'插入空节点。
')'意味着升一级。
这是我在编码2-3天后想到的：

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

最后，在尝试访问新创建的树时，我一直得到“memory unreadable 0xcccccc”。我一点也不知道哪里做错了。
有什么想法吗？

最佳答案

几个问题：
您还没有向我们显示类型nodeBT的定义，但是您已经声明aux、root和parent是指向该类型的指针。
然后将aux指定为指向BinaryTree，即使它声明为指向nodeBT。
您分配给aux->dr，这不是BinaryTree的一部分，所以我不能假设您在您的意思是nodeBT的地方键入了BinaryTree。您分配给nodeBT->st，这也不是BinaryTree的一部分。
您试图通过分配nodeBT=root来返回解析的树。问题是c是一种“按值调用”语言。这意味着当create函数赋值给nodeBT时，它只改变其局部变量的值。create的调用方没有看到这种变化。所以调用方没有收到根节点。这可能就是为什么会出现“内存不可读”错误；调用方访问的是一些随机内存，而不是包含根节点的内存。
如果您使用一种称为“递归下降”的标准技术编写解析器，那么您的代码实际上会更容易理解。这是怎么回事。
让我们编写一个函数，从表达式字符串中解析一个节点。天真地说，它应该有这样的签名：

BinaryTree *nodeFromExpression(char const *expression) {

要解析节点，首先需要获取节点的info：

    char info = expression[0];

接下来，我们需要看看节点是否应该有子节点。

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

如果它应该有孩子，我们需要分析他们。这就是我们把“递归”放在“递归下降”中的地方：我们只需再次调用nodeFromExpression来解析每个子元素。要解析左边的子节点，我们需要跳过expression中的前两个字符，因为它们是当前节点的info和(：

        leftChild = nodeFromExpression(expression + 2);

但是我们要跳过多少来解析正确的孩子呢？我们需要跳过所有的字符，我们在分析左边的子…

        rightChild = nodeFromExpression(expression + ???

我们不知道那是多少个角色！结果我们需要使nodeFromExpression不仅返回它解析的节点，而且还返回一些它消耗了多少字符的指示。所以我们需要更改nodeFromExpression的签名以允许这样做。如果在解析时遇到错误呢？让我们定义一个nodeFromExpression可以用来返回它解析的节点、它使用的字符数以及它遇到的错误（如果有）的结构：

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

我们会说，如果error是非空的，那么node是空的，offset是字符串中发现错误的偏移量。否则，offset刚好超过解析node所用的最后一个字符。
因此，从头开始，我们将使nodeFromExpression返回一个ParseResult。它将把整个表达式字符串作为输入，并取该字符串中开始解析的偏移量：

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

现在我们有了报告错误的方法，让我们做一些错误检查：

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

我第一次没有提到这一点，但我们应该在这里处理您的$空标记：

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

现在我们可以开始分析孩子们了。

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

所以，为了解析左边的孩子，我们只需再次递归地调用自己。如果递归调用得到错误，则返回相同的结果：

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

好的，我们成功地解析了左边的孩子。现在我们需要检查并使用孩子们之间的逗号：

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

现在我们可以递归调用nodeFromExpression来解析正确的子对象：

        ParseResult rightResult = nodeFromExpression(expression, offset);

如果我们不想泄漏内存，那么现在的错误情况会更复杂一些。在返回错误之前，我们需要释放左孩子：

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

请注意，free如果您传递它，则不会执行任何操作，因此我们不需要显式检查它。
现在我们需要检查并消费孩子们之后的NULL：

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

当)和leftChild变量仍在范围内时，我们需要设置本地rightChild和leftResult变量：

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

如果需要的话，我们已经解析了两个子节点，现在我们可以构造需要返回的节点：

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

我们还有最后一件事要做：我们需要设置孩子们的rightResult指针：

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

最后，我们可以返回一个成功的father：

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

我把所有的代码都放在this gist中，以便复制粘贴。
更新
如果编译器不喜欢ParseResult语法，您应该寻找更好的编译器。该语法自1999年以来一直是标准的（§6.5.2.5复合文字）。当你在寻找一个更好的编译器时，你可以这样处理它。
首先，添加两个静态函数：

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

然后，用对这些函数的调用替换有问题的语法。实例：

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

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