伪代码比较两棵树

Question

这是我遇到过几次的问题，而且我并不确定我使用的逻辑是最高效的。

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

是否有一种已被接受的算法来处理这个问题呢？

- ianmayo

---

给那位对这个问题进行了负评的人。如果您能给一些反馈，解释一下为什么要负评，我会非常感激。这样我就可以成为更好的Stack Overflow参与者了... - ianmayo

Answer 1

看起来你只想做一个先序遍历，本质上是这样的。在"访问"一个节点时，意味着检查那些在一个版本中但不在另一个版本中的子节点。

更具体地说: 从根开始。在每个节点，在两个节点版本中获取一组项目。两个集合的对称差包含了其中一个而不是另一个版本的项目。打印/输出它们。交集包含共同存在于两个版本中的项目。对于交集中的每个项目(我假设你不会进一步查找缺失的节点)，递归调用 "访问" 其内容的节点进行检查。这是一个O(n)的操作，有一点递归开销。

- Jeremy West

---

注意：遍历的时间复杂度为O(n)。对称差和交集取决于您用来存储项目的容器，它们是否已排序等因素。 - Jeremy West

Answer 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);
}

- Pratik Khadloya

Answer 3

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 right 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)

我也附上了一个可以运行的示例。

- RamPrasadBismil

Answer 4

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

接下来，将两者逐个比较，通过按顺序遍历你的树并检查已排序的目录数组中的下一个项目来前进到下一个项目。

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

- benjist

Answer 5

你可能也想看看 git 是如何做的。实际上，每当你执行 git diff 命令时，在幕后都会进行一次树比较。

- se7entyse7en