数据结构——树的应用：哈夫曼树、并查集、二叉搜索树

树是最常用的非线性结构之一。除了基本的二叉树遍历树在编码压缩、集合合并、快速查找等场景有广泛应用。一、哈夫曼树哈夫曼树最优二叉树是带权路径长度最短的树广泛应用于数据压缩。1. 基本概念带权路径长度WPL Σ叶子节点权值 × 路径长度 最优二叉树WPL 最小的二叉树2. 构造算法1. 将 n 个节点按权值从小到大排序每个节点视为一棵树 2. 取出权值最小的两棵树合并新节点权值为两树之和 3. 将新树放回集合重复步骤 2 4. 直到只剩一棵树即为哈夫曼树举例权值集合 {5, 3, 7, 2, 9} 构造哈夫曼树的过程第一轮排序 [2, 3, 5, 7, 9] 合并 2 和 3 → 新节点 5集合变为 [5, 5, 7, 9] 第二轮排序 [5, 5, 7, 9] 合并 5 和 5 → 新节点 10集合变为 [7, 9, 10] 第三轮排序 [7, 9, 10] 合并 7 和 9 → 新节点 16集合变为 [10, 16] 第四轮合并 10 和 16 → 根节点 263. 哈夫曼编码左分支为 0右分支为 1从根到叶子的路径即为该字符的编码。classHuffmanNodeimplementsComparableHuffmanNode{intweight;charch;// 叶子节点存储的字符HuffmanNodeleft;HuffmanNoderight;publicHuffmanNode(intweight,charch){this.weightweight;this.chch;}OverridepublicintcompareTo(HuffmanNodeo){returnthis.weight-o.weight;}}publicclassHuffmanTree{publicstaticHuffmanNodebuildTree(MapCharacter,Integerfreq){PriorityQueueHuffmanNodepqnewPriorityQueue();// 1. 创建叶子节点for(Map.EntryCharacter,Integerentry:freq.entrySet()){pq.offer(newHuffmanNode(entry.getValue(),entry.getKey()));}// 2. 合并直到只剩一个节点while(pq.size()1){HuffmanNodeleftpq.poll();HuffmanNoderightpq.poll();HuffmanNodeparentnewHuffmanNode(left.weightright.weight,\0);parent.leftleft;parent.rightright;pq.offer(parent);}returnpq.poll();// 返回根节点}// 生成编码表publicstaticvoidbuildCodeTable(HuffmanNoderoot,Stringcode,MapCharacter,Stringtable){if(rootnull)return;// 叶子节点if(root.leftnullroot.rightnull){table.put(root.ch,code);return;}buildCodeTable(root.left,code0,table);buildCodeTable(root.right,code1,table);}}4. 编码与解码publicclassHuffmanCode{/** * 编码字符串 → 二进制串 * 假设已有编码表 table */publicstaticStringencode(Stringtext,MapCharacter,Stringtable){StringBuildersbnewStringBuilder();for(charc:text.toCharArray()){sb.append(table.get(c));}returnsb.toString();}/** * 解码二进制串 → 字符串 */publicstaticStringdecode(Stringcode,HuffmanNoderoot){StringBuildersbnewStringBuilder();HuffmanNodecurrentroot;for(charbit:code.toCharArray()){if(bit0){currentcurrent.left;}else{currentcurrent.right;}if(current.leftnullcurrent.rightnull){sb.append(current.ch);currentroot;// 回到根节点继续解码}}returnsb.toString();}}5. 应用场景哈夫曼树的应用 1. 文件压缩ZIP、RAR 中的压缩算法之一 2. 图像编码JPEG 中的 Huffman 编码 3. 网络传输HTTP 中的 HPACK 压缩二、并查集并查集用于处理不相交集合的合并和查找问题时间复杂度接近 O(1)。1. 核心思想classUnionFind{privateint[]parent;// 父节点数组privateint[]rank;// 秩高度publicUnionFind(intn){parentnewint[n];ranknewint[n];for(inti0;in;i){parent[i]i;// 每个节点的父节点初始为自己rank[i]0;}}/** * 查找找到元素的根节点路径压缩 */publicintfind(intx){if(parent[x]!x){parent[x]find(parent[x]);// 路径压缩}returnparent[x];}/** * 合并将两个元素所在的集合合并按秩合并 */publicvoidunion(intx,inty){introotXfind(x);introotYfind(y);if(rootXrootY)return;// 按秩合并树矮的挂到树高的下面if(rank[rootX]rank[rootY]){parent[rootX]rootY;}elseif(rank[rootX]rank[rootY]){parent[rootY]rootX;}else{parent[rootY]rootX;rank[rootX];}}/** * 判断两个元素是否属于同一集合 */publicbooleanisConnected(intx,inty){returnfind(x)find(y);}/** * 获取集合数量 */publicintcount(){SetIntegerrootsnewHashSet();for(inti0;iparent.length;i){roots.add(find(i));}returnroots.size();}}2. 优化技巧优化一路径压缩find 时优化 普通查找沿着父指针一直往上找 路径压缩找到根后把路径上所有节点直接挂到根下面 优化二按秩合并union 时优化 秩小的树挂到秩大的树下面 保证树的高度不超过 O(log n) 两种优化一起用时间复杂度接近 O(1)3. 应用场景/** * 场景一判断图是否连通 * 将所有边 union最后检查所有节点是否同一集合 */publicbooleanisConnectedGraph(intn,int[][]edges){UnionFindufnewUnionFind(n);for(int[]edge:edges){uf.union(edge[0],edge[1]);}for(inti1;in;i){if(!uf.isConnected(0,i))returnfalse;}returntrue;}/** * 场景二Kruskal 最小生成树 * 按边权排序从小到大 union避免形成环 */三、二叉搜索树复习与应用1. 查找前驱和后继publicclassBSTOperations{/** * 查找前驱小于当前节点的最大值 */publicTreeNodepredecessor(TreeNoderoot,intval){TreeNodenodesearch(root,val);if(nodenull)returnnull;// 如果有左子树取左子树的最大值if(node.left!null){TreeNodecurnode.left;while(cur.right!null)curcur.right;returncur;}// 否则向上找找到第一个右转的节点TreeNodepredecessornull;while(root!node){if(node.valroot.val){predecessorroot;rootroot.right;}else{rootroot.left;}}returnpredecessor;}/** * 查找后继大于当前节点的最小值 */publicTreeNodesuccessor(TreeNoderoot,intval){TreeNodenodesearch(root,val);if(nodenull)returnnull;// 如果有右子树取右子树的最小值if(node.right!null){TreeNodecurnode.right;while(cur.left!null)curcur.left;returncur;}// 否则向上找找到第一个左转的节点TreeNodesuccessornull;while(root!node){if(node.valroot.val){successorroot;rootroot.left;}else{rootroot.right;}}returnsuccessor;}privateTreeNodesearch(TreeNoderoot,intval){if(rootnull||root.valval)returnroot;returnvalroot.val?search(root.left,val):search(root.right,val);}}2. 验证二叉搜索树/** * 判断一棵树是否是合法的 BST * 思路中序遍历检查是否严格递增 */publicbooleanisValidBST(TreeNoderoot){ListIntegerinordernewArrayList();inorderTraversal(root,inorder);for(inti1;iinorder.size();i){if(inorder.get(i)inorder.get(i-1)){returnfalse;}}returntrue;}privatevoidinorderTraversal(TreeNoderoot,ListIntegerresult){if(rootnull)return;inorderTraversal(root.left,result);result.add(root.val);inorderTraversal(root.right,result);}3. 区间查找/** * 查找 BST 中所有在 [low, high] 范围内的节点值 * 利用 BST 性质剪枝 */publicListIntegerrangeSearch(TreeNoderoot,intlow,inthigh){ListIntegerresultnewArrayList();rangeSearchHelper(root,low,high,result);returnresult;}privatevoidrangeSearchHelper(TreeNodenode,intlow,inthigh,ListIntegerresult){if(nodenull)return;// 当前节点值在范围内才加入if(node.vallow){rangeSearchHelper(node.left,low,high,result);}if(node.vallownode.valhigh){result.add(node.val);}if(node.valhigh){rangeSearchHelper(node.right,low,high,result);}}四、408 考研常见考题题1哈夫曼树带权路径长度叶子节点权值 {2, 3, 5, 7, 9} 的哈夫曼树 WPL 2×3 3×3 5×2 7×2 9×2 69101418 57题2并查集查找次数在 n 个元素的并查集中进行 m 次 find 操作 路径压缩 按秩合并后总时间复杂度 O(m α(n)) α(n) 是阿克曼函数的反函数增长极慢 n ≤ 宇宙原子数量时α(n) ≤ 5题3BST 删除节点删除叶子节点直接删除 删除有一个子树的节点子节点替换父节点 删除有两个子树的节点用前驱或后继替换总结哈夫曼树 → WPL 最小用于压缩编码 并查集 → 快速合并和查找用于连通性问题 二叉搜索树 → 动态查找O(log n) 平均性能408 重点哈夫曼树构造和 WPL 计算、并查集的路径压缩和按秩合并、BST 的删除操作。 觉得有用的话点赞 关注【张老师技术栈】吧每周更新 Java/Python/爬虫 实战干货不让你白来。