树在实际应用中最常出现的三种形态二叉排序树快速查找、平衡二叉树高效查找、哈夫曼树数据压缩。这篇把完整实现和 408 考点讲透。一、二叉排序树BST二叉排序树Binary Search Tree的性质左子树所有节点值 根节点值右子树所有节点值 根节点值左右子树也分别是二叉排序树8 / \ 3 10 / \ \ 1 6 14 / \ 4 71. 查找publicTreeNodesearchBST(TreeNoderoot,intval){if(rootnull||root.valval){returnroot;}if(valroot.val){returnsearchBST(root.left,val);}else{returnsearchBST(root.right,val);}}2. 插入publicTreeNodeinsertBST(TreeNoderoot,intval){if(rootnull){returnnewTreeNode(val);}if(valroot.val){root.leftinsertBST(root.left,val);}elseif(valroot.val){root.rightinsertBST(root.right,val);}// 等于时不处理BST 中不允许重复returnroot;}3. 删除删除是 BST 最复杂的操作分三种情况publicTreeNodedeleteBST(TreeNoderoot,intval){if(rootnull)returnnull;// 查找要删除的节点if(valroot.val){root.leftdeleteBST(root.left,val);}elseif(valroot.val){root.rightdeleteBST(root.right,val);}else{// 找到要删除的节点// 情况1叶子节点无子节点if(root.leftnullroot.rightnull){returnnull;}// 情况2只有一个子节点if(root.leftnull){returnroot.right;}if(root.rightnull){returnroot.left;}// 情况3有两个子节点// 用右子树的最小节点或左子树的最大节点替换TreeNodeminfindMin(root.right);root.valmin.val;root.rightdeleteBST(root.right,min.val);}returnroot;}privateTreeNodefindMin(TreeNoderoot){while(root.left!null){rootroot.left;}returnroot;}4. 性能分析最好情况完全平衡的树 → O(log n) 最坏情况退化成链表 → O(n) 比如按 {1,2,3,4,5} 顺序插入树变成一条右斜链二、平衡二叉树AVL1. 为什么需要 AVL二叉排序树在最坏情况下退化成链表查找变成 O(n)。AVL 树通过旋转保持平衡保证查找效率始终是 O(log n)。平衡因子 左子树高度 - 右子树高度 |平衡因子| ≤ 1 → 平衡 |平衡因子| 1 → 需要旋转2. AVL 节点定义classAVLNode{intval;AVLNodeleft;AVLNoderight;intheight;// 节点高度AVLNode(intval){this.valval;this.height1;}}3. 四种旋转LL 型左左——右旋y x / \ 右旋 / \ x C → A y / \ / \ A B B CRR 型右右——左旋x y / \ 左旋 / \ A y → x C / \ / \ B C A BLR 型左右——先左旋再右旋y 先左旋 x y 再右旋 y z / \ → / \ → / \ x C z C x y / \ / \ / \ / \ A z x B A B C ? / \ / \ B ? A ?RL 型右左——先右旋再左旋x 先右旋 y x 再左旋 x z / \ → / \ → / \ A y A z x y / \ / \ / \ / \ z C B y A B C ? / \ / \ B ? C ?4. AVL 插入完整实现classAVLTree{// 获取节点高度privateintheight(AVLNodenode){returnnodenull?0:node.height;}// 获取平衡因子privateintgetBalance(AVLNodenode){returnnodenull?0:height(node.left)-height(node.right);}// 更新高度privatevoidupdateHeight(AVLNodenode){node.heightMath.max(height(node.left),height(node.right))1;}// 右旋privateAVLNoderightRotate(AVLNodey){AVLNodexy.left;AVLNodeT2x.right;// 旋转x.righty;y.leftT2;// 更新高度updateHeight(y);updateHeight(x);returnx;}// 左旋privateAVLNodeleftRotate(AVLNodex){AVLNodeyx.right;AVLNodeT2y.left;y.leftx;x.rightT2;updateHeight(x);updateHeight(y);returny;}// 插入publicAVLNodeinsert(AVLNodenode,intval){// 1. 普通 BST 插入if(nodenull){returnnewAVLNode(val);}if(valnode.val){node.leftinsert(node.left,val);}elseif(valnode.val){node.rightinsert(node.right,val);}else{returnnode;// 不插入重复值}// 2. 更新高度updateHeight(node);// 3. 检查平衡因子intbalancegetBalance(node);// 4. 四种不平衡情况// LLif(balance1valnode.left.val){returnrightRotate(node);}// RRif(balance-1valnode.right.val){returnleftRotate(node);}// LRif(balance1valnode.left.val){node.leftleftRotate(node.left);returnrightRotate(node);}// RLif(balance-1valnode.right.val){node.rightrightRotate(node.right);returnleftRotate(node);}returnnode;}}5. 验证 AVL 树publicbooleanisBalanced(AVLNoderoot){if(rootnull)returntrue;intlhheight(root.left);intrhheight(root.right);returnMath.abs(lh-rh)1isBalanced(root.left)isBalanced(root.right);}三、哈夫曼树最优二叉树1. 基本概念树的带权路径长度WPL Σ 叶子节点权值 × 路径长度 WPL 最小的二叉树称为哈夫曼树最优二叉树2. 构造算法1. 将 n 个节点按权值排序每个节点视为一棵树 2. 取出权值最小的两棵树合并 3. 新节点权值 两树权值之和 4. 重复步骤 2-3直到只剩一棵树举例权值 {2, 3, 5, 7, 9}第一轮合并 2 和 3 → 5 → {5, 5, 7, 9} 第二轮合并 5 和 5 → 10 → {7, 9, 10} 第三轮合并 7 和 9 → 16 → {10, 16} 第四轮合并 10 和 16 → 26 → {26} WPL 2×3 3×3 5×2 7×2 9×2 573. 完整实现classHuffmanNodeimplementsComparableHuffmanNode{intweight;charch;// 叶子节点存储的字符HuffmanNodeleft;HuffmanNoderight;HuffmanNode(intweight,charch){this.weightweight;this.chch;}OverridepublicintcompareTo(HuffmanNodeo){returnthis.weight-o.weight;}}publicclassHuffmanTree{publicstaticHuffmanNodebuildTree(MapCharacter,Integerfreq){PriorityQueueHuffmanNodepqnewPriorityQueue();// 1. 创建叶子节点for(Map.EntryCharacter,Integere:freq.entrySet()){pq.offer(newHuffmanNode(e.getValue(),e.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. 哈夫曼编码左分支为0右分支为1 从根到叶子的路径即为该字符的编码 特点 前缀编码任何一个编码不是另一个编码的前缀 压缩率出现频率越高的字符编码越短四、408 考研经典考题题1BST 查找长度一棵 BST 有 10 个节点查找成功的最小比较次数 最好情况根节点 → 1 次 最坏情况最深层叶子 → h 次h 是树高 平均情况与树形有关 完全二叉树ASL ≈ (1×1 2×2 4×3 3×4) / 10 2.9题2AVL 插入过程依次插入 {3, 2, 1, 4, 5, 6, 7} 插3: [3] 插2: [3(左2)] 平衡 插1: [3(左2(左1))] 平衡因子2 → LL右旋 → [2(左1)(右3)] 插4: [2(左1)(右3(右4))] 平衡 插5: [2(左1)(右3(右4(右5)))] → 3的平衡因子-2 → RR左旋 → [2(左1)(右4(左3)(右5))]题3哈夫曼编码字符 A B C D E 出现频率 2 3 5 7 9 求各字符的哈夫曼编码 构造过程同上结果 A: 010 → 2位 B: 011 → 3位 C: 00 → 2位 D: 10 → 2位 E: 11 → 2位 总编码长度 2×3 3×3 5×2 7×2 9×2 57 平均编码长度 57 / (23579) 57/26 ≈ 2.19五、三种树的对比类型查找插入删除适用场景BSTO(n)~O(log n)O(n)~O(log n)O(n)~O(log n)动态查找数据不固定AVLO(log n)O(log n)O(log n)频繁查找对效率要求高哈夫曼树———数据压缩编码总结二叉排序树 → 快速查找但可能退化成链表 平衡二叉树 → 通过旋转保持 O(log n)插入删除稍复杂 哈夫曼树 → WPL 最小用于压缩编码408 重点BST 的删除操作、AVL 的四种旋转判断、哈夫曼树的 WPL 计算和编码。 觉得有用的话点赞 关注【张老师技术栈】吧每周更新 Java/Python/爬虫 实战干货不让你白来。