c - 二叉搜索树指针问题

Question

我正在尝试实现一个应该在 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;
}

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

Answer 1

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

您的代码有两个代码无限循环问题。请记住，此代码中没有 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。您只需要两件事:

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 的额外循环。

希望有帮助。