我已經在UVA 10410 Tree Reconstruction幾天工作過。但我現在無法得到正確的答案。UVA#10410樹重建
我已經使用了一種類似於我們通常用來通過預遍歷和中序遍歷來恢復二叉樹的算法。但它不能工作。
任何人都可以幫助我嗎?提前致謝。
我已經在UVA 10410 Tree Reconstruction幾天工作過。但我現在無法得到正確的答案。UVA#10410樹重建
我已經使用了一種類似於我們通常用來通過預遍歷和中序遍歷來恢復二叉樹的算法。但它不能工作。
任何人都可以幫助我嗎?提前致謝。
「請注意,當父母擴展時,孩子在 的升序中被遍歷。」 這句話很重要!
#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;
}
我想我有這個問題。我不假裝它是有效的。
讓我們看一下第3位的BFS輸出:
4 3 5
我們在以下情況之一:
4 4
/\ OR |
3 5 3
x x |
5
x
什麼是DFS爲這2案例?
快速注:如果3
沒有任何孩子,那麼這是不可能的告訴兩者分開...
如果我們認爲問題是可判定的,那麼這是一個知道在DFS表示中是否5
跟在3
之後的問題。
4
有2個孩子3
和5
,你可以很容易地從DFS表示確定的子樹。然後從BFS中提取(保留順序)這些子樹的BFS表示,並且遞歸:)它看起來與最佳值相差甚遠,但我更加擔心不可判定性。
是否有表達,解析樹的約束其中規定,一旦你有一個只有一個孩子沒有節點在它代表可以有不止一個的子樹的節點?
我不認爲可決定性很重要。解決方案應該找到適合的樹,可以有多個答案。此外,問題陳述中提到的解析樹只是故事的一部分,給定的遍歷不一定是解析樹的一部分:)。它可以是任何樹... – IVlad 2010-04-21 17:48:40
看起來有趣!這將成爲我的新玩具問題:D – 2010-04-21 14:32:54
我有一個想法。請注意這個說法:「請注意,當父母擴大時,孩子按照升序排列。」我會盡快粘貼我的代碼。 – Vincent 2010-04-22 02:35:40