从森林中建造一棵n-ary树

Question

我让我的教授给我另一个学期的旧作业。它是关于建立一个家谱，然后找到两个节点之间的亲缘关系。家谱是关于namekians（龙珠z）所以每个namekian都有一个父亲。

问题是输入它是这样的：

First name is the parent  Second name is the child
Iolin                     Lyre
Iolin                     Piyano
Batu                      Iolin
Batu                      Okiat
Ollusc                    Xylo
Organa                    Murd
Piccoro                   Ollusc
Piccoro                   Rombone
Rombone                   Organa

所以我必须拥有两棵树，其中一棵是Piccoro作为领导者（他总是一棵树的领导者），另一棵是未知的领导者。

问题是，当我尝试创建树时，我遇到了麻烦，我知道我有两个根，但正如你所看到的那样，输入不是那样，在我阅读并创建其父节点之前，没有父节点的节点。例如，我创建了Ollusc及其子Xylo，然后是Organa和Murd，但我只有一个根来代表那棵树（我也不知道它们是否在同一棵树中）所以我不知道如何“保存“稍后连接它们的那些节点，与Organa和Rombone同样发生，Organa将在某处，直到我创建Rombone然后将他与Organa联系起来。

   Batu------>NULL
   /     \
 Iolin--->Okiat->NULL
  /   \
Lyre-->Piyano->NULL

   Piccoro-----> NULL
   /       \
 Ollusc--->Rombone->NULL
 /          /
Xylo->NULL Organa->NULL
           /
          Murd->NULL

我考虑过将节点保存到队列或者堆栈中，因为我不知道有多少节点会在某个地方浮动，直到我连接它们，但是将它们保存到队列然后是什么？，因为当我想到我的下一步时我不会我不知道该怎么做。也许将一个节点存储到队列中，直到出现一个节点Parent，然后从队列中取出该节点，但排队其FIFO并没有太多帮助我认为，因为如果我需要采取第二个节点或者第三个节点而不是前面一个。那么可能将它们存储到辅助列表中？我应该添加一个节点到列表，队列，堆栈，如果他们没有父，他们不是根权利？或者我应该将根添加到列表，队列，堆栈？因为我正在使用root来构建树在第一棵树中我的根它的Iolin直到batu出现并且我将它改为batu在第二棵树Root将始终是Piccoro，但是从piccoro开始构建树有点困难因为我不懂他的孩子

你怎么看？我该怎么办？你有更好的或其他想法吗？

int main(int argc, char const *argv[])
{
    FILE *fpInput,*fpOutput;

    fpInput = fopen("input.in","r");
    fpOutput = fopen("output.out","w");

    if ((fpInput == NULL)){ printf("Open File Error\n"); exit(1); }

        // To read a line of the file
        char *fpInputString;
        char *parentInput, *childInput;

        // Because i dont know the number of lines that comes next, read until a number is found
        // That number is the number of consult of kinship about namekians

        fpInputString = inputString(fpInput,5);
        while ((strlen(fpInputString) != 1) && (strlen(fpInputString) != 2) && (strlen(fpInputString) != 3))
        {           

            parentInput = strtok(fpInputString," ");
            childInput  = strtok(NULL,"\0");

            fpInputString = inputString(fpInput,5);
        }


    fclose(fpInput);
    fclose(fpOutput);
    return 0;
}

InputString函数从文件中读取整行

tree.h中

// Struct of a node
struct treeNode
{
    // Name
    char *name;

    // Pointers
    struct treeNode *parent;
    struct treeNode *firstChild;
    struct treeNode *nextSibling;
    struct treeNode *prevSibling;
};

如果你帮助我，我将非常感激，我知道很难理解我或我的代码

但我真的想学习编码的新东西，我不知道如果我用c ++做这个功课会更好，因为c没有STL

Answer 1

使用地图保存输入信息。

找到祖先节点。

将子节点添加到祖先节点。

如果节点不是祖先节点，请不要为节点构建树。