poj-1635 Subway tree systems（判断两个有根树是否同构）-哈希法(二)
}
else
{
System.out.println("different");
}
}
}
public static int hash(Node tree,int j)
{
int sum=h[j+5000];//j是树的高度
for(Node n:tree.children)
sum=(sum+h[j]*hash(n,j+1))%m;//把子树的哈希值加到父节点上去
return (sum*sum)%m;
}
private static Node createTree(String s) {
char[] seq=s.toCharArray();
Node root=new Node(0);
Node p=root;
int index=1;
for(int i=0;i
{
if(seq[i]=='0')
{
Node node =new Node(index++);
connect(p,node);
p=node;
}
else if(seq[i]=='1')
{
p=p.parent;
}
}
//if(p==root)
// System.out.println("create success!");
return root;
}
private static void connect(Node p, Node node) {
node.parent=p;
p.children.add(node);
}
public static void displayTree(Node tree)
{
System.out.println(tree);
for(Node ch:tree.children)
displayTree(ch);
}
}
class Node
{
int id;
Node parent=null;
List children=new ArrayList();
public Node(int n)
{
id=n;
}
public String toString()
{
StringBuilder sb=new StringBuilder();
sb.append(id).append(": ");
for(Node n:children)
sb.append(n.id).append(" ");
return sb.toString();
}
}