二进制的分割故障

Question

我正在研究一个程序，该程序通过程序进行搜索，并输出它的数量大于或等于函数参数中指定的值。我已将代码附加在下面，我看到它在发生分割故障之前遍历了两个值。分段故障错误指向返回count + count_values（value，ever） + count_values（value，current）;>

typedef struct BinaryTree {
    int val;
    struct BinaryTree *left;
    struct BinaryTree *right;
} BinaryTree;

BinaryTree *build_tree(int value, BinaryTree *leftnode, BinaryTree *rightnode) {
    BinaryTree *out = calloc(1, sizeof(BinaryTree));
    out->val = value;
    out->leftnode = leftnode;
    out->rightnode = rightnode;

    return out;
}

int count_values(int value, BinaryTree *tree) {
  
    BinaryTree *current = tree;
    BinaryTree *here = current;
    int count = 0;

    if (current != NULL) {
        printf("Value in tree is not NULL\n");

        if (current->val < value) {
            printf("%d < %d\n", current->val, value);
            printf("Count value: %d\n", count);
            here = current->leftnode;
            count_values(value, here);
            current = current->rightnode;
            count_values(value, current);

        } else if (current->val == value) {
            printf("%d = %d\n", current->val, value);
            count++;
            printf("Count value: %d\n", count);
            here = current->leftnode;
            count_values(value, here);
            current = current->rightnode;
            count_values(value, current);
        } else {
            printf("%d > %d\n", current->val, value);
            count++;
            printf("Count value: %d\n", count);
            here = current->leftnode;
            count_values(value, here);
            current = current->rightnode;
            count_values(value, current);
        }
    }
        
    return count + count_values(value, here) + count_values(value, current);
}

int main(void) {
    BinaryTree *tree =
        build_tree(14, build_tree(3, NULL, NULL),
                   build_tree(15, NULL, build_tree(42, NULL, NULL)));

    //path is 14->15->42
    int count = count_values(42, tree);
    printf("should have a count of 1, got %d\n", count);

    count = count_values(14, tree);
    printf("should have a count of 3, got %d\n", count);

    return 0;
}

Answer 1

1. 在中，如果（current-＆gt; val！= null）{ current-＆gt; value永远不可能为null指针，因为值不是指针。只是int。您可能应该检查当前，而不是current-＆gt; val，
2. 即使您更正了该行，您的程序可能会导致堆叠溢出（hehe），因为您无条件地从本身在返回count + count_values（value，there） + count_values（value，current）; line

P.S 中您发布的代码需要进行一些调整才能构建。如果可以的话，请修复

Answer 2

对于初学者，这两个函数中都有错别字，例如

out->leftnode = leftnode;
out->rightnode = rightnode;

，

here = current->leftnode;
current = current->rightnode;

您必须编写

out->left = leftnode;
out->right = rightnode;

here = current->left;
current = current->right;

Count_values 中的函数在此If语句

if (current->val != NULL) {

调用不确定的行为。

首先，这是没有意义的。其次，在访问节点的数据成员之前，您需要检查指针当前（更准确地说，指针tree）是否是空指针。

注意这样的陈述

count_values(value, here);
count_values(value, current);

实际上没有影响。

可以按照以下方式定义递归函数，

size_t count_values( const BinaryTree *tree, int value ) 
{
    return tree == NULL 
        ? 0 
        : ( tree->val >= value ) + count_values( tree->left, value ) + count_values( tree->right, value );
}    

将树指针应为第一个函数参数，并使用限定器const声明，因为该函数不会更改树。并且该函数应返回未签名整数类型的对象，因为计数器不能为负值。代替返回类型size_t您可以使用例如类型无符号int。

这是一个演示程序。

#include <stdio.h>
#include <stdlib.h>

typedef struct BinaryTree {
    int val;
    struct BinaryTree *left;
    struct BinaryTree *right;
} BinaryTree;

BinaryTree *build_tree(int value, BinaryTree *leftnode, BinaryTree *rightnode) {
    BinaryTree *out = calloc(1, sizeof(BinaryTree));
    out->val = value;
    out->left = leftnode;
    out->right = rightnode;

    return out;
}

size_t count_values( const BinaryTree *tree, int value ) 
{
    return tree == NULL 
        ? 0 
        : ( tree->val >= value ) + count_values( tree->left, value ) + count_values( tree->right, value );
} 

int main(void) {
    BinaryTree *tree =
        build_tree(14, build_tree(3, NULL, NULL),
                   build_tree(15, NULL, build_tree(42, NULL, NULL)));

    //path is 14->15->42
    size_t count = count_values( tree, 42);
    printf("should have a count of 1, got %zu\n", count);

    count = count_values(tree, 14 );
    printf("should have a count of 3, got %zu\n", count);

    return 0;
}

它的输出是

should have a count of 1, got 1
should have a count of 3, got 3

Answer 3

您使这种方式比需要更难。

通过测试tree是null，首先测试基本情况。

如果不是，请在左和右节点上重复，并将这些计数添加到当前节点的计数中。

int count_values(int value, BinaryTree *tree) {
    if (tree == NULL) {
        return 0;
    }

    int count = tree->val >= value;
    count += count_values(value, tree->left);
    count += count_values(value, tree->right);

    return count;
}