Как проверить, являются ли два полных бинарных дерева зеркалом друг друга, где дается только обход уровня деревьев?Учитывая обход уровня порядка двух полных бинарных деревьев, как проверить, является ли одно дерево зеркалом другого?
Полное двоичное дерево - это двоичное дерево, в котором все узлы, кроме листовых узлов, имеют 2 дочерних узла.
Я не думаю, что это возможно. Рассмотрим эти два дерева:
0 0
/\ / \
1 2 1 2
/\ /\ /\
3 4 3 4 5 6
/\
5 6
Эти полные бинарные деревья (по вашему определению), и даже если они разные деревья, они имеют те же обходов уровень порядка:.
Теперь посмотрим в их зеркалах:
0 0
/\ / \
2 1 2 1
/\ /\ /\
4 3 6 5 4 3
/\
6 5
Обратите внимание, что левое дерево имеет уровень порядка обхода 0214365, в то время как правая дерево имеет уровень порядка обхода 0216543. другими словами, оригинальные деревья имеют те же обходы порядка уровне, но их зеркала имеют разные обходы.
Теперь подумайте о том, что произойдет, если у вас есть свой алгоритм, и вы подаете(обход уровня одного из деревьев) и 0214365 (обход уровня одного из зеркал). Что может сказать алгоритм? Если он говорит, что это зеркала, это будет неправильно, если вы будете кормить во втором из входных деревьев. Если в нем говорится, что они не зеркала, это будет неправильно, если вы будете кормить в первом из входных деревьев. Поэтому алгоритм не всегда дает правильный ответ.
Надеюсь, это поможет!
Нет деревьев правила в соответствии с моим определением, я думаю, может быть его полное дерево, в традиционном. И я предполагаю, что обход порядка между зеркалами обоих деревьев одинаковый (0 2 1 4 3). Итак, если нам дают два обхода деревьев (0 1 2 3 4) и (0 2 1 4 3), то можно сказать, что они зеркала? – Tippis
@ Tippis Неверно было бы сказать, что дерево является зеркалом, если оно действительно не является зеркалом. В конце концов, вы можете связать одно дерево с зеркалом другого и не иметь соответствия.(Кстати, тип двоичного дерева, который вы называете «полным» двоичным деревом, традиционно называют ** полным ** бинарным деревом.) – templatetypedef
Спасибо за комментарий. То, что я пытаюсь сказать в более ранних комментариях, было обход уровня обоих деревьев одинаковый, и поэтому их зеркальное обхождение уровня тоже. Возможно ли создать два полных бинарных дерева с их обходным порядком уровня, а их взаимный разброс по уровням зеркал различен? – Tippis
Согласно общим определениям, в полном двоичном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы как можно дальше. Таким образом, полное двоичное дерево может иметь узел с одним ребенком (например, один корневой узел с одним левым дочерним элементом является полным двоичным деревом). Дерево, где все узлы, кроме листьев, имеют 2 дочерних узла, называются полным двоичным деревом.
Для полных бинарных деревьев проблема будет тривиальной. Начиная с нисходящего, для уровня ith вам нужно сравнить 2^i элементов (корень - это уровень 0th) данных обходов уровня A и B. Для любого заданного i набор из 2^i элементов из A должен быть равен на обратную сторону от этих элементов из B. Однако последний уровень не может быть полностью заполнен, и вам нужно будет это учитывать.
Для полных двоичных деревьев, где задано единственное ограничение: каждый узел имеет 2 или ни одного ребенка, это будет невозможно, если вы не построили само дерево. И вы не можете построить дерево, используя только обход уровня. Хорошим примером является templatetypedef.
Что вы думаете о себе? –
То, что я думал, сначала сравнивает корневой элемент. Если они равны, то сравнивайте следующие два элемента (f1, f2) с (s2, s1) в обход порядка порядка. Если они равны, то переместите два следующих двух элемента. числа представляют собой первое и второе. – Tippis