我正在尝试实现一个应该在 leaf 中添加值的函数，这里是我的代码
节点结构: 该节点包含两个 shild，左一个和右一个以及他的 dadi(前驱)和值。
struct arbre {
int val ;
struct arbre * D;
struct arbre * G ;
struct arbre * pere ;
};
这是函数: 该函数总是将值添加到叶子上
void ajout_feuille( struct arbre** arbre , int value )
{
struct arbre* q ,*p ;
if ( *arbre == NULL)
{
q=malloc(sizeof(struct arbre ));
q->D=NULL ;
q->G=NULL;
q->pere=NULL;
q->val=value;
*arbre=q ;
}
else
{
p=*arbre;
while(p!=NULL)
{
if (p->val<value) //if the value is > we go on the right shild;
{
if (p->D==NULL) // if we are on the leaf
{
q=malloc(sizeof(struct arbre ));
q->val=value;
q->D=NULL;
q->G=NULL;
q->pere=p;
p->D=q;
}else
{
p=p->D;
}
}else
{
if (p->val>value)
{
if(p->G==NULL)
{
q=malloc(sizeof(struct arbre ));
q->val=value;
q->D=NULL;
q->G=NULL;
q->pere=p;
p->G=q;
}
}else { p=p->G; }
}
}
}
}
这是显示方法:这是前缀显示方法
void affichage (struct arbre * arbre )
{
if (arbre != NULL){
printf("%d\n",arbre->val);
affichage(arbre->G);
affichage(arbre->D);
}
}
主要方法如下:
int main()
{
struct arbre * A=NULL ;
ajout_feuille(&A,5);
ajout_feuille(&A,4);
affichage(A);
return 0;
}
问题是:显示方法没有显示任何内容，我认为指针有问题。
最佳答案
其中更多的指针和变量并不会使代码更易于阅读。没有打印任何内容的原因是您的枚举循环永远不会终止。
您的代码有两个代码无限循环问题。请记住，此代码中没有 break 语句，因此释放 while 循环的唯一事情是当 p 变为 NULL 时。
- 左侧结束遍历永远不会退出循环
- 重复的条目永远不会退出循环
关于第一个，追逐左侧遍历永远不会将 p 设置为 NULL，原因如下。考虑右侧遍历和左侧遍历之间的差异。
右侧遍历的作用是:
if (p->val<value) //if the value is >, we go on the right child;
{
if (p->D==NULL) // if we are on the leaf
{
q=malloc(sizeof(struct arbre ));
q->val=value;
q->D=NULL;
q->G=NULL;
q->pere=p;
p->D=q;
}
else
{
p=p->D;
}
}
特别注意 else-reaction p=p->D 所涉及的内容。现在看看你的左侧逻辑，它应该是类似的，但是使用相反的逻辑追逐不同的指针(这是一个错误，最终导致重复插入情况下的无限循环问题，但我们将在一会儿):
if (p->val>value) // ok so far
{
if(p->G==NULL)
{
q=malloc(sizeof(struct arbre ));
q->val=value;
q->D=NULL;
q->G=NULL;
q->pere=p;
p->G=q;
}
}
else
{
p=p->G;
}
注意 else 条件现在卡在哪里。首先，这是错误的，其次，if 和 else 确实不应该存在，除非您专门尝试构建一个集合(即没有重复的键)，并且如果这是在这种情况下，您仍然需要一个 exit 子句来打破否则无休止的 while(p!=NULL) 状态。
下面是您的代码的完整功能版本，(a) 不允许重复(您的目标似乎是这样)，并且 (b) 允许重复。然后提供了一个替代方案，我强烈建议您查看。
修复 #1 - 无重复
void ajout_feuille0( struct arbre** arbre , int value )
{
struct arbre* q ,*p ;
if ( *arbre == NULL)
{
q=malloc(sizeof(struct arbre ));
q->D=NULL ;
q->G=NULL;
q->pere=NULL;
q->val=value;
*arbre=q ;
}
else
{
p = *arbre;
while (p!=NULL)
{
if (p->val<value) //if the value is > we go on the right shild;
{
if (p->D==NULL) // if we are on the leaf
{
q=malloc(sizeof(struct arbre ));
q->val=value;
q->D=NULL;
q->G=NULL;
q->pere=p;
p->D=q;
}
else
{
p=p->D;
}
}
else if (value < p->val) // else if less we go down the left side.
{
if(p->G==NULL)
{
q=malloc(sizeof(struct arbre ));
q->val=value;
q->D=NULL;
q->G=NULL;
q->pere=p;
p->G=q;
}
else
{
p=p->G;
}
}
else // else the value is already in the tree.
{
break;
}
}
}
}
修复 #2 - 允许重复
void ajout_feuille0( struct arbre** arbre , int value )
{
struct arbre* q ,*p ;
if ( *arbre == NULL)
{
q=malloc(sizeof(struct arbre ));
q->D=NULL ;
q->G=NULL;
q->pere=NULL;
q->val=value;
*arbre=q ;
}
else
{
p = *arbre;
while (p!=NULL)
{
if (p->val<value) //if the value is > we go on the right shild;
{
if (p->D==NULL) // if we are on the leaf
{
q=malloc(sizeof(struct arbre ));
q->val=value;
q->D=NULL;
q->G=NULL;
q->pere=p;
p->D=q;
}
else
{
p=p->D;
}
}
else
{
if(p->G==NULL)
{
q=malloc(sizeof(struct arbre ));
q->val=value;
q->D=NULL;
q->G=NULL;
q->pere=p;
p->G=q;
}
else
{
p=p->G;
}
}
}
}
}
替代方案
事实是，您不需要 p 和 q。您只需要两件事:
- 给你的指针到指针。我们可以使用它在下降过程中直接寻址每个指针来遍历树。
- 一个单向“父”指针，最初设置为 NULL，并在我们下降下一个子节点之前设置为当前节点指针。
使用这些，您可以更简洁地实现这两种算法(无重复和允许重复):
无重复
void ajout_feuille( struct arbre** tree , int value )
{
struct arbre *pere = NULL;
while (*tree)
{
pere = *tree;
// left side ?
if (value < (*tree)->val)
tree = &(*tree)->G;
// right side ?
else if ((*tree)->val < value)
tree = &(*tree)->D;
else // duplicate found
break;
}
if (!*tree) // null means we have a place to hang a node.
{
*tree = malloc(sizeof **tree);
if (!*tree)
{
perror("Failed to allocate new tree node");
exit(EXIT_FAILURE);
}
(*tree)->val = value;
(*tree)->pere = pere;
(*tree)->G = NULL;
(*tree)->D = NULL;
}
}
允许重复
void ajout_feuille( struct arbre** tree , int value )
{
struct arbre *pere = NULL;
while (*tree)
{
pere = *tree;
// left side ?
if (value < (*tree)->val)
tree = &(*tree)->G;
// els ejust move to right
else tree = &(*tree)->D;
}
if (!*tree) // null means we have a place to hang a node.
{
*tree = malloc(sizeof **tree);
if (!*tree)
{
perror("Failed to allocate new tree node");
exit(EXIT_FAILURE);
}
(*tree)->val = value;
(*tree)->pere = pere;
(*tree)->G = NULL;
(*tree)->D = NULL;
}
}
在这两种情况下，代码都更加简洁，并且避免了外部 while 的额外循环。
希望有帮助。
关于c - 二叉搜索树指针问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/59000988/