二叉树通关指南：从底层逻辑到实战落地，一篇吃透！

果酱带你啃java

发布于 2026-04-14 13:45:15

370

二叉树通关指南：从底层逻辑到实战落地，一篇吃透！

如果你是程序员，一定绕不开“二叉树”这个话题——它是算法面试的“常客”，是数据库索引（B+树）的底层基础，更是MyBatisPlus、Spring等框架中树形结构处理的核心逻辑。但很多人学二叉树时总觉得“抽象难懂”，要么卡在递归遍历，要么搞不清平衡树的旋转规则。今天，我们就用“人话”拆解二叉树的所有核心知识点，从概念到代码，从理论到实战，让你彻底搞懂它！

一、二叉树是什么？先把基础概念掰明白

1.1 二叉树的本质：“分岔”的节点结构

二叉树是一种非线性数据结构，每个节点最多只有两个“孩子”（左孩子、右孩子），就像树杈分了两个叉。我们可以用生活中的“家谱”类比：

根节点：家谱里的“老祖宗”，是树的起点（没有父节点）；
叶子节点：家谱里的“晚辈”，没有孩子的节点；
节点的度：一个节点有几个孩子（二叉树中最多为2）；
树的深度：从根节点到最远叶子节点的“步数”（比如根是深度1，根的孩子是深度2）；
树的高度：从叶子节点到根节点的“步数”（和深度方向相反，叶子节点高度为0）。

1.2 二叉树的分类：别搞混这些“变种”

普通二叉树：每个节点最多两个孩子，没有其他限制；
完全二叉树：除了最后一层，其他层节点都满，最后一层从左到右排满；
满二叉树：所有层的节点都排满（完全二叉树的“顶配版”）；
二叉搜索树（BST）：左子树所有节点值 < 根节点值，右子树所有节点值 > 根节点值（查询效率高）；
平衡二叉树（AVL/红黑树）：解决BST退化成链表的问题，保证树的“高度差”可控。

二、二叉树怎么存？两种存储方式的底层逻辑

二叉树的存储分为顺序存储（数组）和链式存储（链表），各有适用场景。

2.1 顺序存储：用数组“排座位”

顺序存储是把二叉树节点按“层序遍历”顺序存到数组里，父子节点的位置有固定公式：

若父节点下标为i，则左孩子下标 = 2i + 1，右孩子下标 = 2i + 2；
反过来，孩子节点下标为j，则父节点下标 = (j - 1) / 2（整数除法）。

举个例子：数组[1,2,3,4,5]对应的二叉树结构是：

    1（下标0）
   / \
  2（1） 3（2）
 / \
4（3）5（4）

优点：访问速度快（数组随机访问）；缺点：空间浪费（非完全二叉树会有空位）。

2.2 链式存储：用节点“搭链条”

链式存储是二叉树最常用的方式，每个节点包含“值 + 左孩子指针 + 右孩子指针”。我们用Java定义一个标准的二叉树节点类：

package com.example.binarytree.entity;

import lombok.Data;

/**
 * 二叉树节点
 * @author ken
 */
@Data
public class TreeNode<T> {
    /**
     * 节点值
     */
    private T val;
    /**
     * 左子节点
     */
    private TreeNode<T> left;
    /**
     * 右子节点
     */
    private TreeNode<T> right;

    public TreeNode(T val) {
        this.val = val;
    }
}

优点：空间利用率高（只存实际节点）；缺点：访问需要遍历指针。

三、二叉树的核心操作：遍历（递归+非递归）

遍历是二叉树的“灵魂操作”——把所有节点按规则访问一遍。主要分深度优先（DFS）和广度优先（BFS）两类，其中DFS又分前序、中序、后序。

3.1 深度优先遍历：“钻到底”再回头

3.1.1 前序遍历（根→左→右）

规则：先访问根节点，再递归遍历左子树，最后递归遍历右子树。

递归实现（简单但可能栈溢出）：

package com.example.binarytree.util;

import com.example.binarytree.entity.TreeNode;
import lombok.extern.slf4j.Slf4j;
import org.springframework.util.ObjectUtils;
import com.google.common.collect.Lists;

import java.util.List;

/**
 * 二叉树遍历工具类
 * @author ken
 */
@Slf4j
public class BinaryTreeTraversalUtil {

    /**
     * 前序遍历（递归）：根 -> 左 -> 右
     * @param node 根节点
     * @param result 存储结果的集合
     * @param <T> 节点值类型
     */
    public static <T> void preOrderRecursive(TreeNode<T> node, List<T> result) {
        if (ObjectUtils.isEmpty(node)) {
            return;
        }
        result.add(node.getVal()); // 访问根
        preOrderRecursive(node.getLeft(), result); // 左子树
        preOrderRecursive(node.getRight(), result); // 右子树
    }
}

非递归实现（用栈模拟递归，避免栈溢出）：

/**
 * 前序遍历（非递归）：栈实现
 * @param root 根节点
 * @param <T> 节点值类型
 * @return 遍历结果
 */
public static <T> List<T> preOrderIterative(TreeNode<T> root) {
    List<T> result = Lists.newArrayList();
    if (ObjectUtils.isEmpty(root)) {
        return result;
    }
    java.util.Deque<TreeNode<T>> stack = new java.util.LinkedList<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode<T> node = stack.pop();
        result.add(node.getVal()); // 访问根
        // 栈是“后进先出”，先压右孩子，再压左孩子
        if (!ObjectUtils.isEmpty(node.getRight())) {
            stack.push(node.getRight());
        }
        if (!ObjectUtils.isEmpty(node.getLeft())) {
            stack.push(node.getLeft());
        }
    }
    return result;
}

3.1.2 中序遍历（左→根→右）

规则：先递归左子树，再访问根，最后递归右子树（二叉搜索树的中序遍历是“有序序列”，这是BST的核心特性）。

递归实现：

/**
 * 中序遍历（递归）：左 -> 根 -> 右
 * @param node 根节点
 * @param result 存储结果的集合
 * @param <T> 节点值类型
 */
public static <T> void inOrderRecursive(TreeNode<T> node, List<T> result) {
    if (ObjectUtils.isEmpty(node)) {
        return;
    }
    inOrderRecursive(node.getLeft(), result); // 左子树
    result.add(node.getVal()); // 访问根
    inOrderRecursive(node.getRight(), result); // 右子树
}

非递归实现（用栈记录路径）：

/**
 * 中序遍历（非递归）：栈实现
 * @param root 根节点
 * @param <T> 节点值类型
 * @return 遍历结果
 */
public static <T> List<T> inOrderIterative(TreeNode<T> root) {
    List<T> result = Lists.newArrayList();
    if (ObjectUtils.isEmpty(root)) {
        return result;
    }
    java.util.Deque<TreeNode<T>> stack = new java.util.LinkedList<>();
    TreeNode<T> current = root;
    while (!stack.isEmpty() || !ObjectUtils.isEmpty(current)) {
        // 先走到左子树最深处
        while (!ObjectUtils.isEmpty(current)) {
            stack.push(current);
            current = current.getLeft();
        }
        current = stack.pop();
        result.add(current.getVal()); // 访问根
        current = current.getRight(); // 处理右子树
    }
    return result;
}

3.1.3 后序遍历（左→右→根）

规则：先递归左子树，再递归右子树，最后访问根。

递归实现：

/**
 * 后序遍历（递归）：左 -> 右 -> 根
 * @param node 根节点
 * @param result 存储结果的集合
 * @param <T> 节点值类型
 */
public static <T> void postOrderRecursive(TreeNode<T> node, List<T> result) {
    if (ObjectUtils.isEmpty(node)) {
        return;
    }
    postOrderRecursive(node.getLeft(), result); // 左子树
    postOrderRecursive(node.getRight(), result); // 右子树
    result.add(node.getVal()); // 访问根
}

非递归实现（用栈+标记位）：

/**
 * 后序遍历（非递归）：栈+标记位
 * @param root 根节点
 * @param <T> 节点值类型
 * @return 遍历结果
 */
public static <T> List<T> postOrderIterative(TreeNode<T> root) {
    List<T> result = Lists.newArrayList();
    if (ObjectUtils.isEmpty(root)) {
        return result;
    }
    java.util.Deque<java.util.Map.Entry<TreeNode<T>, Boolean>> stack = new java.util.LinkedList<>();
    stack.push(new java.util.AbstractMap.SimpleEntry<>(root, false));
    while (!stack.isEmpty()) {
        java.util.Map.Entry<TreeNode<T>, Boolean> entry = stack.pop();
        TreeNode<T> node = entry.getKey();
        boolean visited = entry.getValue();
        if (visited) {
            result.add(node.getVal()); // 已访问过子节点，访问根
        } else {
            stack.push(new java.util.AbstractMap.SimpleEntry<>(node, true)); // 标记为待访问
            // 后序是左→右→根，栈需反向压入：根→右→左
            if (!ObjectUtils.isEmpty(node.getRight())) {
                stack.push(new java.util.AbstractMap.SimpleEntry<>(node.getRight(), false));
            }
            if (!ObjectUtils.isEmpty(node.getLeft())) {
                stack.push(new java.util.AbstractMap.SimpleEntry<>(node.getLeft(), false));
            }
        }
    }
    return result;
}

3.2 广度优先遍历（层序遍历）：“一层一层”往下走

规则：从根节点开始，按层从上到下、从左到右访问节点（用队列实现）。

/**
 * 层序遍历（广度优先）：队列实现
 * @param root 根节点
 * @param <T> 节点值类型
 * @return 遍历结果
 */
public static <T> List<T> levelOrder(TreeNode<T> root) {
    List<T> result = Lists.newArrayList();
    if (ObjectUtils.isEmpty(root)) {
        return result;
    }
    java.util.Queue<TreeNode<T>> queue = new java.util.LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode<T> node = queue.poll();
        result.add(node.getVal()); // 访问当前层节点
        // 压入下一层节点
        if (!ObjectUtils.isEmpty(node.getLeft())) {
            queue.offer(node.getLeft());
        }
        if (!ObjectUtils.isEmpty(node.getRight())) {
            queue.offer(node.getRight());
        }
    }
    return result;
}

3.3 遍历测试：验证代码正确性

我们构造一棵测试树：

// 构建测试树：
//     1
//    / \
//   2   3
//  / \
// 4   5
TreeNode<Integer> root = new TreeNode<>(1);
root.setLeft(new TreeNode<>(2));
root.setRight(new TreeNode<>(3));
root.getLeft().setLeft(new TreeNode<>(4));
root.getLeft().setRight(new TreeNode<>(5));

// 前序遍历：[1,2,4,5,3]
List<Integer> preResult = Lists.newArrayList();
BinaryTreeTraversalUtil.preOrderRecursive(root, preResult);
log.info("前序遍历结果：{}", preResult);

// 中序遍历：[4,2,5,1,3]
List<Integer> inResult = Lists.newArrayList();
BinaryTreeTraversalUtil.inOrderRecursive(root, inResult);
log.info("中序遍历结果：{}", inResult);

// 后序遍历：[4,5,2,3,1]
List<Integer> postResult = Lists.newArrayList();
BinaryTreeTraversalUtil.postOrderRecursive(root, postResult);
log.info("后序遍历结果：{}", postResult);

// 层序遍历：[1,2,3,4,5]
List<Integer> levelResult = BinaryTreeTraversalUtil.levelOrder(root);
log.info("层序遍历结果：{}", levelResult);

运行结果完全符合预期，证明代码正确！

四、二叉搜索树（BST）：最常用的二叉树“变种”

二叉搜索树（BST）是实用价值最高的二叉树，核心规则是：

左子树所有节点值 < 根节点值；
右子树所有节点值 > 根节点值；
左右子树也必须是BST。

BST的优势是**查询、插入、删除的平均时间复杂度为O(logn)**（类似二分查找）。

4.1 BST的查找操作

逻辑：比根小往左找，比根大往右找，找到则返回，直到null则不存在。

package com.example.binarytree.service;

import com.example.binarytree.entity.TreeNode;
import lombok.extern.slf4j.Slf4j;
import org.springframework.util.ObjectUtils;

/**
 * 二叉搜索树（BST）操作服务类
 * @author ken
 */
@Slf4j
public class BinarySearchTreeService {

    /**
     * 查找BST中的节点
     * @param root 根节点
     * @param target 目标值
     * @param <T> 节点值类型（需实现Comparable接口）
     * @return 找到的节点（null表示未找到）
     */
    public static <T extends Comparable<T>> TreeNode<T> search(TreeNode<T> root, T target) {
        if (ObjectUtils.isEmpty(root) || root.getVal().compareTo(target) == 0) {
            return root;
        }
        // 目标值小于根，往左找
        if (target.compareTo(root.getVal()) < 0) {
            return search(root.getLeft(), target);
        } else {
            // 目标值大于根，往右找
            return search(root.getRight(), target);
        }
    }
}

4.2 BST的插入操作

逻辑：递归找到“空位置”——比根小往左，比根大往右，直到子节点为null时插入。

/**
 * 插入节点到BST
 * @param root 根节点
 * @param val 要插入的值
 * @param <T> 节点值类型（需实现Comparable接口）
 * @return 插入后的根节点
 */
public static <T extends Comparable<T>> TreeNode<T> insert(TreeNode<T> root, T val) {
    // 找到空位置，插入新节点
    if (ObjectUtils.isEmpty(root)) {
        return new TreeNode<>(val);
    }
    // 不插入重复值
    if (val.compareTo(root.getVal()) == 0) {
        return root;
    }
    // 小于根，往左子树插入
    if (val.compareTo(root.getVal()) < 0) {
        root.setLeft(insert(root.getLeft(), val));
    } else {
        // 大于根，往右子树插入
        root.setRight(insert(root.getRight(), val));
    }
    return root;
}

4.3 BST的删除操作（最复杂）

BST的删除分三种情况，我们逐一拆解：

情况1：删除的是叶子节点（无孩子）

直接把该节点置为null即可。

情况2：删除的节点只有一个孩子

把孩子节点“提上来”替代被删节点。

情况3：删除的节点有两个孩子

需要找后继节点（右子树中最小的节点）或前驱节点（左子树中最大的节点）替代被删节点，再删除后继/前驱节点。

/**
 * 删除BST中的节点
 * @param root 根节点
 * @param val 要删除的值
 * @param <T> 节点值类型（需实现Comparable接口）
 * @return 删除后的根节点
 */
public static <T extends Comparable<T>> TreeNode<T> delete(TreeNode<T> root, T val) {
    if (ObjectUtils.isEmpty(root)) {
        return null;
    }
    // 找到要删除的节点
    if (val.compareTo(root.getVal()) < 0) {
        root.setLeft(delete(root.getLeft(), val));
    } else if (val.compareTo(root.getVal()) > 0) {
        root.setRight(delete(root.getRight(), val));
    } else {
        // 情况1：叶子节点
        if (ObjectUtils.isEmpty(root.getLeft()) && ObjectUtils.isEmpty(root.getRight())) {
            return null;
        }
        // 情况2：只有一个孩子
        else if (ObjectUtils.isEmpty(root.getLeft())) {
            return root.getRight();
        } else if (ObjectUtils.isEmpty(root.getRight())) {
            return root.getLeft();
        }
        // 情况3：有两个孩子，找后继节点（右子树最小）
        else {
            TreeNode<T> successor = findMin(root.getRight());
            root.setVal(successor.getVal()); // 替换值
            root.setRight(delete(root.getRight(), successor.getVal())); // 删除后继
        }
    }
    return root;
}

/**
 * 查找树中最小节点（用于找后继）
 * @param node 节点
 * @param <T> 节点值类型（需实现Comparable接口）
 * @return 最小节点
 */
private static <T extends Comparable<T>> TreeNode<T> findMin(TreeNode<T> node) {
    while (!ObjectUtils.isEmpty(node.getLeft())) {
        node = node.getLeft();
    }
    return node;
}

4.4 BST的缺陷：可能退化成链表

如果插入的是有序数据（如1→2→3→4→5），BST会退化成“链表”，此时查询复杂度从O(logn)变成O(n)。为了解决这个问题，平衡二叉树应运而生。

五、平衡二叉树：让BST“站得稳”

平衡二叉树的核心目标是：让树的左右子树高度差不超过1，避免退化成链表。常见的平衡树有AVL树和红黑树。

5.1 AVL树：严格平衡的二叉树

AVL树是最早的平衡二叉树，定义是：每个节点的左右子树高度差（平衡因子）的绝对值 ≤ 1（平衡因子=右子树高度-左子树高度）。

如果插入/删除导致平衡因子>1，需要通过旋转来调整：

右旋：左子树过高时使用（把左孩子变成根，原根变成右孩子）；
左旋：右子树过高时使用（把右孩子变成根，原根变成左孩子）；
左右旋：左子树的右子树过高时，先左旋左子树，再右旋根；
右左旋：右子树的左子树过高时，先右旋右子树，再左旋根。

右旋示例（左子树过高）：

flowchart TD A[3] --> B[2] B --> C[1] B --> D[null] A --> E[null] --> B[2] --> C[1] B --> A[3] A --> E[null] A --> D[null]

5.2 红黑树：近似平衡的二叉树

AVL树的旋转太频繁（每次插入/删除都要调整），红黑树做了“妥协”——不追求严格平衡，而是通过“颜色规则”保证近似平衡：

每个节点要么红，要么黑；
根节点是黑的；
叶子节点（NIL节点）是黑的；
红节点的子节点必须是黑的（不能有连续红节点）；
从根到任意叶子的路径上，黑节点数量相同。

红黑树的优势是旋转次数少（插入最多2次旋转，删除最多3次），因此在HashMap（JDK8+）、TreeMap等场景中广泛使用。

5.3 AVL vs 红黑树：怎么选？

AVL：查询更快（更平衡），但插入/删除慢（旋转多）；
红黑树：插入/删除更快（旋转少），查询略慢（近似平衡）；
工程中优先选红黑树（综合性能更好）。

六、实战落地：二叉树在业务中的应用

6.1 树形结构构建：部门树/菜单树

业务中经常需要处理“层级结构”（如部门树、菜单树），本质是二叉树层序遍历的扩展（多叉树）。我们用MyBatisPlus实现部门树的构建：

第一步：创建部门表（MySQL8.0）

CREATE TABLE `sys_dept` (
  `id` bigint NOT NULL AUTO_INCREMENT COMMENT '部门ID',
  `dept_name` varchar(50) NOT NULL COMMENT '部门名称',
  `parent_id` bigint DEFAULT 0 COMMENT '父部门ID（0为根部门）',
  `sort` int DEFAULT 0 COMMENT '排序',
  `create_time` datetime DEFAULT CURRENT_TIMESTAMP COMMENT '创建时间',
  `update_time` datetime DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '更新时间',
  PRIMARY KEY (`id`) USING BTREE,
  KEY `idx_parent_id` (`parent_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COMMENT='部门表';

-- 插入测试数据
INSERT INTO `sys_dept` (`dept_name`, `parent_id`, `sort`) VALUES ('总公司', 0, 0);
INSERT INTO `sys_dept` (`dept_name`, `parent_id`, `sort`) VALUES ('技术部', 1, 1);
INSERT INTO `sys_dept` (`dept_name`, `parent_id`, `sort`) VALUES ('产品部', 1, 2);
INSERT INTO `sys_dept` (`dept_name`, `parent_id`, `sort`) VALUES ('后端组', 2, 1);
INSERT INTO `sys_dept` (`dept_name`, `parent_id`, `sort`) VALUES ('前端组', 2, 2);

第二步：定义部门实体类

package com.example.binarytree.entity;

import com.baomidou.mybatisplus.annotation.IdType;
import com.baomidou.mybatisplus.annotation.TableId;
import com.baomidou.mybatisplus.annotation.TableName;
import io.swagger.v3.oas.annotations.media.Schema;
import lombok.Data;

import java.time.LocalDateTime;
import java.util.List;

/**
 * 部门实体类
 * @author ken
 */
@Data
@TableName("sys_dept")
@Schema(description = "部门实体")
public class SysDept {

    @TableId(type = IdType.AUTO)
    @Schema(description = "部门ID")
    private Long id;

    @Schema(description = "部门名称")
    private String deptName;

    @Schema(description = "父部门ID")
    private Long parentId;

    @Schema(description = "排序")
    private Integer sort;

    @Schema(description = "创建时间")
    private LocalDateTime createTime;

    @Schema(description = "更新时间")
    private LocalDateTime updateTime;

    /**
     * 子部门列表（非数据库字段）
     */
    @Schema(description = "子部门列表")
    private List<SysDept> children;
}

第三步：MyBatisPlus Mapper

package com.example.binarytree.mapper;

import com.baomidou.mybatisplus.core.mapper.BaseMapper;
import com.example.binarytree.entity.SysDept;
import org.apache.ibatis.annotations.Mapper;

/**
 * 部门Mapper
 * @author ken
 */
@Mapper
public interface SysDeptMapper extends BaseMapper<SysDept> {
}

第四步：构建部门树服务

package com.example.binarytree.service;

import com.baomidou.mybatisplus.core.conditions.query.LambdaQueryWrapper;
import com.example.binarytree.entity.SysDept;
import com.example.binarytree.mapper.SysDeptMapper;
import com.google.common.collect.Lists;
import lombok.RequiredArgsConstructor;
import lombok.extern.slf4j.Slf4j;
import org.springframework.stereotype.Service;
import org.springframework.util.CollectionUtils;

import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * 部门服务类
 * @author ken
 */
@Service
@Slf4j
@RequiredArgsConstructor
public class SysDeptService {

    private final SysDeptMapper sysDeptMapper;

    /**
     * 构建部门树形结构（类比二叉树层序遍历）
     * @return 树形结构的部门列表
     */
    public List<SysDept> buildDeptTree() {
        // 1. 查询所有部门
        List<SysDept> deptList = sysDeptMapper.selectList(
            new LambdaQueryWrapper<SysDept>().orderByAsc(SysDept::getSort)
        );
        if (CollectionUtils.isEmpty(deptList)) {
            return Lists.newArrayList();
        }
        // 2. 按父ID分组（父ID→子部门列表）
        Map<Long, List<SysDept>> parentIdMap = deptList.stream()
            .collect(Collectors.groupingBy(SysDept::getParentId));
        // 3. 构建树形结构：先找根部门（parent_id=0），再递归设置子部门
        List<SysDept> rootDepts = parentIdMap.getOrDefault(0L, Lists.newArrayList());
        for (SysDept rootDept : rootDepts) {
            setChildren(rootDept, parentIdMap);
        }
        return rootDepts;
    }

    /**
     * 递归设置子部门
     * @param dept 当前部门
     * @param parentIdMap 父ID-子部门映射
     */
    private void setChildren(SysDept dept, Map<Long, List<SysDept>> parentIdMap) {
        List<SysDept> children = parentIdMap.getOrDefault(dept.getId(), Lists.newArrayList());
        if (!CollectionUtils.isEmpty(children)) {
            dept.setChildren(children);
            // 递归设置子部门的子部门
            for (SysDept child : children) {
                setChildren(child, parentIdMap);
            }
        }
    }
}

第五步：接口暴露（Swagger3）

package com.example.binarytree.controller;

import com.example.binarytree.entity.SysDept;
import com.example.binarytree.service.SysDeptService;
import io.swagger.v3.oas.annotations.Operation;
import io.swagger.v3.oas.annotations.tags.Tag;
import lombok.RequiredArgsConstructor;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RestController;

import java.util.List;

/**
 * 部门控制器
 * @author ken
 */
@RestController
@RequestMapping("/dept")
@Tag(name = "部门管理", description = "部门树形结构接口")
@RequiredArgsConstructor
public class SysDeptController {

    private final SysDeptService sysDeptService;

    @GetMapping("/tree")
    @Operation(summary = "获取部门树形结构", description = "基于二叉树层序遍历扩展实现")
    public List<SysDept> getDeptTree() {
        return sysDeptService.buildDeptTree();
    }
}

测试结果

访问http://localhost:8080/swagger-ui.html调用接口，返回结果如下：

[
  {
    "id": 1,
    "deptName": "总公司",
    "parentId": 0,
    "sort": 0,
    "createTime": "2025-11-24T10:00:00",
    "updateTime": "2025-11-24T10:00:00",
    "children": [
      {
        "id": 2,
        "deptName": "技术部",
        "parentId": 1,
        "sort": 1,
        "createTime": "2025-11-24T10:00:00",
        "updateTime": "2025-11-24T10:00:00",
        "children": [
          {"id": 4, "deptName": "后端组", "parentId": 2, "sort": 1, ...},
          {"id": 5, "deptName": "前端组", "parentId": 2, "sort": 2, ...}
        ]
      },
      {"id": 3, "deptName": "产品部", "parentId": 1, "sort": 2, ...}
    ]
  }
]

完美构建出树形结构！

6.2 数据库索引：B+树的底层逻辑

MySQL的InnoDB引擎用B+树作为索引结构，而B+树是二叉树的“多路扩展”：

每个节点有多个孩子（不是2个）；
叶子节点按顺序链接（方便范围查询）；
非叶子节点只存索引，叶子节点存数据。

B+树的设计思想源于二叉搜索树的“有序性”，保证了索引查询的高效性（O(logn)）。

七、常见误区与易混淆点

7.1 深度 vs 高度：别搞反了

深度：从根到当前节点的步数（根深度=1）；
高度：从当前节点到最远叶子的步数（叶子高度=0）。

7.2 递归 vs 非递归遍历：什么时候用？

递归：代码简洁，但数据量大时可能栈溢出（JVM栈深度有限）；
非递归：代码复杂，但更稳定（用堆内存的栈/队列）。

7.3 BST的中序遍历：为什么是有序的？

BST的规则是“左<根<右”，中序遍历是“左→根→右”，自然形成升序序列——这是BST最核心的特性，也是排序、去重的关键。

八、总结：二叉树的学习方法

二叉树的学习核心是“理解逻辑+动手编码”：

先搞懂基础概念（节点、深度、高度），用生活例子类比；
遍历是重中之重，先写递归再写非递归，多画图模拟；
BST的插入/删除要分情况讨论，结合代码一步步走；
平衡树不用死记旋转规则，理解“为什么要旋转”更重要；
结合业务场景（如部门树），把抽象知识落地。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2025-11-24，如有侵权请联系 cloudcommunity@tencent.com 删除

树形结构

本文分享自果酱带你啃java 微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度

二叉树通关指南：从底层逻辑到实战落地，一篇吃透！

二叉树通关指南：从底层逻辑到实战落地，一篇吃透！

二叉树通关指南：从底层逻辑到实战落地，一篇吃透！

一、二叉树是什么？先把基础概念掰明白

1.1 二叉树的本质：“分岔”的节点结构

1.2 二叉树的分类：别搞混这些“变种”

二、二叉树怎么存？两种存储方式的底层逻辑

2.1 顺序存储：用数组“排座位”

2.2 链式存储：用节点“搭链条”

三、二叉树的核心操作：遍历（递归+非递归）

3.1 深度优先遍历：“钻到底”再回头

3.1.1 前序遍历（根→左→右）

3.1.2 中序遍历（左→根→右）

3.1.3 后序遍历（左→右→根）

3.2 广度优先遍历（层序遍历）：“一层一层”往下走

3.3 遍历测试：验证代码正确性

四、二叉搜索树（BST）：最常用的二叉树“变种”

4.1 BST的查找操作

4.2 BST的插入操作

4.3 BST的删除操作（最复杂）

情况1：删除的是叶子节点（无孩子）

情况2：删除的节点只有一个孩子

情况3：删除的节点有两个孩子

4.4 BST的缺陷：可能退化成链表

五、平衡二叉树：让BST“站得稳”

5.1 AVL树：严格平衡的二叉树

右旋示例（左子树过高）：

5.2 红黑树：近似平衡的二叉树

5.3 AVL vs 红黑树：怎么选？

六、实战落地：二叉树在业务中的应用

6.1 树形结构构建：部门树/菜单树

第一步：创建部门表（MySQL8.0）

第二步：定义部门实体类

第三步：MyBatisPlus Mapper

第四步：构建部门树服务

第五步：接口暴露（Swagger3）

测试结果

6.2 数据库索引：B+树的底层逻辑

七、常见误区与易混淆点

7.1 深度 vs 高度：别搞反了

7.2 递归 vs 非递归遍历：什么时候用？

7.3 BST的中序遍历：为什么是有序的？

八、总结：二叉树的学习方法

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐