检测树结构之间的差异
这更像是一个CS问题，但却是一个有趣的问题：
比方说，我们有2个树结构，或多或less相同的节点重组。 你会如何发现
- 任何
- 在某种意义上说是最小
操作顺序
-
MOVE(A, B)– 移动节点B下的节点A（整个子树） -
INSERT(N, B)– 在节点B下插入一个新节点N. -
DELETE (A)– 删除节点A（与整个子树）
将一棵树转换为另一棵树。
可能显然存在这样的转换不可能的情况，根本上是小孩B与小孩A之间的根B）。 在这种情况下，algorithm只会传递一个“ 不可能 ”的结果。
更壮观的版本是对networking的一种推广，即当我们假设一个节点可以在树中多次出现（实际上有多个“父母”），而周期是禁止的。
免责声明：这不是一个家庭作业，实际上它来自一个真正的商业问题，我发现它是相当有趣的，想知道如果有人可能知道一个解决scheme。
不仅有维基百科关于图同构的文章（正如Space_C0wb0y指出的那样），而且还有关于图同构问题的专门文章。 它有一个部分Solved special cases了多项式时间解已知的Solved special cases 。 树是其中之一，它引用了以下两个引用：
- PJKelly，“树的同余定理”，太平洋math杂志，7（1957），第961-968页
- 阿霍，阿尔弗雷德五世。 霍普克罗夫特，约翰; Ullman，Jeffrey D.（1974），“计算机algorithm的devise与分析”，Reading，MA：Addison-Wesley。
您不清楚您是否比较源代码的抽象语法树，解释为树的XML文档或某种其他types的树。
有很多论文讨论比较语法树和通过各种方法计算最小距离。 这些想法应该是相关的。
一个很好的论文是Change Distilling ，它试图比较两个抽象语法树的源代码并报告最小差异。 本文讨论了一种特定的方法，并且还提到了许多类似的技术（并提供了参考）。
几乎没有这些algorithm实际上是用于比较源文本的可用工具。 我们的智慧差异就是其中之一。
虽然这个问题很老，但我会在下面添加更多的参考和algorithm：
- X-Diff：一种有效的XML文档变化检测algorithm，王远，David J. DeWitt，蔡金义
- KF-Diff +：XML文档的高效变化检测algorithm
- diffX：一种用于检测多版本XML文档中的更改的algorithm
- XML树中的变化检测：一项调查，Luuk Peters
- 树数据结构的相似性
此外，在GitHub上（在JavaScript中）有库和框架，它们实现树状结构的差异，例如处理JSON数据或XML树的应用程序（例如，用于客户端MVC / MVVM）：
- React.js
- JSON-补丁
- jsondiffpatch
- objectDiff
如果人们发现这个问题，并需要为Node.js或浏览器实现的东西，我提供了一个链接和代码示例，我已经写了一个实现，你可以在这里findgithub：（ https://github.com /hoonto/jqgram.git ）基于现有的PyGram Python代码（ https://github.com/Sycondaman/PyGram ）。
这是一个树编辑距离近似algorithm，但比试图find真正的编辑距离要快得多。 近似在O（n log n）时间和O（n）空间中执行，而使用已知的编辑距离的真实algorithm，真正的编辑距离通常是O（n ^ 3）或O（n ^ 2）。 请参阅PQ-Gramalgorithm的学术论文：（ http://www.vldb2005.org/program/paper/wed/p301-augsten.pdf ）
所以使用jqgram：
例：
var jq = require("jqgram").jqgram; var root1 = { "thelabel": "a", "thekids": [ { "thelabel": "b", "thekids": [ { "thelabel": "c" }, { "thelabel": "d" } ]}, { "thelabel": "e" }, { "thelabel": "f" } ] } var root2 = { "name": "a", "kiddos": [ { "name": "b", "kiddos": [ { "name": "c" }, { "name": "d" }, { "name": "y" } ]}, { "name": "e" }, { "name": "x" } ] } jq.distance({ root: root1, lfn: function(node){ return node.thelabel; }, cfn: function(node){ return node.thekids; } },{ root: root2, lfn: function(node){ return node.name; }, cfn: function(node){ return node.kiddos; } },{ p:2, q:3 }, function(result) { console.log(result.distance); });
这就给了你一个介于0和1之间的数字。越接近于零，两棵树的关系就越密切。 一种方法可能是使用jqgram从许多树木中按照其速度缩小几个密切相关的树木，然后在剩下的几棵树上利用真正的编辑距离进行仔细检查，并且为此可以findpython例如用于张和沙沙algorithm的参考或端口的实现。
请注意，lfn和cfn参数指定每棵树应该如何独立确定每个树根的节点标签名称和子节点数组，以便您可以做比较对象与浏览器DOM等时髦事物。 所有你需要做的就是提供这些函数以及每个根，jqgram将完成剩下的工作，调用你的lfn和cfn提供的函数来构build树。 所以从这个意义上来说，（在我看来）比PyGram更容易使用。 另外，它的Javascript，所以使用它的客户端或服务器端！
另外，就周期检测而言，应该检查jqgram里面的克隆方法，在那里有周期检测，但是对于那些稍微修改和包含的节点克隆的作者来说，这是值得的。
