当前位置：首页 > C > 正文

树的指纹识别术（C语言实现树哈希算法详解）

主机测评网
C
2025-12-03
317

在计算机科学中，我们经常需要判断两棵树是否“相同”——不仅是结构相同，节点值也要一致。暴力比较虽然可行，但效率低下。这时，“树哈希”就派上用场了！本文将用通俗易懂的方式，手把手教你用C语言实现树哈希算法，即使是编程小白也能轻松掌握。

什么是树哈希？

树哈希（Tree Hashing）是一种将整棵树映射为一个唯一（或高概率唯一）的整数（称为“哈希值”）的技术。如果两棵树的哈希值相同，那么它们极大概率是相同的树。这就像给每棵树生成一个“数字指纹”。

为什么需要树哈希？

快速判断两棵树是否相同（O(1) 比较哈希值 vs O(n) 遍历比较）
在竞赛编程中优化子树匹配问题
作为更复杂算法（如树同构判定）的基础

核心思想

树哈希的核心思想是：自底向上计算每个子树的哈希值。一个节点的哈希值由它自身的值和所有子节点的哈希值共同决定。

常用公式（以二叉树为例）：

hash(node) = (val + P * hash(left) + Q * hash(right)) % MOD

其中：

val 是当前节点的值
hash(left) 和 hash(right) 是左右子树的哈希值
P、Q 是两个大质数（用于打乱顺序，避免冲突）
MOD 是一个大质数（防止哈希值溢出）

C语言实现步骤

下面我们用 C 语言一步步实现这个算法。

1. 定义树节点结构

typedef struct TreeNode { int val; struct TreeNode* left; struct TreeNode* right;} TreeNode;

2. 选择合适的常量

#define MOD 1000000007  // 大质数，防止溢出#define P   131         // 左子树权重#define Q   137         // 右子树权重

3. 编写递归哈希函数

unsigned long long treeHash(TreeNode* root) {    if (root == NULL) {        return 1; // 空树返回固定值（不能为0，否则会丢失结构信息）    }    unsigned long long leftHash  = treeHash(root->left);    unsigned long long rightHash = treeHash(root->right);    // 计算当前节点的哈希值    unsigned long long hash = root->val;    hash = (hash + P * leftHash) % MOD;    hash = (hash + Q * rightHash) % MOD;    return hash;}

4. 使用示例

#include <stdio.h>#include <stdlib.h>// ... 上面的定义和函数 ...int main() {    // 构建第一棵树    TreeNode* t1 = malloc(sizeof(TreeNode));    t1->val = 1;    t1->left = malloc(sizeof(TreeNode));    t1->left->val = 2;    t1->left->left = t1->left->right = NULL;    t1->right = NULL;    // 构建第二棵树（与第一棵相同）    TreeNode* t2 = malloc(sizeof(TreeNode));    t2->val = 1;    t2->left = malloc(sizeof(TreeNode));    t2->left->val = 2;    t2->left->left = t2->left->right = NULL;    t2->right = NULL;    unsigned long long h2 = treeHash(t1);    unsigned long long h2 = treeHash(t2);    if (h2 == h2) {        printf("两棵树相同！哈希值：%llu\n", h2);    } else {        printf("两棵树不同。\n");    }    return 0;}