Сравнение множеств на структуре бинарного дерева

Question

Интересует вопрос: как можно сравнить два множества, в структуре которых лежат бинарные деревья? Изначально, идеей было сравнить левое/правое поддерево одного множество с левым/правым поддеревом другого, но тогда мы будем получать false, в случае, если элементы находятся в разных поддеревьях. Например, [[1] - [*]] - 5 - [[*] - [*]] и [[5] - [*]] - 1 - [[*] - [*]] -- это одно и тоже множество. Спасибо!

Answer 1

Если это двоичное дерево поиска, реализуйте возможность центрированного обхода дерева, и обходите деревья параллельно, до первого несовпадения или до того, как в одном из деревьев кончатся элементы.

Пример (Haskell)

import Data.Foldable (toList)

data Tree a = Nil | Node (Tree a) a (Tree a) deriving Show

instance Foldable Tree where
  foldMap _ Nil = mempty
  foldMap f (Node left x right) = foldMap f left <> f x <> foldMap f right

instance Eq a => Eq (Tree a) where
  s1 == s2 = toList s1 == toList s2

GHCi> set1 = Node Nil 1 (Node Nil 2 (Node Nil 3 Nil))
GHCi> set2 = Node (Node Nil 1 Nil) 2 (Node Nil 3 Nil)
GHCi> set1 == set2
True

БЛОГ НА HUSL

Сравнение множеств на структуре бинарного дерева

Ответы (1 шт):