C语言 二叉搜索树指针问题

Question

我正在尝试实现一个应该在叶子中添加值的函数，这里是我的代码

节点结构： 节点包含两个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("%dn",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;
}

问题是：显示方法没有显示任何内容，我认为指针中有问题。

Answer 1

其中更多的指针和变量不会使代码更易于阅读。不打印的原因是枚举循环永远不会终止。

您的代码有两个代码无限循环问题。请记住，此代码中没有break语句，因此释放该 while-loop 的唯一方法是当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;
}
}

具体注意其他反应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 真的不应该首先存在，如果是这种情况，你仍然需要一个退出子句来打破否则无休止的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.您只需要两样东西：

为您提供的指针

1. 指向指针。我们可以使用它来遍历树，通过在下降过程中直接寻址每个指针。
2. 一个单向"父"指针，最初设置为 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 的额外循环。

希望对您有所帮助。