在最简单的情况下，我有两个树（有向图），每个树节点都有一个唯一的id，并且可以有多个子节点，其中第二个树的所有叶子都包含在第一个树的叶子中 . 基于叶子，我想将第一棵树分成两棵树，使得新的第一棵树不包含原始第二棵树的任何叶子，而新的第二棵树将包含原始第二棵树的所有叶子 . 诀窍还在于，如果节点的所有子节点都将移动到新的第二个树，那么节点本身也应该被移动 .
例如，对于这样的两棵树作为输入：
-
1（第一棵树的根）
-
11
-
111
-
1111
-
11111
-
11112
-
1112
-
11121
-
11122
-
112
-
11201
-
11202
-
12
-
121
-
12101
-
12102
-
122
-
12201
-
12202
-
2（第二棵树的根）
-
21
-
211
-
2111
-
11112
-
212
-
11201
-
11202
我希望得到两棵新树，这样：
-
1（新的第一棵树的根）
-
11
-
111
-
1111
-
11111
-
1112
-
11121
-
11122
-
12
-
121
-
12101
-
12102
-
122
-
12201
-
12202
-
2（新第二棵树的根）
-
21
-
211
-
2111
-
11112
-
112（从原始第一个树复制的节点导致其所有子节点复制）
-
11201
-
11202
实现这一目标的最佳方法（算法）是什么？
从第一个树中删除节点很简单，但是我有问题如何从第一个树中重新构造第二个树重用节点 .
我正试图在Java 1.7版本中实现这种拆分（我不能使用1.8） .
编辑
我能够在下面的答案中提出一个解决方案，更多细节，但如果有人能提供我更好的一个，我也会很高兴:)
1 回答
我提出了解决问题的方法，也许对任何人都有用 . 我的算法如下：
让我们将第一个原始树称为源树，将第二个原始树称为掩码树 .
将树转换为叶子列表，其父项来自所有原始树 .
迭代叶子列表并从叶子父级重建树 .
来自掩码树的父母对源头树的父母有更高的优先权
为掩码树父目录注册源树父作为可能的替换
迭代可能的替换，如果未在任何树中使用替换，则用节点替换它 .
不确定我是否说得够清楚 . 如果没有，请检查BitBucket TreeSplitter上可用的implamantation .
这个解决方案可能不是最优的，所以如果你有更好的方法将其作为答案发布 .