UVA # 10410 Реконструкция дерева

Question

Я работал над Реконструкция дерева UVA 10410 несколько дней.Но сейчас я не могу получить правильный ответ unitl.

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

Кто-нибудь может мне помочь?Заранее спасибо.

Answer 1

"Обратите внимание, что когда родитель был расширен, дети пересекались в по возрастанию. " Это предложение очень важно!

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct Node
{
    int value;
    Node *child; //left child
    Node *sibling; //right sibling

    Node(int v)
    {
        value = v;
        child = NULL;
        sibling = NULL;
    }
};

void BuildTree(Node *&root,vector<int> bfs,vector<int> dfs)
{
    root = NULL;
    if(bfs.size() == 1)
        root = new Node(bfs[0]);
    if(bfs.size() > 1)
    {
        root = new Node(bfs[0]);

        vector<int> candidate; //store candidate childs
        unsigned i;
        for(i = 1; i < bfs.size(); i++)
        {
            if(bfs[i] >= bfs[1])
                candidate.push_back(bfs[i]);
            else
                break;
        }

        //remove the non-candidate node
        int boundOfChild = candidate.size() - 1;
        for(i = candidate.size() - 1; i >= 1; i--)
        {
            vector<int>::iterator it1;
            vector<int>::iterator it2;
            it1 = find(dfs.begin(),dfs.end(),candidate[i]);
            it2 = find(dfs.begin(),dfs.end(),candidate[i - 1]);
            if(it1 < it2)
                boundOfChild = i;
        }
        if(boundOfChild != candidate.size() - 1)
            candidate.erase(candidate.begin() + boundOfChild,candidate.end());

        //get every child's bfs and dfs
        for(i = candidate.size(); i >= 1; i--)
        {
            vector<int>::iterator it1;
            vector<int>::iterator it2;
            if(i == candidate.size())
            {
                it1 = find(dfs.begin(),dfs.end(),candidate[i - 1]);
                it2 = dfs.end();
            }
            else
            {
                it1 = find(dfs.begin(),dfs.end(),candidate[i - 1]);
                it2 = find(dfs.begin(),dfs.end(),candidate[i]);
            }

            vector<int> tmp_dfs(it1,it2);
            vector<int> tmp_bfs;
            for(vector<int>::iterator it = bfs.begin(); it < bfs.end(); it++)
            {
                if(find(tmp_dfs.begin(),tmp_dfs.end(),*it) != tmp_dfs.end())
                    tmp_bfs.push_back(*it);
            }

            Node *tmp = root->child;
            BuildTree(root->child,tmp_bfs,tmp_dfs);
            root->child->sibling = tmp;
        }
    }
}

void PrintTree(Node *root)
{
    if(root == NULL)
        return;
    queue<Node*> Q;
    Q.push(root);
    while(!Q.empty())
    {
        Node *tmp = Q.front();
        Q.pop();
        cout << tmp->value << ": ";
        tmp = tmp->child;
        while(tmp)
        {
            cout << tmp->value << ",";
            Q.push(tmp);
            tmp = tmp->sibling;
        }
        cout << endl;
    }
}

//just test case
int BFS[] = {7,8,12,4,5,1,6,11,2,3,10,9,13,14};
int DFS[] = {7,8,4,5,2,3,12,1,6,10,14,11,9,13};

int main()
{
    vector<int> vBFS(BFS,BFS + sizeof(BFS) / sizeof(int));
    vector<int> vDFS(DFS,DFS + sizeof(DFS) / sizeof(int));

    Node *root = NULL;
    BuildTree(root,vBFS,vDFS);    
    PrintTree(root);

    return 0;
}

Answer 2

Я думаю, что у меня есть навык. Я не притворяюсь, что это эффективно.

Давайте посмотрим на первые 3 цифры вывода BFS:

4 3 5

Мы находимся в одной из следующих ситуаций:

  4         4
/  \   OR   |
3  5        3
x  x        |
            5
            x

Что такое DFS для этих двух случаев?

• 4 3 (дети 3s) 5 (дети 5s)
• 4 3 5 (5 детей)

Быстрое примечание: если 3 не имеет детей, то невозможно различить двух ...

Если мы считаем, что проблема разрешима, то нужно знать, следует ли 5 за 3 в представлении DFS.

• Если это так: это линейная композиция
• Если это не так, вы идете рекурсивно: 4 имеет 2 дочерних элементов 3 и 5, и вы можете легко идентифицировать поддерево из представления DFS. Затем извлеките (сохраняя порядок) представление BFS этих поддеревьев из имеющейся у вас BFS и рекурсивно:)

Это выглядит довольно далеко от оптимального, но я немного больше беспокоюсь о неразрешимости.

Существует ли ограничение в деревьях синтаксического анализа, которое гласит, что если у вас есть узел, у которого есть только один дочерний элемент, ни один из узлов в поддереве, которое он представляет, не может иметь более одного?