Слияние двух несортированных и несортируемых деревьев

Question

Правильно, я изучаю CS и заканчиваю лабораторию на C, все прошло довольно хорошо, но сейчас я наткнулся на то, что, кажется, невозможно найти для бонусных марок. Я занимался этим день или два, и просто не могу понять, как правильно это сделать.

Введение

Краткое изложение задач на данный момент:

Постройте игру ящеров, где компьютер хранит вопросы и объекты в древовидной структуре. Игра работает следующим образом: вы думаете об объекте, а компьютер пытается угадать, о чем вы думаете, задавая вам ряд вопросов «да / нет». Если компьютер угадает правильно, он побеждает. Если вам удастся обмануть его, вы выиграете, но затем вы должны задать компьютеру вопрос, который позволит ему правильно угадать в следующий раз. Вот и все, что нужно.

Пример древовидной структуры, с которой вы в итоге (слева-> справа):

                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

Проблема

Бонус следующий:

Сделайте так, чтобы ваша программа брала произвольное количество входных файлов и прививала их вместе, чтобы сделать огромное дерево. Обменяйте свои файлы с друзьями и получить огромную коллекцию бессмысленных вопросов. Чтобы сделать это правильно вам нужно сканировать дубликаты записей (вы не сможете сделать это отлично, но это должно по крайней мере отсеять очевидные дубликаты и привить деревья вместе разумным способом.)

или подытожил:

Возьмите две свои древовидные структуры (или файлы, представляющие древовидные структуры) и объедините их вместе, чтобы получить более крупное дерево, удаляя при этом дубликаты.

Моя проблема:

1. Как можно удалить два несортированных дерева?
2. Можно ли даже удалить дубликаты, не проверяя вручную каждый узел?
3. Как вы можете выполнить цикл до конца каждого узла и сравнить его с другим деревом?

Моя лучшая идея:

1. Поиск во втором дереве объектов, которые также находятся в первом дереве
2. Заменить эти объекты панголиновым объектом
3. Найти все вхождения панголина в первом
4. Вместо этого укажите родителя на вершину второго дерева

Но это нарушает древовидную структуру и потенциально приводит к разрыву игры (скажем, главный вопрос в первом дереве: красный), а второе дерево было прикреплено к узлу no, а все элементы во втором дереве были красными

Мои основные вопросы:

• Есть ли у вас какие-либо идеи относительно того, как бы вы решили это? Или взломать что-то вроде работы?
• Как вообще можно найти дубликаты на двух деревьях?
• Как вы соединяете деревья вместе?
• Как вы проходите через нижнюю часть каждого дерева?

Answer 1

Я думаю, что самый простой способ объединить все ваши деревья - это перестроить дерево решений с минимальной энтропией, например:

1. Рассмотрим все предметы.
2. Создать новый узел.
3. Для узла выберите вопрос, который различает большинство элементов в текущем наборе элементов:
   • обратите внимание, что число элементов, между которыми различается вопрос, является суммой всех элементов под вопросом в каждом дереве, где возникает вопрос.
4. Разделить набор предметов по вопросу.
5. Повторите процедуру с шага 2 для каждого из двух новых наборов.

Когда речь идет о сопоставлении логически идентичных, но лингвистически разных вопросов ... это чрезвычайно сложная проблема естественного языка. Не анализируя язык, вы можете сделать что-то простое, например сравнить строки вопросов, игнорируя регистр, пунктуацию и интервал.