伪代码比较两棵树 [英] Pseudocode to compare two trees

问题描述

这是我遇到过几次的问题，而且还没有确信我使用了最有效的逻辑。

This is a problem I've encountered a few times, and haven't been convinced that I've used the most efficient logic.

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

As an example, presume I have two trees: one is a folder structure, the other is an in-memory 'model' of that folder structure. I wish to compare the two trees, and produce a list of nodes that are present in one tree and not the other - and vice versa.

是否有一种公认的算法可以

Is there an accepted algorithm to handle this?

推荐答案

似乎本质上来说，您只是想进行预遍历。 访问节点意味着检查一个版本而不是另一个版本的子级。

Seems like you just want to do a pre-order traversal, essentially. Where "visiting" a node means checking for children that are in one version but not the other.

更准确地说：从根开始。在每个节点上，在节点的两个版本中的每个版本中获取一组项目。两组的对称差异包含一项，但另一项不包含。打印/输出那些。相交包含两个共同的项目。对于相交处的每个项目（假设您不会再深入研究一棵树中缺少的项目），请对该节点进行递归调用 visit以检查其内容。这是一个O（n）操作，具有少量递归开销。

More precisely: start at the root. At each node, get a set of items in each of the two versions of the node. The symmetric difference of the two sets contains the items in one but not the other. Print/output those. The intersection contains the items that are common to both. For each item in the intersection (I assume you aren't going to look further into the items that are missing from one tree), call "visit" recursively on that node to check its contents. It's a O(n) operation, with a little recursion overhead.

这篇关于伪代码比较两棵树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！