Сравняване на две дървета, за да се види дали са еднакви

Използвах Neighbor-joining, за да изведа филогенетично дърво. Направих също стартиране, но не е ясно как да сравня топологиите на репликите на първоначалното зареждане с тази на оригиналното дърво. Например възел А на оригиналното дърво възстановен ли е в репликата на Boostrap? Какъв е алгоритъмът за сравняване на топологията на две невкоренени дървета?

Пример:

Две дървета, които трябва да се сравнят, за да се види дали някои възли са различни

Дърво, с което да се сравнява


algorithm tree
person keterpstra_mwu    schedule 17.12.2016    source източник

Отговори (1)


arrow_upward
0
arrow_downward

Най-доброто обяснение е дадено тук,

  1. Обърнете се към GeeksForGeeks тук
  2. CrazyForCode
  3. StackOverFlow
person dahiya_boy    schedule 17.12.2016
comment
Трябва да сравня дърветата са подобни или различни поради родителския възел. Листата и вътрешните клони често имат различни дължини и все още се считат за подобна част на дърветата. Предполагам, че в крайна сметка търсят подобен път на дърво, когато сравняват дървета. Не знам лесен тест за това. Единствената лесна част е съпоставянето на листата на дърветата. Надявам се, че примерните дървета дават обяснение. - person keterpstra_mwu; 21.12.2016
comment
Трябва да сравня дървета, за да намеря дали възлите на дървото съвпадат. Докато вървите към корена, дърветата ще имат по-малко съвпадения. С много голям брой съвпадения, докато стигнете до листата. Ние сравняваме поддърветата или възлите, за да видим дали съвпадат. Използвах метода на точно съвпадение, но това не покрива всички клонове, които биха съвпаднали. Ще се опитам да дам добър пример във въпроса. Синият или аква текст съдържа две дървовидни диаграми, които можете да видите. - person keterpstra_mwu; 05.01.2017
comment
Бихте ли обяснили данни или стойност? Сравнявам топология на дървета, които често са подобни, но имат различни дължини на клоните. Стартирането съпоставя възлите на дървото с друго дърво. Има обстоятелства, при които изглежда, че дърветата са, но всъщност са същите. - person keterpstra_mwu; 11.01.2017
comment
Последното изречение трябва да гласи: Има обстоятелства, при които дърветата изглеждат различни, но всъщност са еднакви. Това се дължи на вмъкване на корен в клад или възел близо до мястото, където се опитвате да сравните. - person keterpstra_mwu; 12.01.2017
comment
Бихте ли могли да обясните какви са стойностите във всеки възел. Дали са например дължината на линията на дървото? - person keterpstra_mwu; 21.01.2017