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即使它被声明指向a 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,因为那些是信息和(当前节点:

        leftChild = nodeFromExpression(expression + 2);

但是我们跳过多少来解析正确的孩子呢？我们需要跳过解析左子时我们使用的所有字符...

        rightChild = nodeFromExpression(expression + ??? 

我们不知道有多少个角色!事实证明,我们不仅需要nodeFromExpression返回它所解析的节点,还需要指出它消耗了多少个字符.所以我们需要更改签名nodeFromExpression以允许它.如果我们在解析时遇到错误怎么办？让我们定义一个结构,它nodeFromExpression可以用来返回它解析的节点,它消耗的字符数,以及它遇到的错误(如果有的话):

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

我们会说如果error是非null,node则为null,并且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和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
    };
}

我已经将所有代码放在这个要点中,以便于复制'''''''''''''''''''

UPDATE

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