有向树变异算法

Question

我想出了一个检测两棵定向树之间“突变”的问题。

示例: tree1：

    A         
   /  \        
  B    C - D      
 / \  / \   \ 
G   A 2  A   3
| \   |\ 
1  3  2 3

tree2：

    A         
   /  \        
  B    C - F      
 / \  /    \ 
G   A 2     3
| \   |\ 
1  3  2 3

算法应该会发现有一个变异

R
|
C - D
|\   \
X Y   Z

倒置

R
|
C - D
|   \
X    Z

其中R、Y和Z是各自的值。

我正在寻找任何想法，可能是：

algorithms

• pseaudocode

• code

• 链接到任何语言的算法或带有某些的书籍(最好是任何语言(最好是)中的)

Answer 1

你看过树的差异问题吗？

大多数树差异问题产生一个更改列表(例如，节点的插入、删除、移动和重新标记)，而不是模板子树，但它们可能给您提供了一个起点。