Это проблема, с которой я столкнулся несколько раз, и не был убежден, что я использовал наиболее эффективную логику.
В качестве примера предположим, что у меня есть два дерева: одна - структура папок, другая - "модель" в этой структуре папок. Я хочу сравнить два дерева и создать список узлов, которые присутствуют в одном дереве, а не в другом - и наоборот.
Есть ли приемлемый алгоритм для этого?
Похоже, вы просто хотите сделать предварительный обход, по существу. Где "посещать" node означает проверку для детей, которые находятся в одной версии, но не в другой.
Точнее: начинайте с корня. В каждом node получите набор элементов в каждой из двух версий node. Симметричная разность двух наборов содержит элементы в одном, но не в другом. Распечатайте/распечатайте те. Пересечение содержит элементы, которые являются общими для обоих. Для каждого элемента в пересечении (я предполагаю, что вы не собираетесь больше смотреть на элементы, отсутствующие на одном дереве), вызовите "посещать" рекурсивно на этом node, чтобы проверить его содержимое. Это операция O (n) с небольшой накладной рекурсией.
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);
}
Если вы используете дерево сортировки, например дерево AVL, вы также можете эффективно перемещать свое дерево в порядке. Это вернет ваши пути в порядке сортировки от "низкого" до "высокого". Затем вы можете отсортировать свой массив каталогов (например, с помощью quicksort), используя тот же метод сравнения, что и в своем дереве.
Затем начните сравнение двух бок о бок, перейдя к следующему элементу, пройдя по дереву в порядке и проверив следующий элемент в вашем отсортированном массиве.
Это должно быть более эффективным на практике, но может сравниться только бенчмаркинг.
Простой пример кода в 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)
Также вставлен пример, который вы можете запустить.