c - 如何在二叉搜索树的节点上插入链表

Question

我想填充一个位于二叉搜索树节点中的链表。如果用户已在列表中退出，请将 ip 添加到该特定用户的链接列表中。

这是我到目前为止尝试过的：

我的数据结构：

typedef struct ip{
    int ip;
    struct ip *ipNext;
}IP;
typedef struct bstNode
{
    char data[32];
    struct bstNode* left;
    struct bstNode* right;
    IP *ipHead; //Pointer to linked list. 
}bstNode;

这就是我遇到问题的地方

我的插入函数将IP地址插入用户的列表中：

bstNode insertIP(bstNode *head, char *username, int ip){
 if (search(username)==1)
    {
        if (head->ipHead == NULL)
    {
        IP *temp; 
        temp = (IP*)malloc(sizeof(IP));
        temp->ip = ip;
        temp->ipNext = NULL;
    }else{
        head->ipHead->ip= ip;
        head->ipHead->ipNext=NULL;
    }
}

插入功能(这有效(：

bstNode *insert(bstNode *node, char *word)
{
    if(node==NULL){
        node= malloc(sizeof(bstNode));
        //IP* ipNode=malloc(sizeof(IP));
        strcpy(node->data, word);
        node->left=NULL;
        node->right=NULL;
    }
    else{
        if(strcmp(word, node->data)<0)
            node->left=insert(node->left, word);
        else if(strcmp(word, node->data)>0)
            node->right=insert(node->right, word);
    }
    return node;
}

搜索功能(有效(：

void search(char* user, bstNode* root)  
{
    int res;
    if( root!= NULL ) {
        res = strcmp(root, root->data);
        if( res < 0)
            search( user, root->left);
        else if( res > 0)
            search( user, root->right);
        else
            printf("User Foundn");   
            return 1;                       
    }
    else printf("nNot in treen");
    return 0;
}

Answer 1

第一个

问题：创建temp时，不会将其分配给head->ipHead。

第二个问题：当ipHead存在时，您仍然需要为新的列表节点分配内存，如果要将其添加到末尾，则必须遍历整个列表。您也可以将其添加到列表的开头。

第三个问题：如果搜索函数找到用户名，它应该返回树中的节点。我猜你不想总是在第一个树节点上添加新的列表节点。我建议您在函数中使用局部变量遍历树 - 而不是递归。

Answer 2

当您发现该用户已经存在于树中时，首先您必须存储包含给定用户的bstNode。之后，您必须遍历该bstNode的链接列表以在最后附加ip。如果链接链接NULL，您的代码还有一个问题。您必须将新节点地址分配给ipHead。目前，您已经创建了一个临时节点，但未将其分配给 head。

Answer 3

最近我编写了一个二叉搜索树，其中每个树节点都托管一个链表(列表节点是单向链接的(，我使用了以下数据结构(如果有人需要整个代码，请告诉我(。

// data in each
// list node
struct data_info
{
    //body of data
};
typedef struct data_info Item;
// list node
typedef struct lnode
{
    Item data_item;
    struct lnode * next;
} Lnode;
// List points to
// first list node
typedef Lnode * List;
// tree node contains
// linked list
typedef struct trnode
{
    List list_item;
    struct trnode * left;   // pointer to right branch
    struct trnode * right;  // pointer to left branch
} Trnode;
// tree of linked lists
typedef struct tree
{
    Trnode * root;          // pointer to root of tree
    int size;               // number of list nodes in tree
} Tree;