根付いたツリーを効率的にハッシュする方法もいくつかあります。
これらの方法の 1 つは次のように整理されます。
深さのトラバースの順序で頂点を再帰的に処理します。単一の頂点のハッシュが p に等しいと仮定します。子を持つ頂点の場合、最初にそれらのアルゴリズムを実行し、次に子を通じて現在のサブツリーのハッシュを計算します。これを行うには、子のサブツリーのハッシュを一連の数値とみなして、このシーケンスからハッシュを計算します。これは現在のサブツリーのハッシュになります。
子の順序が重要でない場合は、ハッシュを計算する前に、子のサブツリーからハッシュのシーケンスを並べ替え、並べ替えられたシーケンスからハッシュを計算します。
このようにして、ツリーの同型性をチェックできます。子のハッシュを順序なしでカウントするだけです (つまり、子のハッシュをソートするたびに)。そして、ルートのハッシュが一致する場合、ツリーは同型であり、一致しない場合は一致しません。
根のない木の場合、すべてが同様の方法で起こりますが、重心を根と見なす必要があります。または、重心が 2 つある場合は、ハッシュのペアを検討します。