简单的方法来找到子树的树 [英] Easy way to find Subtree in a Tree

问题描述

我在写一个使用树约code（正则树，可以有无限数量的节点，但没有交叉，即两家母公司节点不会指向同一个子节点）。无论如何，两件事情：

I'm writing some code that uses a Tree (a regular tree that can have an unlimited number of nodes, but no crossover, i.e. two parent nodes will not point the the same child node). Anyway, two things:

1）是否有任何众所周知的算法为一个树内找到一个子树

1) Are there any well-known algorithms for finding a sub-tree within a tree.

2）是否有任何Java库（或已实现该算法的任何图书馆的这个问题）？即使有没有，任何人都可以提出任何好的通用的Java树库？

2) Are there any Java libraries (or any libraries for that matter) that already implement this algorithm? Even if there are none, can anyone recommend any good general purpose Java tree library?

我要用于保存数据以树的形式，而不是为他们的搜索能力这些树。

I want to use these trees for holding data in a tree format, not for their searching capabilities.

要拓展了一下：我使用的树作为游戏的一部分，以保持当某个事件发生的事情会发生的历史。例如，一个可以打A，B，可以打两个A的，可以撞到了另外两个A等。

To expand a bit: I'm using the tree as part of game to keep a history of what happens when a certain events happen. For example, an A can hit a B which can hit two A's which can hit another two A's etc.

这看起来是这样的：

    A
    |
    B
   /
  A 
 / \  
A   A
   / \
  A   A

当然，还有多只A和B.我想要做的是（对于成就系统）是能够告诉时，说了一个先后命中2 A的：

Of course there's more than just A and B. What I want to do is (for an achievement system) is be able to tell when, say an A has hit two A's:

  A
 / \
A   A

我希望能够很容易地知道，如果在第一树包含该子树。我不希望有写所有的code这样做，如果我没有：）

I want to be able to easily know if the first tree contains that subtree. And I don't want to have to write all the code for doing so if I don't have to :)

推荐答案

看起来像一个简单的算法：查找搜索树的根在比赛中的树，并检查搜索树的孩子是否是孩子的一个子集博弈树。

Looks like a straightforward algorithm: Find the root of the search tree in the game tree and check whether the children of the search tree are a subset of the children in the game tree.

从你的解释，我不知道是否搜索树

From your explanations, I'm not sure whether the search tree

  A
 / \
A   A

应符合的树：

should match this tree:

  A
 /|\
A C A

（即如果不匹配的儿童都应该被忽略。）

(i.e. if non-matching children are supposed to be ignored.)

总之，这里的code我只是玩弄周围。这是一个完全运行的例子，并配备了一个主要方法和一个简单的节点类。随意发挥它：

Anyway, here's the code I just toyed around with. It's a fully running example and comes with a main method and a simple Node class. Feel free to play with it:

import java.util.Vector;

public class PartialTreeMatch {
    public static void main(String[] args) {
    	Node testTree = createTestTree();
    	Node searchTree = createSearchTree();

    	System.out.println(testTree);
    	System.out.println(searchTree);

    	partialMatch(testTree, searchTree);
    }

    private static boolean partialMatch(Node tree, Node searchTree) {
    	Node subTree = findSubTreeInTree(tree, searchTree);
    	if (subTree != null) {
    		System.out.println("Found: " + subTree);
    		return true;
    	}
    	return false;
    }

    private static Node findSubTreeInTree(Node tree, Node node) {
    	if (tree.value == node.value) {
    		if (matchChildren(tree, node)) {
    			return tree;
    		}
    	}

    	Node result = null;
    	for (Node child : tree.children) {
    		result = findSubTreeInTree(child, node);

    		if (result != null) {
    			if (matchChildren(tree, result)) {
    				return result;
    			}
    		}
    	}

    	return result;
    }

    private static boolean matchChildren(Node tree, Node 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 Node createTestTree() {
    	Node subTree1 = new Node('A');
    	subTree1.children.add(new Node('A'));
    	subTree1.children.add(new Node('A'));

    	Node subTree2 = new Node('A');
    	subTree2.children.add(new Node('A'));
    	subTree2.children.add(new Node('C'));
    	subTree2.children.add(subTree1);

    	Node subTree3 = new Node('B');
    	subTree3.children.add(subTree2);

    	Node root = new Node('A');
    	root.children.add(subTree3);

    	return root;
    }

    private static Node createSearchTree() {
    	Node root = new Node('A');
    	root.children.add(new Node('A'));
    	root.children.add(new Node('A'));

    	return root;
    }
}

class Node {
    char value;
    Vector<Node> children;

    public Node(char val) {
    	value = val;
    	children = new Vector<Node>();
    }

    public String toString() {
    	StringBuilder sb = new StringBuilder();

    	sb.append('(');
    	sb.append(value);

    	for (Node child : children) {
    		sb.append(' ');
    		sb.append(child.toString());
    	}

    	sb.append(')');

    	return sb.toString();
    }
}

这篇关于简单的方法来找到子树的树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！