用C语言中的数组实现二进制搜索树

Question

我正在尝试使用一维数组实现一个二进制搜索树。我熟悉的事实是，左边的节点将是parent*2+1，右边的节点将为parent*2+2。我用这个概念在这里写插入函数：

int* insert(int tree[], int element){
int parent=0;
if(tree[parent]==''){
tree[parent]=element;
return tree;
}
else{
if(element<tree[parent]){
parent=parent*2+1;
tree[parent]=insert(tree[parent], element);  
}
else{
parent=parent*2+2;
tree[parent]=insert(tree[parent], element);
}
}
return tree;
}

然而，我确信这不会起作用，因为我在递归时将数组的一个元素传递给insert()函数，而它实际上需要一个数组。我不知道该怎么做。我要把返回类型从int*替换成int吗？感谢提供的任何帮助

Answer 1

左侧节点将为父节点2+1，右侧节点将为母节点2+2

没错。你想使用像一样的数组索引

0
/ 
/   
/     
/       
1         2
/        / 
/        /   
3     4   5     6

但是您的递归是而不是。

您总是执行int parent=0;，因此您不知道实际的数组索引，因此，您访问了错误的数组元素。

例如：

当您传递tree[2]时，您确实希望函数在下一个递归调用中使用tree[5]或tree[6]。但是，由于您从将parent设置为零开始，您的下一个递归调用将是tree[3]或tree[4]。

结论如果要使用递归，则需要跟踪当前节点的实际数组索引。简单地将指针传递到当前节点是不够的。

相反，您的代码可能是：

int insert(int* tree, unsigned current_idx, int element){
if (current_idx >= ARRAY_SIZE) return -1;
if(tree[current_idx]==''){
tree[current_idx]=element;
return 0;
}
if(element<tree[current_idx]){
return insert(tree, 2*current_idx + 1, element);  
}
return insert(tree, 2*current_idx + 2, element);  
}

也就是说，您还应该花一些时间考虑递归是否真的是这项任务的好解决方案。

没有递归，你可以做：

int insert(int* tree, int element){
unsigned current_idx = 0;
while (1)
{    
if (current_idx >= ARRAY_SIZE) return -1;
if(tree[current_idx]==''){
tree[current_idx]=element;
return 0;
}
if(element<tree[current_idx]){
current = 2*current_idx + 1;
}
else {
current = 2*current_idx + 2;
}    
}
}

正如你所看到的，递归方法并没有给你任何东西。相反，它让事情变得更糟。。。

Answer 2

您可以避免递归并迭代执行。注意，tree实际上是大小为size的整数数组。在函数insert()中，我们传递一个指向数组的指针。假设使用0s:初始化阵列

void insert(int* tree, int size, int element)
{
if (tree == NULL)
return;

int pos = 0;
while (pos < size)
{
if (tree[pos])
{
if (tree[pos] < element)
pos = 2 * pos + 2;  // right
else if (tree[pos] && tree[pos] > element)
pos = 2 * pos + 1;  // left
}
else
{
tree[pos] = element;
return;
}
}
}

完整代码：

#include <stdio.h>
#include <stdlib.h>
void insert(int* tree, int size, int element)
{
if (tree == NULL)
return;

int pos = 0;
while (pos < size)
{
if (tree[pos])
{
if (tree[pos] < element)
pos = 2 * pos + 2;  // right
else if (tree[pos] && tree[pos] > element)
pos = 2 * pos + 1;  // left
}
else
{
tree[pos] = element;
return;
}
}
}
void print(int* tree, int size)
{
for (int i = 0; i < size; i++)
printf("%d ", tree[i]);
printf("n");
}
int main()
{
int tree[100] = {0};
const int tsize = 100;

// print first 20 elements
print(tree, 20);

insert(tree, tsize, 2);
insert(tree, tsize, 3);
insert(tree, tsize, 5);
insert(tree, tsize, 1);
insert(tree, tsize, 4);

print(tree, 20);

return 0;
}