樹哈希，顧名思義，對(duì)樹進(jìn)行哈希，經(jīng)常判斷兩個(gè)樹是否同構(gòu)。一下均為對(duì)有根樹的算法，而無(wú)根樹只需要找重心。

我們有時(shí)需要判斷一些樹是否同構(gòu)。這時(shí)，選擇恰當(dāng)?shù)墓７绞絹?lái)將樹映射成一個(gè)便于儲(chǔ)存的哈希值（一般是 32 位或 64 位整數(shù)）是一個(gè)優(yōu)秀的方案。

樹哈希有很多種哈希方式，下面將選出幾種較為常用的方式來(lái)加以介紹。

方法一

公式

注意：

其中為以節(jié)點(diǎn) x 為根的子樹對(duì)應(yīng)的哈希值。特殊地，我們令葉子節(jié)點(diǎn)的哈希值為 1。

表示以節(jié)點(diǎn) x 為根的子樹大小。

表示 x 所有子節(jié)點(diǎn)以 f 作為關(guān)鍵字排序后排名第 i 的兒子。

為選定的一個(gè)合適的種子（最好是質(zhì)數(shù)，對(duì)字符串 hash 有了解的人一定不陌生）

上述哈希過(guò)程中，可以適當(dāng)取模避免溢出或加快運(yùn)行速度。

Hack

上圖中，可以計(jì)算出兩棵樹的哈希值均為。

方法二

公式

注意：

其中為以節(jié)點(diǎn) x 為根的子樹對(duì)應(yīng)的哈希值。特殊地，我們令葉子節(jié)點(diǎn)的哈希值為 1。

表示以節(jié)點(diǎn) x 為根的子樹大小。

表示 x 所有子節(jié)點(diǎn)之一（不用排序）。

為選定的一個(gè)合適的質(zhì)數(shù)。

表示異或和。

Hack

由于異或的性質(zhì)，如果一個(gè)節(jié)點(diǎn)下有多棵本質(zhì)相同的子樹，這種哈希值將無(wú)法分辨該種子樹出現(xiàn)1,3,5,…次的情況。

方法三

公式

注意：

其中為以節(jié)點(diǎn) x 為根的子樹對(duì)應(yīng)的哈希值。

表示以節(jié)點(diǎn) x 為根的子樹大小。

表示 x 所有子節(jié)點(diǎn)之一（不用排序）。

表示第 i 個(gè)質(zhì)數(shù)。

事實(shí)上，樹哈希是可以很靈活的，可以有各種各樣奇怪的姿勢(shì)來(lái)進(jìn)行 hash，只需保證充分性與必要性，選手完全可以設(shè)計(jì)出與上述方式不同的 hash 方式。