Кто знает алгоритм проверки двух деревьев на изоморфизм

vlad12

Скажите пожалуйста. Как это делается не тупым перебором.

Lika25

как это - не тупым?
оба дерева по разу все равно придется пройти
если не то - напиши подробнее

vlad12

Расскажи пожалуйста поподробнее, как это сделать пройдя всего по разу!

Lika25

допускаем null-trees


void compare_trees (node *root1, node *root2)
{
if (!(root1 && root2) || (cc = root1->childrencount) != root2->childrencount)
return false;
for (i = 0; i < cc && compare_trees (root1->children[i], root2->children[i]); i++);
if (i != cc)
return false;
return true;
}

Lika25

sorry
bool compare_trees (node *, node *);

slo14

a) не откомпилируется
б) порядок перечисления "детей" может быть разным, если я не ошибаюсь

Lika25

про б) - к автору треда вопрос
в этом случае такой простой алгоритм не подойдет, конечно
пусть он подробнее напишет какие у него деревья и зачем это нужно

slo14

Ну, судя по тому, что у него появились сомнения насчет однопроходности...
А может просто не разобрался.
В третьем лице обращаются либо к королевским и т.п. особам, но в этом случае следует называть титул. Либо - Горлум так еще любил делать...

Lika25

я вообще-то реплай тебе делал, поэтому так написал
имелось ввиду продолжение: ", тогда мы и разберемся что к чему"
ну да ладно, забей на это
Оставить комментарий
Имя или ник:
Комментарий: