UVA＃10410树重建

Question

我已经在UVA 10410 Tree Reconstruction几天工作过。但我现在无法得到正确的答案。

我已经使用了一种类似于我们通常用来通过预遍历和中序遍历来恢复二叉树的算法。但它不能工作。

任何人都可以帮助我吗？提前致谢。

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为这2案例？

• 4 3（3S子女）5（5S子女）
• 4 3 5（5S子女）

快速注：如果3没有任何孩子，那么这是不可能的告诉两者分开...

如果我们认为问题是可判定的，那么这是一个知道在DFS表示中是否5跟在3之后的问题。

• 如果是这样：这是一个线性组成
• 如果没有，那么你去递归：4有2个孩子3和5，你可以很容易地从DFS表示确定的子树。然后从BFS中提取（保留顺序）这些子树的BFS表示，并且递归:)

它看起来与最佳值相差甚远，但我更加担心不可判定性。

是否有表达，解析树的约束其中规定，一旦你有一个只有一个孩子没有节点在它代表可以有不止一个的子树的节点？