c++ - 从森林中构建一棵 n 叉树

Question

我要求教授给我一份另一个学期的旧作业。它是关于构建一个家谱，然后找到给定的两个节点之间的亲属关系。家谱是关于那美克星人(龙珠z)的，所以每个那美克星人都有一个父亲。

问题是输入是这样的:

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

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

你觉得怎么样？我应该怎么办？您有更好的或其他想法吗？

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 函数从文件中读取整行

树.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

用 map 保存输入信息。

找到祖先节点。

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

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