Сравнить два дерева

Question

[Zubchick]

Привет, никак не могу найти описание какого-нибудь алгоритма по сравнению двух деревьев, подскажите пожалуйста

Comments

[maxgalkin]

Конкретизируйте вопрос, пожалуйста.

Answer 1

[TheHorse]

function compare(tree1, tree2): boolean;
var i : integer;
begin
   result := true;
   if tree1.childCount <> tree2.childCount then
   begin
      result := false;
      exit;
   end;
   for i:= 0 to tree1.childCount - 1 do
   begin
     if tree1.child[i].value <> tree2.child[i].value then
       result := false
     else
       result :=  compare(tree1.child[i], tree2.child[i]);
     if result = false then break;  
   end;
end;

Comments

[Zubchick]

Спасибо за труды конечно, но мне хотелось что-то менее пиримитивное, мне нужно что-то похожее на дифф для деревьев

[TheHorse]

Это было не трудно). Структура деревьев может быть разной, или только значения листьев рызные?

[Zubchick]

структура конечно тоже

Answer 2

[philpirj]

Сначала сравниваете общие признаки — кору, листья/иголки, высота…
Вроде как сессия ещё не скоро?
Несколько алгоритмов тут.

Comments

[Zubchick]

Хорошая шутка!
Но все это я видел

Answer 3

[eliah_lakhin]

Рекомендую посмотреть сюда: stackoverflow.com/questions/523307/semantic-diff-utilities. В особенности на комментарий Ira Baxter.

В качестве собственного варианта могу предложить вам, например, сделать представление дерева в виде списка(просто последовательный обход всех вершин), а потом применить к этому списку обычный diff.