Псевдокод для сравнения двух деревьев

Ответ 1

Похоже, вы просто хотите сделать предварительный обход, по существу. Где "посещать" node означает проверку для детей, которые находятся в одной версии, но не в другой.

Точнее: начинайте с корня. В каждом node получите набор элементов в каждой из двух версий node. Симметричная разность двух наборов содержит элементы в одном, но не в другом. Распечатайте/распечатайте те. Пересечение содержит элементы, которые являются общими для обоих. Для каждого элемента в пересечении (я предполагаю, что вы не собираетесь больше смотреть на элементы, отсутствующие на одном дереве), вызовите "посещать" рекурсивно на этом node, чтобы проверить его содержимое. Это операция O (n) с небольшой накладной рекурсией.

Ответ 2

public boolean compareTrees(TreeNode root1, TreeNode root2) {
  if ((root1 == null && root2 != null) || 
      (root1 != null && root2 == null)) {
    return false;
  }

  if (root1 == null && root2 == null) {
    return true;
  }

  if (root1.data != root2.data) {
    return false;
  }

  return compareTrees(root1.left, root2.left) && 
    compareTrees(root1.right, root2.right);
}

Ответ 3

Если вы используете дерево сортировки, например дерево AVL, вы также можете эффективно перемещать свое дерево в порядке. Это вернет ваши пути в порядке сортировки от "низкого" до "высокого". Затем вы можете отсортировать свой массив каталогов (например, с помощью quicksort), используя тот же метод сравнения, что и в своем дереве.

Затем начните сравнение двух бок о бок, перейдя к следующему элементу, пройдя по дереву в порядке и проверив следующий элемент в вашем отсортированном массиве.

Это должно быть более эффективным на практике, но может сравниться только бенчмаркинг.

Ответ 4

Простой пример кода в python.

class Node(object):
  def __init__(self, val):
    self.val = val
    self.child = {}

  def get_left(self):
    #if left is not in the child dictionary that means the element does not have a left child
    if 'left' in self.child:
      return self.child['left']
    else:
      return None

  def get_right(self):
    #if right is not in the child dictionary that means the element does not have a rigth child
    if 'right' in self.child:
      return self.child['right']
    else:
      return None


def traverse_tree(a):
  if a is not None:
    print 'current_node : %s' % a.val
    if 'left' in a.child:
      traverse_tree(a.child['left'])

    if 'right' in a.child:
      traverse_tree(a.child['right'])



def compare_tree(a, b):
  if (a is not None and b is None) or (a is None and b is not None):
    return 0
  elif a is not None and b is not None:
    print a.val, b.val
    #print 'currently comparing a : %s, b : %s, left : %s, %s , right : %s, %s' % (a.val, b.val, a.child['left'].val, b.child['left'].val, a.child['right'].val, b.child['right'].val)
    if a.val==b.val and compare_tree(a.get_left(), b.get_left()) and compare_tree(a.get_right(), b.get_right()):
      return 1
    else:
      return 0
  else:
    return 1

#Example
a = Node(1)
b = Node(0)
a.child['left'] = Node(2)
a.child['right'] = Node(3)
a.child['left'].child['left'] = Node(4)
a.child['left'].child['right'] = Node(5)
a.child['right'].child['left'] = Node(6)
a.child['right'].child['right'] = Node(7)
b.child['left'] = Node(2)
b.child['right'] = Node(3)
b.child['left'].child['left'] = Node(4)
#b.child['left'].child['right'] = Node(5)
b.child['right'].child['left'] = Node(6)
b.child['right'].child['right'] = Node(7)
if compare_tree(a, b):
  print 'trees are equal'
else:
  print 'trees are unequal'
#DFS traversal
traverse_tree(a)

Также вставлен пример, который вы можете запустить.