c - 合并两个未排序和不可排序的树

Question

是的，我正在学习 CS，并且已经完成了 C 语言的实验室，一切进展顺利，但我现在遇到了一些似乎无法解决的问题以获得加分。我已经研究了一两天了，只是想不出正确的方法来完成它。

简介

到目前为止的任务总结:

Build the game of pangolins, where the computer stores the questions and objects in a tree structure. The game works as follows: You think of an object and the computer tries to guess what you are thinking of by asking you a series of 'yes/no' questions. If the computer guesses correctly, it wins. If you manage to fool it, you win, but you must then provide the computer with a question that would allow it to guess correctly next time round. That's all there is to it.

您最终得到的树结构示例(从左到右):

                Tree
                /
        Is it made of wood?
                \
                Grass
        /
Is it green?
        \
                Pangolin
                /
        Does it have a legs?
                \
                                Computer
                                /
                        Is it larger than a microwave?
                                \
                                Laptop
                        /
                Does it have a keyboard?
                        \
                        Desk

这是由以下结构组成的:

typedef struct node {
  char* object_name; // object-name (which may be NULL)
  char* question; // question (which may be NULL) 

  struct node *yesNode; // where if yes (NULL)
  struct node *noNode; // where if no (NULL)
} node;

上面的树存储为以下文件:

Is it green?
Does it have a legs?
Does it have a keyboard?
        Desk
Is it larger than a microwave?
        Laptop
        Computer
        Pangolin
Is it made of wood?
        Grass
        Tree

问题

奖金如下:

Make your program take an arbitrary number of input files, and graft them together to make a huge tree. Swap your files with your friends and get a huge collection of pointless questions. To do this properly you need to scan for duplicate entries (you won't be able to do this perfectly, but it should at least weed out obvious duplicates and graft the trees together in sensible ways.)

或总结:

Take your two tree structs (or files representing tree structs) and merge them together to produce a larger tree, while removing duplicates.

我的问题:

1. 如何删除两棵未排序的树？
2. 是否有可能在不手动检查每个节点的情况下删除重复项？
3. 您如何循环到每个节点的底部并将其与另一棵树进行比较？

我最好的想法:

1. 在第二棵树中搜索第一棵树中的对象
2. 用穿山甲对象替换那些对象
3. 找出第一个出现的所有穿山甲
4. 改为将父节点指向第二棵树的顶部

但这破坏了树结构，并可能使游戏中断(假设第一棵树中的首要问题是它是红色的)并且第二棵树附加在 no 节点上并且第二棵树中的所有项目都是红色的？

我的主要问题:

• 您知道如何解决这个问题吗？还是一种可行的黑客攻击？
• 你如何在两棵树中找到重复项？
• 如何将树连接在一起？
• 如何遍历每棵树的底部？

Answer 1

我认为加入所有树的最简单方法是重新构建最小熵决策树，如下所示:

1. 考虑所有项目。
2. 创建一个新节点。
3. 对于节点，选择区分当前项目集中最多项目的问题:
   • 请注意，一个问题区分的项目数是出现该问题的每棵树中该问题下所有项目的总和。
4. 根据问题拆分项目集。
5. 从第 2 步开始对两个新集合中的每一个重复递归。

当涉及到关联逻辑上相同但语言上不同的问题时……这是一个极其困难的自然语言问题。在不进行任何语言分析的情况下，您可以做一些简单的事情，例如忽略大小写、标点符号和空格来比较问题字符串。