各ノードが任意の数の子ノードを持つことができる、順序付けられていない根付きツリーを使用する Java でコードを書いています。木 T と部分木 S が与えられた場合、S に一致する T 内のすべての部分木 (つまり、S に同型である T 内のすべての部分木) を見つけられるようにしたいと考えています。
T の部分木は、S のエッジが T のエッジにマッピングされるように S のノードを T のノードにマッピングできる場合、S に同形です。
ツリーに別のサブツリーが含まれているかどうかを確認する方法について以前の質問がありましたが、S に一致する T のすべてのサブツリーを検索できるようにしたいと考えています。さらに、 T の各一致の各ノードからS の対応するノード。
つまり、一致が見つかった場合、単純に S に一致するツリーがルート化されている T 内のノードへのポインターとしてではなく、ノードへのポインターのペアのリストのようなものとして一致を返す必要があります [ (T1,S1),(T2,S2),...(Tn,Sn)] であり、T1 は、サブツリー内のノード S1 にマップされる T 内のノードへのポインターです。
別の方法として、ツリー T とサブツリー S の各ノードには固有の整数識別子が関連付けられているため、単に値のペアのリストを返すこともできます。
例えば：
木 T が次のように与えられます。
a
/ \
b c
/ \
d e
サブツリー S は次のようになります。
x
/ \
y z
次の一致のリストが返されます。
[(a,x),(b,y),(c,z)] [(b,x),(d,y),(e,z)]
一意の一致は、T と S のノード間のマッピングではなく、T のノードのセットによって決定されます。
したがって、次の一致：
[(a,x),(b, z ),(c, y )]
の複製と見なされます
[(a,x),(b, y ),(c, z )]
それらは T (a,b,c) からの同じノードのセットを持っているため、一致するもののうちの 1 つだけが返されます。
別の例として、ツリー T が与えられた場合:
a
/|\
b c d
部分木 S:
x
/ \
y z
次の一致のリストが返されます。
[(a,x),(b,y),(c,z)] [(a,x),(b,y),(d,z)] [(a,x),(c,y) ,(d,z)]
誰でもこれを行う方法のサンプルコードを教えてもらえますか?
編集（Chris Kannonのコメントに関連して）：
誰かに答えをコーディングしてもらいたいと思っていますか? どこまで行きましたか？どんなコードを書きましたか？– クリス・カノン 1時間前
次のコードを実行すると、特定のサブツリーに一致するサブツリーがルート化されているツリー内のノードへのポインターのリスト (matchesList) が作成されます。ただし、同じノードをルートとする複数のサブツリーが存在する可能性があり、現在、各ノードは、そこにルートが設定されている一致の数に関係なく、matchesList に最大 1 回しか追加されません。
さらに、サブツリーのノードと元のツリーで見つかった一致のノードとの間で上記のマッピングを構築する方法がわかりません。
package Example;
import java.util.LinkedList;
import java.util.Vector;
public class PartialTreeMatch {
public static void main(String[] args) {
NodeX testTree = createTestTree();
NodeX searchTree = createSearchTree();
System.out.println(testTree);
System.out.println(searchTree);
partialMatch(testTree, searchTree);
}
static LinkedList<NodeX> matchesList = new LinkedList<NodeX>();
private static boolean partialMatch(NodeX tree, NodeX searchTree) {
findSubTreeInTree(tree, searchTree);
System.out.println(matchesList.size());
for (NodeX n : matchesList) {
if (n != null) {
System.out.println("Found: " + n);
}
}
return false;
}
private static NodeX findSubTreeInTree(NodeX tree, NodeX node) {
if (tree.value == node.value) {
if (matchChildren(tree, node)) {
matchesList.add(tree);
}
}
NodeX result = null;
for (NodeX child : tree.children) {
result = findSubTreeInTree(child, node);
if (result != null) {
if (matchChildren(tree, result)) {
matchesList.add(result);
}
}
}
return result;
}
private static boolean matchChildren(NodeX tree, NodeX searchTree) {
if (tree.value != searchTree.value) {
return false;
}
if (tree.children.size() < searchTree.children.size()) {
return false;
}
boolean result = true;
int treeChildrenIndex = 0;
for (int searchChildrenIndex = 0; searchChildrenIndex < searchTree.children
.size(); searchChildrenIndex++) {
// Skip non-matching children in the tree.
while (treeChildrenIndex < tree.children.size()
&& !(result = matchChildren(tree.children
.get(treeChildrenIndex), searchTree.children
.get(searchChildrenIndex)))) {
treeChildrenIndex++;
}
if (!result) {
return result;
}
}
return result;
}
private static NodeX createTestTree() {
NodeX subTree2 = new NodeX('A');
subTree2.children.add(new NodeX('A'));
subTree2.children.add(new NodeX('A'));
NodeX subTree = new NodeX('A');
subTree.children.add(new NodeX('A'));
subTree.children.add(new NodeX('A'));
subTree.children.add(subTree2);
return subTree;
}
private static NodeX createSearchTree() {
NodeX root = new NodeX('A');
root.children.add(new NodeX('A'));
root.children.add(new NodeX('A'));
return root;
}
}
class NodeX {
char value;
Vector<NodeX> children;
public NodeX(char val) {
value = val;
children = new Vector<NodeX>();
}
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append('(');
sb.append(value);
for (NodeX child : children) {
sb.append(' ');
sb.append(child.toString());
}
sb.append(')');
return sb.toString();
}
}
上記のコードは、次のすべてのサブグラフを見つけようとします。
A
/|\
A A A
/ \
A A
一致するもの:
A
/ \
A A
コードは、最初のツリーの最上位ノードと最初のツリーの 3 番目の子をルートとする一致があることを正常に検出します。ただし、実際には、1 つだけではなく、最上位ノードに根ざした 3 つの一致があります。さらに、コードはツリー内のノードとサブツリー内のノード間のマッピングを構築せず、これを行う方法がわかりません。
誰でもこれを行う方法についてアドバイスを提供できますか?