25

这是我遇到过几次的问题，并且不相信我使用了最有效的逻辑。

例如，假设我有两棵树：一棵是文件夹结构，另一棵是该文件夹结构的内存“模型”。我希望比较两棵树，并生成一棵树中存在的节点列表，而不是另一棵树 - 反之亦然。

是否有公认的算法来处理这个问题？

4

5 回答 5

13

基本上，您似乎只想进行预购遍历。“访问”一个节点意味着检查一个版本但不是另一个版本的子节点。

更准确地说：从根开始。在每个节点上，在节点的两个版本中的每一个中获取一组项目。两组的对称差包含一组中的项，而不包含另一组中的项。打印/输出那些。交集包含两者共有的项目。对于交叉点中的每个项目（我假设您不会进一步查看一棵树中缺少的项目），在该节点上递归调用“访问”以检查其内容。这是一个 O(n) 操作，有一点递归开销。

于 2013-10-11T05:25:14.613 回答
3 
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);
}
于 2015-06-25T22:02:42.797 回答
2

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)

还粘贴了一个可以运行的示例。

于 2015-08-28T06:04:15.117 回答
1

如果您使用排序树，例如 AVL 树，您还可以有效地按顺序遍历您的树。这将以从“低”到“高”的排序顺序返回您的路径。然后您可以使用与您在树算法中使用的相同比较方法对您的目录数组进行排序（例如使用快速排序）。

然后开始并排比较两者，通过按顺序遍历树并检查排序目录数组中的下一项来前进到下一项。

这在实践中应该更有效，但只有基准测试才能说明。

于 2015-08-29T10:19:55.087 回答
1

您可能还想看看git它是如何做到的。基本上，每当您执行git diff, 在引擎盖下进行树比较时。

于 2019-11-22T13:45:09.897 回答