三进制搜索trie插入函数问题

Question

所以我试着做一个三元搜索。现在，我只处理插入函数。我已经理解了三元搜索的基本思想。我知道一个根节点有3个叶子，如果字符在根之前，它就会在左边，在右边之后，如果它匹配根，它就会在中间的叶子上。因此，我的主要目标是制作一个程序，可以为拼写错误的用户输入的单词提供建议。但现在我只是在做三元搜索。我用trie做了一本字典，用它检查用户输入的单词，以建议下一个最好的选择。但是现在，只是在三进制trie中输入一些字符，当我显示它时，应该按顺序显示它。我不是100%确定我的逻辑关于中间的叶子。现在我的程序，当运行时，给我一些垃圾无限值，不知何故与最后输入的字符有关。我不知道哪里出了问题。谁能指出我犯错的地方吗？还有，你能告诉我，我写的逻辑有没有错？我的意思是，你不必给我代码或任何东西，因为我觉得一旦我明白我哪里出错了，我就有能力自己做，但如果有人能帮我找到我的错误，这将对我帮助很大！

整个代码：

#include <stdio.h>
#include <stdlib.h>  //Because usage of malloc gives warnings without this header
typedef struct tstree
{
    struct tstree *lokid;
    struct tstree *hikid;
    struct tstree *eqkid;
    char letter;
}node;
node *head = NULL;
int count = 0;
int insert(char x, node **head)
{
    if (*head==NULL)            //If it's the first element
    {
        *head = malloc(sizeof(node));   
        (*head)->letter = x;
        count++;            
        (*head)->lokid = (*head)->hikid = (*head)->eqkid = NULL;            //Assign all 3 to null initially
    }
    else if ((*head)->letter == x)          //If equal, insert below
    insert(x , &((*head)->eqkid) );
    else if ((*head)->letter > x)   //If inserted char comes before current val, insert to left
    insert(x,&(*head)->lokid);
    else
    insert(x,&(*head)->hikid);              //Else to the right
    return 0;
}
void display(node *head)
{
    if(head)
    {
        display(head->lokid);               //print in infix order
        printf("%c ",head->letter);
        display(head->hikid);
    }
    //return 0;
}
int main()
{   
    int op;
    char num;
    printf("\nWelcome Fabiz. Hope it meets your expectations!\n");
    while(1)
    {
        printf("\n1. To insert an element\n2. Display the tree\n3. Exit\nOption :");
        scanf("%d",&op);
        switch(op)
        {
            case 1:
            {
                system("clear");
                printf("\nEnter the element : ");
                scanf(" %c",&num);
                insert(num,&head);
                break;
            }
            case 2:
            {
                system("clear");
                if(count == 0)
                printf("\nEmpty tree\n");
                else
                {
                    printf("Display in order..\n");
                    display(head);
                }
                break;
            }
            default: exit(0);
        }
    }
    return 0;
}

我正在使用Geany文本编辑器和Linux Mint。我遇到了一个问题，在编译器中，当我点击display函数时，只会无限地打印我输入的最后一个字符。任何帮助都会很有帮助！谢了！

Answer 1

您的显示功能错误。循环条件从不计算为false：

while(&(*head)->lokid!=NULL && &(*head)->hikid!=NULL)

这不是你想要的。&(*head)->lokid或&(*head)->hikid都不会计算为null。如果head不是null，那么&(*head)->lokid只是与*head在结构tstree中加上lokid的偏移量相同的地址。请注意，您的循环甚至没有可能使条件为false的update语句，也没有任何break-这是注定要失败的。

事实上，你甚至根本不需要循环。要按顺序打印，您只需要以下内容：

void display(node *head) {
    if (head) {
        display(head->lokid);
        printf("%c ", head->letter);
        display(head->hikid);
    }
}

请注意，传递节点**没有任何意义（我将其更改为节点*)，返回值应该是void。

更新

temp = *head = malloc(sizeof(node));

display(head);

调用INSERT时也会发生同样的情况。您不希望从上次添加的节点开始插入新字母，而是希望从根节点开始添加新字母。main()应该具有以下内容：

insert(num, &head);

同时，请注意temp是完全不必要的。你不需要。insert通过引用操作全局head，temp在这里没有用处（实际上它引入了bug）。

在main中改变这两行就足够了，在这里测试一下，它像一个魅力一样工作。