---

一、樹的同構

樹的同構是一個重要的概念，以下是關于樹的同構的詳細定義：

1. 定義

給定兩棵樹$T1$和$T2$，如果$T1$可以通過若干次左右孩子互換就變成$T2$，則稱這兩棵樹是“同構”的。這意味著，兩棵樹中的每兩個對應結點的孩子必須相同，但左右位置可以不一樣。

2. 具體理解

(1) 結點對應

兩棵樹中的結點需要一一對應，即每一個結點都有一個與之對應的結點，且這些對應結點的值需要相等。

(2) 孩子相同

對應結點的孩子（即子結點）必須相同，也就是說，對應結點左孩子和右孩子的數量和值都要相等，但它們的左右位置可以互換。

(3) 遞歸性質

由于樹是遞歸定義的，因此樹的同構也具有遞歸性質。即，如果兩棵樹的根結點對應，且它們的左子樹和右子樹（不考慮左右順序）分別同構，則這兩棵樹就是同構的。

3. 示例

例如，有以下兩棵樹：

• 樹$A$：根結點為$1$，左子結點為$2$，右子結點為$3$。
• 樹$B$：根結點為$1$，左子結點為$3$，右子結點為$2$。

雖然樹$A$和樹$B$的左右子結點位置不同，但它們的根結點值相同，且左子結點和右子結點的值也相同（只是位置互換），因此可以認為這兩棵樹是同構的。

綜上所述，樹的同構是一個基于結點對應和孩子相同（左右位置可互換）的遞歸概念。

二、樹哈希

樹哈希（Tree Hash）是對樹形數據結構進行哈希處理的一種方法。以下是對樹哈希的詳細解釋：

1.定義

樹哈希是一種哈希算法，它通過對樹形數據結構中的每個節點進行哈希計算，并將這些哈希值組合起來，以生成整個樹的唯一哈希值。這個哈希值可以作為樹的“數字指紋”，用于快速比較兩棵樹是否相同或檢測樹的修改。

2.哈希過程

（1）葉節點哈希

首先，對樹中的每個葉節點進行哈希計算，生成葉節點的哈希值。這些哈希值通常作為葉節點的標簽或標識符。

（2）非葉節點哈希

對于非葉節點（包括中間節點和根節點），它們的哈希值是通過對其子節點的哈希值進行進一步哈希計算得到的。具體來說，可以將子節點的哈希值作為輸入，應用哈希函數來生成非葉節點的哈希值。

（3）組合哈希值

在生成非葉節點的哈希值時，通常需要按照一定的順序或規則來組合其子節點的哈希值。這可以確保哈希值的唯一性和一致性。

3.性質

（1）$\text{唯一性}$

對于不同的樹形數據結構，即使它們包含相同的節點和邊，但只要結構不同（例如節點的排列順序不同），它們的哈希值也將不同。

（2）快速比較

通過比較兩棵樹的哈希值，可以快速判斷它們是否相同。如果哈希值相同，則兩棵樹在結構上必然相同；如果哈希值不同，則兩棵樹在結構上必然不同。

（3）檢測修改

哈希值對樹的修改非常敏感。即使對樹中的某個節點進行微小的修改（例如更改節點的值或添加/刪除節點），也會導致整個樹的哈希值發生變化。

4.應用

例如算法優化，在算法設計中，樹哈希可以用于優化某些算法的性能。例如，在字符串匹配算法中，可以使用樹哈希來快速比較兩個字符串的子串是否相同。

5.示例

假設有以下樹形數據結構：

我們可以按照以下步驟計算整個樹的哈希值：

（1）first step

計算葉節點$D$、$E$、$C$的哈希值，分別記為$H(D)$、$H(E)$、$H(C)$。

（2）second step

計算非葉節點$B$的哈希值，可以使用$H(B)=Hash(H(D)+H(E))$（這里的“$+$”表示哈希值的組合方式，可以是拼接、異或等操作）。

（3）third step

計算根節點$A$的哈希值，可以使用$H(A)=Hash(H(B)+H(C))$。

最終，整個樹的哈希值就是$H(A)$。

綜上所述，樹哈希是一種強大的工具，可以用于快速比較和檢測樹形數據結構的完整性和一致性。