c - 递归方法不适用于二叉搜索树
问题描述
我有一个 C 代码模板,我需要完成它以获得二叉搜索树,然后将其改进为 AVL 树。在代码模板中,给了我一些必要函数的声明和struct的定义。但是我在使用 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
因此,如果有人可以花时间阅读这些代码行并帮助我解决这个问题,我将不胜感激。感谢帮助。
解决方案
您return
在avl_insert_recursive
. 这会导致未定义的行为。
推荐阅读
- python - 在python 3中处理mysql结果
- c# - 在控制台窗口中(正确)格式化显示的数据
- python - 如何在 Python 3 中的输入后立即添加字符串?
- python - 为什么我必须单击两次才能滚动?kivy,python中的可滚动标签
- sql - 由于语法错误,无法调用存储过程
- python - 刻度之间的 Matplotlib 绘图市场(X 轴)
- bash - ksh 和 bash 中的环境空间不足我如何查看剩余量
- database - 数据库如何在更快的磁盘上获得更差的基准测试结果?
- r - 将 bookdown 移植到 distill::distill_article 不支持定理环境
- arrays - 这行代码在 Julia 编程语言中是什么意思