数据结构- C标准二叉树

Question

我对C语言编程还是个新手。

几天来一直在尝试从以下形式的表达式创建一个二叉树:

A(B,C(D,$))

每个字母都是节点。

'('在树中向下一级(向右)。

','到达树的左侧分支

'$'插入NULL节点。

')'表示上升一级。

这是我经过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;
}

最后，在尝试访问新创建的树时，我一直得到"内存不可读0xCCCCCC"。而且我也没有发现任何错误的地方。

Answer 1

几个问题:

1. 您没有向我们展示类型nodeBT的定义，但是您已经声明了aux、root和parent是指向该类型的指针。

2. 你然后指定aux指向BinaryTree，即使它被声明为指向nodeBT。

3. 你分配给aux->dr，这不是BinaryTree的一部分，所以我不能只是假设你输入nodeBT，你的意思是BinaryTree。

你分配给nodeBT->st，它也不属于BinaryTree。

4. 您尝试通过分配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++];

我第一次没有提到这一点，但是我们应该在这里处理您的$令牌为NULL:

    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;

OK，我们成功解析了左子节点。现在我们需要检查并使用子元素之间的逗号:

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

注意，如果你传递NULL, free什么也不做，所以我们不需要显式地检查。

现在我们需要检查并使用子节点后面的):

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

我们需要设置本地的leftChild和rightChild变量，而leftResult和rightResult变量仍然在作用域中:

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

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

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

我们还有最后一件事要做:我们需要设置子节点的father指针:

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

最后，我们可以返回一个成功的ParseResult:

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

我已经把所有的代码放在这个要点中，以便于复制和粘贴。

更新

如果你的编译器不喜欢(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);
    }