восстановление дерева от его предварительного порядка и постсписков заказов
Я просто записал новое Join, что мне нравится, таким образом, я думал, что повторно отвечу с ним:
public static string Join<T>(this IEnumerable<T> source, string separator)
{
return string.Join(separator, source.Select(e => e.ToString()).ToArray());
}
Одна из прохладных вещей об этом - то, что это работает с наборами, которые не являются строками путем вызова ToString () на элементах. Использование является все еще тем же:
//...
string s = " 1 2 4 5".Split (
" ".ToCharArray(),
StringSplitOptions.RemoveEmptyEntries
).Join (" ");
3 ответа
You cannot use only one list, because you'll get no sense of the depth of the tree. Thus, you definitely require two or more lists.
Here's my attempt at a solution:
Use your preorder traversal as a means of knowing the ordering of the data. This makes sense because you know the first node is the top, and you know that data further to the left of the traversal belongs to the left of the tree, etc.
Your post order traversal can determine the depth of the tree. For example, let's say I have a structure like this:
1
2 5 6
3 4 7
Where 2 is the parent of 3 and 4, and 5 is the parent of 7.
Preorder: 1 2 3 4 5 7 6
Postorder: 3 4 2 7 5 6 1
We know we start with 1, because it is the first node in the preorder traversal. Then we look at the next number, 2. In the post order, because the number 2 comes BEFORE node 1, we know that 2 has to be a child of 1. Next we look at 3. 3 comes before 2, and thus 3 is a child of 2. 4 is before 2 but after 3, so we know 4 is a child of 2 but NOT a child of 3. Etc.
Now, this may not work if the nodes are not unique, but at the very least its a start to a solution.
Edit: The order of the children is preserved with this solution, simply due to knowing the ordering of the nodes via the preorder traversal, and then knowing the structure via the postorder traversal.
Edit2: The proof may lie here: http://ieeexplore.ieee.org/Xplore/login.jsp?url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel2%2F215%2F626%2F00017225.pdf%3Farnumber%3D17225&authDecision=-203
I think you need to purchase the document, however...
Here is a written proof presented to be a solution:
http://www14.informatik.tu-muenchen.de/lehre/2007WS/fa-cse/tutorials/tutorial09-solutions.pdf
Предварительный и последующий порядок не определяют однозначно дерево.
В общем, один обход дерева не определяет однозначно структура дерева. Например, как мы видели, для обоих следующие деревья, обход без порядка дает [1,2,3,4,5,6].
4 3
/ \ / \
2 5 2 5
/ \ \ / / \
1 3 6 1 4 6
Такая же неоднозначность присутствует для предварительного и последующего порядка обходы. Обход предварительного заказа для первого дерева выше: [4,2,1,3,5,6]. Вот другое дерево с таким же предзаказом обход.
4
/ \
2 1
/ \
3 6
\
5
Точно так же мы можем легко построить другое дерево, поступорядочение которого traversal [1,3,2,6,5,4] совпадает с первым деревом выше.
Рассмотрим произвольное дерево T как четверку (A, B, C , D ), где A - корневой узел, B - корневой узел первого дочернего элемента, C - вектор любого не- пустые дочерние элементы B, а D - вектор любых непустых братьев и сестер B. Элементы C и D сами являются деревьями.
Любой из A, B, C и D может быть пустым. Если B пусто, то должны быть C и D ; если А, то все.
Поскольку узлы уникальны, наборы узлов, содержащиеся где-либо в пределах C и D , не пересекаются и не содержат ни A, ни B.
Функции pre () и post () генерируют упорядоченные последовательности вида:
pre (T) = [A, B, pre ( C ) , pre ( D ) ]
post (T) = [ post ( C ) , B , post ( D ) , A]
где функция, применяемая к вектору, определяется как конкатенация последовательностей, возникающих в результате применения функции к каждому элементу по очереди.
Теперь рассмотрим случаи:
- если A пусто, выходом обеих функций будет пустая последовательность []
- , если B пусто, выходом обеих функций будет просто [A]
- , если C и D пусты, pre (T) = [A, B] и post (T) = [B, A]
- , если только C пуст, pre (T) = [A, B, D '] и post (T) = [B, D '' , A] (где штрихи указывают на некоторую перестановку узлов, содержащихся в D )
- , если только D пусто, pre (T) = [A, B, C '] и post (T) = [ C' ', B, A]
- , если ни один не пуст, pre (T) = [A, B, C ', D' ] и post (T) = [ C '' , B, D '' , A]
Во всех случаях мы можем однозначно разделить элементы двух выходных последовательностей в Соответствующие подпоследовательности, используя A и B (если они есть) в качестве разделителей.
Тогда возникает вопрос, можем ли мы также разделить векторные последовательности? Если мы можем, то каждый из них может быть рекурсивно обработан, и все готово.
Поскольку результатом pre () всегда будет цепочка последовательностей , начинающаяся с узлами A, а результатом post () всегда будет цепочка последовательностей , заканчивающаяся узлами A, мы действительно можем разделить их при условии , что узлы A никогда не бывают пустыми.
Здесь процесс падает в случае двоичных (или любых других) деревьев с фиксированными дочерними элементами, которые могут быть независимо пустыми. В нашем случае, однако, мы определили C и D так, чтобы они содержали только непустые узлы, и поэтому реконструкция гарантированно работает.
Я так думаю, во всяком случае. Очевидно, это всего лишь аргумент, а не формальное доказательство!