c语言数据结构--图(社交网络)与二叉树查找问题

Question

c语言数据结构--好友推荐算法--图(社交网络)与二叉树查找问题
已经有下列函数及代码，请帮忙完善或者修改一下，来实现以上功能。

#include <stdio.h>
#include <stdlib.h>
typedef struct BiTreeNode
{
    struct BTreeNode* left;  
    struct BTreeNode* right; 
    BTDataType data;              
}BTNode;

typedef struct person_information
{
    char name[20];
    int age;
    char job[20];
    char friends[20];
}temp, person[10];

//创立二叉树
BTNode* CreateBTreeNode(BTDataType x)
{
    BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    node->data = x;
    node->left = NULL;
    node->right = NULL;
    return node;
}
int find(int x)
{
    if(x == a[x])
        return a[x];
    a[x] = find(a[x]);
    return a[x];
}
//判断两棵给定的树是否等价
int equal(tree t1,tree t2)
{
    int k;
    if(t1==NULL&&t2==NULL)
    {
        return TRUE;
    }
     else if(t1!=NULL&&t2==NULL||t1==NULL&&t2!=NULL)

     {
         return FALSE;
     }
     else if(t1->data!=t2->data)
     {
         return FALSE;
     }
     for(k=0;k<m;k++)
     {
         equal(t1->child[k],t2->child[k]);
         if(equal(t1->child[k],t2->child[k])==FALSE)
         {
             return FALSE;
         }
         else
         {
             return TRUE;
         }
     }
}

//实现二叉树t的非递归前序遍历
void preorder1(bintree t)
{
    seqstack s;
    init(&s);
    while(t||!empty(&s))
    {
        if(t)
        {
            printf("%c",t->data);
            push(&s,t);
            t=t->lchild;
        }
        else if(!empty(&s))
        {
            t=pop(&s);
            t=t->rchild;
        }
    }
}

//输出以邻接表为存储结构的无向图的各顶点的度

 void degree(LinkedGraph g)
 {
     int k;
     int n;
     EdgeNode *p;
     for(k=0;k<g.n;k++)
     {
         p=g.adjlist[k].FirstEdge;
         n=0;
         while(p!=NULL)
         {
             n++;
             p=p->next;
         }

         if(k==0)
         {
             printf("%d\n",n);
         }
         else
         {
             printf("%d\n",n);
         }
     }
 }

int a[300];
int main()
{
   int i,j,n,index;
   scanf("%d",&n);
   for(i=0;i<n;i++)
   {
       scanf("%s%d%s", person[i].name, &person[i].age, person[i].job,person[i].friends);
   }
    
   for(i=0;i<n;i++)
   {
       index=i;
       for(j=i+1;j<n;j++)    
       {
           if(person[index].age>person[j].age)
           index=j;
       }
      
       temp=person[index];
       person[index]=person[i];
       person[i]=temp;
   }
   for(i=0;i<n;i++)
   {
       printf("%s %ld %s\n", person[i].name,person[i].age,person[i].job,person[i].friends));
   } 
   int N;
   scanf("%d\n", &N);


   char graph_1[N+1][N+1];
   for(int i=0;i<N;i++)
   {
       a[i]=i;
       scanf("%s",graph_1[i]);
   }
   int graph_2[N][N];
   for(int i = 0;i < N;i++)
       for(int j = 0;j < N;j++)
       {
           graph_2[i][j] = graph_1[i][j]-'0';
           if(graph_2[i][j] == 1)
           {
               if(find(i) != find(j))
                   a[find(i)] = find(j);
           }
       }
   for(int i = 0;i < N;i++)
       for(int j = 0;j < N;j++)
           if(find(i) == find(j))
               graph_2[i][j] = 1;
   for(int i = 0;i < N;i++)
       for(int j = 0;j < N;j++)
           printf("%d",graph_2[i][j]);
       printf("\n");
    }
   return 0;
}

Answer 1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 10

// 定义结构体存储个人信息
typedef struct person_information
{
    char name[20];
    int age;
    char job[20];
    char friends[20];
    char pinyin[20];
} temp, person[MAXN];

// 定义二叉树结构体
typedef struct BiTreeNode
{
    struct BiTreeNode* left;
    struct BiTreeNode* right;
    person data;
} BTNode;

// 创建一个新的二叉树结点
BTNode* CreateBTreeNode(person x)
{
    BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    node->data = x;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 将一个新的结点插入到二叉排序树中
void insertNode(BTNode** root, BTNode* newNode)
{
    // 如果二叉树为空，则直接将新结点作为根结点
    if (*root == NULL)
    {
        *root = newNode;
        return;
    }

    // 当前结点
    BTNode* curr = *root;

    // 循环找到要插入的位置
    while (1)
    {
        // 新结点的拼音首字母小于当前结点的拼音首字母，则将新结点插入到当前结点的左子树
        if (strcmp(newNode->data.pinyin, curr->data.pinyin) < 0)
        {
            // 如果当前结点的左子树为空，则将新结点插入到当前结点的左子树
            if (curr->left == NULL)
            {
                curr->left = newNode;
                break;
            }
            // 否则，继续向左遍历
            else
            {
                curr = curr->left;
            }
        }
        // 新结点的拼音首字母大于当前结点的拼音首字母，则将新结点插入到当前结点的右子树
        else
        {
        // 如果当前结点的右子树为空，则将新结点插入到当前结点的右子树
        if (curr->right == NULL)
        {
        curr->right = newNode;
        break;
        }
        // 否则，继续向右遍历
        else
        {
                curr = curr->right;
        }
        }
}
}

// 在二叉排序树中查找给定姓名的结点
BTNode* searchNode(BTNode* root, char* name)
{
// 如果二叉树为空，则返回NULL
if (root == NULL)
{
return NULL;
}
// 当前结点
BTNode* curr = root;

// 循环查找
while (1)
{
    // 如果当前结点的姓名与查找的姓名相同，则返回当前结点
    if (strcmp(curr->data.name, name) == 0)
    {
        return curr;
    }
    // 如果当前结点的姓名小于查找的姓名，则向右遍历
    else if (strcmp(curr->data.name, name) < 0)
    {
        curr = curr->right;
    }
    // 否则，向左遍历
    else
    {
        curr = curr->left;
    }

    // 如果遍历完了整棵树都没有找到，则返回NULL
    if (curr == NULL)
    {
        return NULL;
    }
}
}
// 查找某个人的所有好友，并将这些好友的信息存储在数组friends中
void findFriends(BTNode* root, char* name, temp* friends)
{
// 先查找该人的结点
BTNode* node = searchNode(root, name);
if (node == NULL)
{
printf("找不到该人！\n");
return;
}
// 将该人的好友列表以逗号分隔的形式存储在字符串数组中
char* friendList[MAXN];
int count = 0;
char* p = strtok(node->data.friends, ",");
while (p != NULL)
{
    friendList[count++] = p;
    p = strtok(NULL, ",");
}

// 遍历该人的好友列表，并在二叉树中查找好友的信息
for (int i = 0; i < count; i++)
{
    BTNode* friendNode= searchNode(root, friendList[i]);
if (friendNode == NULL)
{
printf("找不到%s这个人！\n", friendList[i]);
continue;
}
friends[i] = friendNode->data;
}
}

// 判断两个人是否互为好友
int isFriend(BTNode* root, char* name1, char* name2)
{
// 先查找两个人的结点
BTNode* node1 = searchNode(root, name1);
BTNode* node2 = searchNode(root, name2);
if (node1 == NULL || node2 == NULL)
{
printf("找不到某个人！\n");
return 0;
}
// 将两个人的好友列表以逗号分隔的形式存储在字符串数组中
char* friendList1[MAXN];
int count1 = 0;
char* p = strtok(node1->data.friends, ",");
while (p != NULL)
{
    friendList1[count1++] = p;
    p = strtok(NULL, ",");
}
char* friendList2[MAXN];
int count2 = 0;
p = strtok(node2->data.friends, ",");
while (p != NULL)
{
    friendList2[count2++] = p;
    p = strtok(NULL, ",");
}

// 遍历两个人的好友列表，判断是否有互为好友的
for (int i = 0; i < count1; i++)
{
    for (int j = 0; j < count2; j++)
    {
        if (strcmp(friendList1[i], friendList2[j]) == 0)
        {
            return 1;
        }
    }
}

// 如果两个人的好友列表中都没有对方，则两个人不是好友
return 0;
}

// 根据好友推荐算法推荐新的好友
void recommendFriend(BTNode* root, char* name)
{
// 先查找该人的结点
BTNode* node = searchNode(root, name);
if (node == NULL)
{
printf("找不到该人！\n");
return;
}
// 将该人的好友列表以逗号分隔的形式存储在字符串数组中
char* friendList[MAXN];
int count = 0;
char* p = strtok(node->data.friends, ",");
while (p != NULL)
{
    friendList[count++] = p;
    p = strtok(NULL, ",");
}

// 遍历该人的好友列表，找出和对方互为好友的人
for (int i = 0; i < count; i++)
{
    // 先查找这个好友的结点
    BTNode* friendNode = searchNode(root, friendList[i]);
    if (friendNode == NULL)
    {
        printf("找不到%s这个人！\n", friendList[i]);
        continue;
    }

    // 将这个好友的好友列表以逗号分隔的形式存储在字符串数组中
    char* friendList2[MAXN];
    int count2 = 0;
    p = strtok(friendNode->data.friends, ",");
    while (p != NULL)
    {
        friendList2[count2++] = p;
        p = strtok(NULL, ",");
    }

    // 遍历该好友的好友列表，找出和对方互为好友的人
    for (int j = 0; j < count2; j++)
    {
        if (isFriend(root, name, friendList2[j]) == 0)
        {
            printf("推荐%s加%s为好友！\n", name, friendList2[j]);
        }
    }
}
}

int main()
{
// 创建二叉排序树
BTNode* root = NULL;
insert(root, temp1);
insert(root, temp2);
insert(root, temp3);
insert(root, temp4);
insert(root, temp5);
insert(root, temp6);
insert(root, temp7);
insert(root, temp8);
insert(root, temp9);
insert(root, temp10);
// 测试查找
temp t = search(root, "李四");
printf("%s %d %s %s\n", t.name, t.age, t.job, t.friends);

// 测试推荐好友
recommendFriend(root, "张三");

return 0;
}