c - 递归方法不适用于二叉搜索树

Question

我有一个C代码模板，我需要完成它以获得二叉搜索树，然后将其改进为AVL树。在代码模板中，给了我一些必要函数的声明和结构体的定义。但我在 BST 方面遇到了麻烦。

这是代码模板中给我的结构；

typedef struct NODE_s *NODE;
typedef struct NODE_s
{
    NODE right;
    NODE left;
    unsigned long long data;
    int height;
} NODE_t[1];

首先，我尝试编写一个节点初始化函数。简单来说，它接受一个unsigned long long数据作为参数，并用它来初始化一个新的唯一节点，然后返回它。我在这里感到困惑的是内存分配部分中结构体的名称的用法。这是函数；

NODE node_init(unsigned long long data)
{

    NODE newNode = (struct NODE_s*)malloc(sizeof(struct NODE_s));
    newNode->data = data;
    newNode->right = NULL;
    newNode->left = NULL;
    newNode->height = 1; 
    return newNode;

}

此后，我尝试为我的树编写一个递归插入函数。它只需要两个参数。我用注释行展示了我编写这些代码的思路，以便让您清楚地了解。

NODE avl_insert_recursive(NODE node, unsigned long long data){

    if( node == NULL){ // if the node is NULL, then assign the data directly to it.

        return(node_init(data)); // call the node initializer function, initialize a node with the value of data
    }

    if( data < node->data ){ // if the data is smaller than the node's data


        node->left = avl_insert_recursive(node->left, data);


    }else if( data > node->data){ // if the data is bigger than the node's data


        node->right = avl_insert_recursive(node->right, data);


    }else{ // if equality occurs, directly return the node itself.

        return node;
    }

最后，为了测试我的树，我在那里有一个函数。但是，为了简化我的问题，我将选择必要的行；

 NODE node = node_init(NULL); // firstly, initializing an empty node for a recursive tree
 int i = 0;
 unsigned long long number; // The numbers will be stored in it.

 fp = fopen(fname, "r+"); // There will be a .txt consist of unsorted long numbers.

 for(i = 0; i<n; i++){

        fscanf(fp, "%llu\n", &number); // taking numbers line by line
        node = avl_insert_recursive(node,number); // inserting each number to our tree
    }

    fclose(fp);

因此，作为结论，我分享了上面必要的线路和函数，并尝试尽可能地简化它。问题是，这段代码不起作用。名为 avl_insert_recursive 的函数无法递归工作，并且在 2-3 个循环后卡住，因为我使用 printf 语句对其进行了检查。因此，如果有人能花时间阅读这些代码行并帮助我解决这个问题，我将非常感激。感谢您的帮助。

Answer 1

您在 avl_insert_recursive 中的某些路径中缺少 return 语句。这会导致未定义的行为。