简介这是一份面向Android开发者的思维导图实现源码工程重点演示如何用递归算法与堆栈数据结构解决节点绘制、遍历与清除问题适合对自定义View、树形结构和交互绘制感兴趣的初中级开发者。压缩包共43个文件以Java源码、XML布局、Gradle配置和图片资源为主其中5个Java文件为核心逻辑11个XML负责界面与资源配置另含PNG/JPG预览图及README说明整体约279KB结构清晰便于直接导入学习。已有257人学习下载。通过该工程可以掌握自定义View中重写onDraw执行递归绘制、利用堆栈回溯清除节点、触摸事件处理及性能优化等关键思路获得一套完整可运行的思维导图Demo便于在此基础上扩展动画效果或节点编辑功能。 接到在Android端实现思维导图的需求时我第一反应是它比普通列表复杂得多。思维导图的本质是树形数据结构每个节点都有子节点且节点绘制时还要考虑父子层级关系、位置计算、缩进折叠等问题。而标题里提到的递归算法和堆栈恰好是解决节点绘制和节点清除这两大痛点的关键工具。这篇文章我会从一个真实项目的角度把我在Android上实现思维导图时遇到的核心问题、算法选型、以及最终跑通的方案完整记录下来。适合准备上手自定义View做树形结构的开发者参考也适合对递归和栈这两种数据结构在图形领域的实战应用感兴趣的读者。1. 为什么递归和堆栈是绘制思维导图的地基1.1 思维导图的数据本质是树而非列表做任何图形化控件之前第一步永远是先把数据模型想清楚。思维导图从外观上看是中心主题向四周发散分支分支再发散子分支这个结构抽象成数据结构就是一棵多叉树根节点存放中心主题每个节点可以有任意数量的子节点叶子节点没有子节点。中心主题根节点 ├── 分支A │ ├── 子节点A-1 │ └── 子节点A-2 ├── 分支B │ └── 子节点B-1 └── 分支C树这种结构有一个天然特性访问某个节点后必须递归地访问它的所有子节点才能完整遍历整棵树。这和数组、链表的线性遍历完全不一样。如果你用for循环和下标去遍历一棵树代码会异常别扭因为你不知道当前节点有多少个孩子、孩子的孩子又有多少层。而递归恰好匹配这个场景——函数在处理当前节点时只需要把处理子节点这件事交给自身的函数调用去完成层数再多也能一层层展开。1.2 绘制节点的核心矛盾位置依赖和层级交错真正上手后会发现绘制思维导图的难点不在于画出几个圆角矩形和文字而在于每个节点的位置是在动态计算中确定的。子节点的水平X坐标取决于父节点的X坐标加上偏移量子节点的垂直Y坐标取决于前面的兄弟节点已经占了多少高度整棵子树的宽高又取决于子树内部所有节点的累加结果。这意味着你在绘制前必须先完成一轮自底向上的测量先计算叶子节点占据的空间再逐级累加给父节点。完成测量后再开始自顶向下的布局从根节点开始依次确认每个子节点落在这个画布的哪个位置。这一测量一布局恰好就是两轮遍历。第一轮用递归顺手就能算出每棵子树的尺寸第二轮布局时依然用递归把坐标逐层下发。如果只用普通的循环变量每处理一层就要手动维护一个当前层节点列表代码的可读性和维护成本会急剧上升。1.3 堆栈在这个场景里扮演什么角色递归和堆栈本质上是一对双胞胎。函数递归调用时系统底层就是靠栈来保存每一层调用的局部变量和返回地址的。但在实际工程中我会刻意引入显式堆栈Stack或Deque来做两件事用显式栈替代部分递归当思维导图的层级非常深比如用户疯狂回车创建了上百层子节点递归调用过深会逼近Android主线程的调用栈上限导致StackOverflowError。用显式栈压入节点对象循环处理就不会有这个风险。用栈来辅助节点清除删除一个节点时除了要移除它本身还要把它下面挂载的所有子孙节点全部从内存中解引用。栈的后进先出特性天然适合深度优先的遍历回收。所以标题里同时提到递归算法和堆栈不是堆砌名词而是各司其职递归负责直观地遍历和布局堆栈负责处理深度风险和控制清除顺序。2. 搭建思维导图节点的基础数据结构2.1 TreeNode类的设计我采用的是典型的三段式结构数据层、布局层、绘制层分离。其中数据层的TreeNode是这个项目的基石它记录节点的业务数据和拓扑关系。public class MindNode { // 节点ID用于删除、查找、动画追踪 public String id; // 节点内容 public String content; // 父节点引用清除和回溯时用 public MindNode parent; // 子节点列表保持插入顺序 public ListMindNode children new ArrayList(); // 以下是布局阶段计算出的位置和尺寸缓存 public float x; public float y; public float width; public float height; // 本子树总高度测量阶段使用 public float subTreeHeight; public MindNode(String id, String content) { this.id id; this.content content; } public boolean isLeaf() { return children.isEmpty(); } }这个类看上去简单其实有几个字段我是一步步补出来的。parent父节点引用是清除阶段的关键。很多新手写的树结构只有child引用没有parent引用这样删除一个节点时你只能从根节点重新遍历整棵树才能找到谁挂着这个待删除节点再把它的children列表里的对应项移除。有了parent引用删除操作就变成了O(1)的操作node.parent.children.remove(node)效率高得多。subTreeHeight子树总高度是布局算法里的关键缓存。思维导图通常是水平方向展开父节点在左侧子节点在右侧。同一层级的多个兄弟节点纵向排列它们的Y坐标必须考虑这个节点下面的整棵子树还要占用多少高度。如果在测量阶段就把每个节点的subTreeHeight算好缓存起来后续计算Y坐标时就是纯加减法不需要重复遍历子树。2.2 准备一份示例数据为了验证算法我通常会在代码里写死一份树形数据先用小数据跑通绘制流程再接入真实业务数据。private MindNode buildTestData() { MindNode root new MindNode(0, Android 知识体系); MindNode javaNode new MindNode(1, Java 基础); javaNode.children.add(new MindNode(1-1, 集合框架)); javaNode.children.add(new MindNode(1-2, 并发编程)); MindNode androidNode new MindNode(2, Android 进阶); androidNode.children.add(new MindNode(2-1, 自定义 View)); androidNode.children.add(new MindNode(2-2, 性能优化)); MindNode algoNode new MindNode(3, 算法与数据结构); root.children.add(javaNode); root.children.add(androidNode); root.children.add(algoNode); // 为每个子节点设置 parent for (MindNode child : root.children) { child.parent root; for (MindNode grandChild : child.children) { grandChild.parent child; } } return root; }注意这段代码里我手动给每个节点补了parent引用这一步在实际业务中很能体现数据接入的规范性。如果是从接口返回的JSON解析出来的树一定要在解析时同步维护parent否则后面删除节点会非常痛苦。3. 核心绘制算法用递归计算位置用栈防止溢出3.1 整体流程测量与布局两轮遍历在Android的自定义View中绘制一个思维导图通常这样组织onMeasure阶段计算每个节点的尺寸宽高这个可以从文字测量得出。measureSubtree阶段自底向上计算每棵子树的总高度。layoutSubtree阶段自顶向下计算每个节点的具体坐标。onDraw阶段画连线、画节点背景、画文字。其中第2步和第3步是算法核心都体现了递归的典型应用。3.2 递归版measureSubtree与layoutSubtree先看测量子树的递归方法。这里的思路是先递归测量所有子节点累加出children的总高度然后再设置当前节点的subTreeHeight。private float measureSubtree(MindNode node) { if (node.isLeaf()) { node.subTreeHeight node.height; return node.subTreeHeight; } float totalChildHeight 0; float verticalGap 16f; // 兄弟节点之间的垂直间距 for (MindNode child : node.children) { totalChildHeight measureSubtree(child); totalChildHeight verticalGap; } totalChildHeight - verticalGap; // 最后一个孩子的尾部不需要再加间距 node.subTreeHeight Math.max(node.height, totalChildHeight); return node.subTreeHeight; }这段代码有一个重要设计父节点的subTreeHeight不一定等于子节点的总和。如果父节点本身就很高比如文字很多节点被撑得很高那么整棵子树高度要取最大值避免父节点和子节点重叠。这个细节我在第一次实现时忽略了结果出现了父节点文字和第一个子节点重叠的界面问题。再看布局方法。布局的思想是把子节点们垂直居中地排列在父节点右侧。private void layoutSubtree(MindNode node, float x, float y) { node.x x; node.y y; if (node.isLeaf()) { return; } float childX x node.width horizontalMargin; float childrenTotalHeight 0; for (MindNode child : node.children) { childrenTotalHeight child.subTreeHeight; childrenTotalHeight verticalGap; } childrenTotalHeight - verticalGap; // 子节点整体区域的起始Y坐标让子节点区域中心和父节点中心对齐 float startY y (node.height - childrenTotalHeight) / 2f; float currentY startY; for (MindNode child : node.children) { // 子节点自身垂直居中于自己占用的子树高度区域 float childY currentY (child.subTreeHeight - child.height) / 2f; layoutSubtree(child, childX, childY); currentY child.subTreeHeight verticalGap; } }这里有个值得说道的细节子节点的Y坐标不是简单地从startY依次往下排而是要在每个子节点分配的subTreeHeight区域内居中。因为子节点本身的height可能比它的整棵子树高度小如果直接靠上排列层级不对称视觉上会很怪。这个区域内居中的手法是思维导图布局里最常用的小技巧也是绘制出来的图看上去端正的关键。3.3 栈版用显式栈做深度优先遍历递归版本虽然简洁但我在压测时曾构造了一棵深度超过1000层的树结果直接在真机上崩了Logcat报出明显的栈溢出错误。这是因为Android主线程默认的栈大小有限通常只有8KB到1MB级别的限制实际因机型而异每一层递归都会压入局部变量、返回地址层级太深时系统栈就扛不住了。于是我在绘制路径上增加了一个显式栈的版本用循环来模拟递归。遍历一棵树是标准的深度优先遍历用栈伪代码如下public void drawByStack(Canvas canvas, MindNode root) { DequeMindNode stack new ArrayDeque(); stack.push(root); while (!stack.isEmpty()) { MindNode node stack.pop(); drawNode(canvas, node); // 注意先压右子节点再压左子节点弹出时才会先处理左边 for (int i node.children.size() - 1; i 0; i--) { stack.push(node.children.get(i)); } } }为什么要用Deque而不是Stack因为Java的Stack继承自Vector所有方法都加了synchronized在单线程UI绘制场景下会白白损失性能。ArrayDeque是纯数组实现没有同步锁性能更高。这个选择在绘制大量节点时能省下不少时间。另外一个细节是压栈顺序从children末尾往前压这样弹出来的顺序就是从左到右和递归版保持一致。如果直接用for循环从头到尾压栈最终绘制顺序会反过来虽然在思维导图里节点之间不重叠的话绘制顺序影响不大但保持一致的遍历顺序对动画、点击命中测试都有好处。3.4 两种方案如何取舍维度递归版显式栈版代码可读性很高直接对应树形结构中等需要理解栈的状态维护层级深度限制受限于系统调用栈深度过大易崩溃只受限于堆内存深度可达数十万性能函数调用有开销但通常可忽略循环压栈略快适合场景常规思维导图层级100层深度未知或需要挂起/恢复遍历的场景我最终的方案是布局计算保留递归版绘制遍历保留栈版。因为布局阶段通常只需要在onMeasure和onLayout时执行一次即便层数很少也不会出问题而onDraw阶段的绘制方法在每帧都会被调用用栈版更稳定。4. 节点清除的完整方案防止内存泄漏的必经之路4.1 清除的两种语义删除节点与清空画布标题里提到的清除在思维导图项目里其实有两种含义很多文章把它们混为一谈但代码实现完全不同删除单个节点用户长按某个分支选择删除该节点和它的子孙节点全部移除。清空整棵导图用户新建导图需要把根节点下所有内容都清掉。两种场景都需要正确的遍历解引用否则就会出现经典的内存问题节点对象虽然从界面上消失了但仍然被某个父节点的children列表引用着导致Activity退出时内存无法被回收。4.2 递归删除 vs 堆栈删除删除单个节点时我用递归来释放子树private void removeSubtree(MindNode node) { if (node null) return; // 先从父节点的 children 列表中移除自己 if (node.parent ! null) { node.parent.children.remove(node); } // 递归释放所有子节点 for (MindNode child : node.children) { removeSubtree(child); } // 清空引用加速GC回收 node.children.clear(); node.parent null; }这段代码本质上是后序遍历先删除子节点再删除当前节点。顺序很重要如果你先把当前节点的children清空了再遍历它就没有子节点可删了内存里依然残留着子节点对象。所以必须是先递归到叶子逐层往上断开引用。清空整棵导图则有两种思路。一种是从根节点调用removeSubtree另一种是用栈做迭代清除private void clearTreeByStack(MindNode root) { if (root null) return; DequeMindNode stack new ArrayDeque(); stack.push(root); while (!stack.isEmpty()) { MindNode node stack.pop(); // 把自己从父节点的children中摘除 if (node.parent ! null) { node.parent.children.remove(node); } // 子节点全部压栈后续逐个清理 for (MindNode child : node.children) { stack.push(child); } // 清空当前节点的子列表和父引用 node.children.clear(); node.parent null; } }这里用栈的优点是即使树有几千个节点也不会占据系统的调用栈空间。清除操作在某些业务场景下是在后台线程做的比如用户连续快速删除如果递归太深一样可能栈溢出。4.3 清除后必须做的事通知重绘和命中测试同步清除节点后要记得刷新界面。调用View.invalidate()触发onDraw重新绘制。这一步看似简单但有个坑如果删除的是当前选中节点而你的代码又在点击事件里持有这个节点的引用再次点击就会出现NullPointerException或绘制出半个节点的情况。我的做法是在删除节点后统一把当前选中引用置空并把删除节点的位置信息放入一个待执行淡出动画的列表中动画结束后再彻底释放。另外需要注意删除节点后必须重新执行measureSubtree和layoutSubtree因为兄弟节点的Y坐标会因为子树的移除而上移。如果只invalidate不重新布局屏幕上会出现空白区域。我封了一个方法专门处理这个事private void refreshMindMap() { // 重新测量子树高度 measureSubtree(rootNode); // 重新布局坐标从根节点(0,0)附近开始 layoutSubtree(rootNode, startX, startY); // 重新绘制 invalidate(); }4.4 清空引用时最常见的两个坑第一个坑是ConcurrentModificationException。如果你在遍历children的时候同时删除子节点比如用for-each遍历时调用removeSubtree修改同一个children列表就会触发这个异常。所以要删除一个节点的多个子节点时先把要删的节点收集到一个临时列表中遍历结束后再统一删除或者像我上面那样在遍历子节点前先把自己从父亲的children里摘掉从根上避免对同一个列表边读边写。第二个坑是括号匹配式的引用遗漏。有些人的树形结构里不仅有children列表还有一张HashMapString, MindNode用于根据ID快速查找节点。删除时只处理了children列表忘了从HashMap里remove掉这条记录结果内存泄漏了。删除操作必须同步维护所有引用该节点的地方这一步非常考察思维的缜密程度。5. 实测中容易翻车的性能瓶颈与优化手段5.1 onDraw不要做复杂计算思维导图的节点数量一旦超过100个onDraw每帧都要绘制所有节点性能就开始变得敏感。我在第一版里犯的错误是在onDraw里直接调用文字测量Paint.measureText和矩形圆角路径构建这导致滑动时每一帧都会重新测量文字帧率掉得厉害。正确做法是文字宽度和节点矩形路径在布局阶段就计算好并缓存onDraw只负责canvas.drawRect和canvas.drawText这种纯绘制操作。文字测量是相对昂贵的操作尤其是在中英文混排的场景下一次绘制200个节点就会调用200次measureText每次都要走一遍字体排版逻辑这些计算越早做越好。5.2 画布裁剪和可见区域过滤另一个优化是对超出屏幕范围的节点直接跳过绘制。思维导图支持平移和缩放后可视区域通常只占整棵树的很小一部分如果依然绘制全部节点就白白浪费了大量GPU渲染指令。在onDraw里加入一个简单的可见性判断protected void onDraw(Canvas canvas) { super.onDraw(canvas); if (rootNode null) return; // 保存当前画布的平移缩放状态 canvas.save(); canvas.translate(offsetX, offsetY); canvas.scale(scaleFactor, scaleFactor); drawSubtree(canvas, rootNode); canvas.restore(); } private void drawSubtree(Canvas canvas, MindNode node) { // 如果节点在可见区域之外跳过绘制子树 if (node.x node.width 0 || node.y node.height 0 || node.x getWidth() || node.y getHeight()) { return; } // 绘制当前节点 drawNode(canvas, node); // 递归绘制子节点 for (MindNode child : node.children) { drawSubtree(canvas, child); } }注意这里我保留了递归实现是因为这段代码只在onDraw里执行而onDraw对绝大多数思维导图场景来说层级不会深到栈溢出的程度。如果确实要画上千层节点可以替换成前面讲的栈版本逻辑一样。5.3 布局计算尽量放在后台线程测量和布局阶段涉及递归遍历整棵树当节点数量达到几千个时即使在主线程执行几十毫秒也会造成可感知的卡顿。我的工程做法是数据变化后先在后台线程做measureSubtree和layoutSubtree得到所有节点的坐标和尺寸缓存后通过runOnUiThread回到主线程只做invalidate。这样界面数据更新时主线程只负责绘制不负责计算。有一点要注意后台线程计算时使用的是节点对象快照如果后台计算还没结束用户又修改了树结构就会产生数据竞争。我在这里用了简单版本号校验数据每次变更version自增后台线程计算结束后检查version是否变化如果变了就舍弃本次结果重新计算。这个方案简单可靠比加锁更好维护。5.4 大量节点时的绘制策略进阶如果节点超过5000个单纯靠自定义View逐节点绘制已经不太够用了。此时可以引入缓存策略把一整棵子树绘制到离屏Bitmap中当用户平移时先整体绘制Bitmap只对发生变化的局部区域重新绘制节点。这个优化我是在后期加上的。实际效果非常明显当平移导图时被缓存区域的绘制成本从几千次drawXxx调用降为一次drawBitmap调用帧率直接从20FPS提升到满帧。缺点是实现复杂度高需要维护缓存失效逻辑比如某个节点内容变更后其对应子树的Bitmap就需要重新生成。6. 这套方案后续可以怎么扩展6.1 从静态绘制走向手势交互绘制铺平了导图就成功了一大半但真正想做成能用的产品还需要补齐手势交互。当前框架下最直接扩展的是两点第一点击命中检测。在onTouchEvent里拿到触摸坐标遍历所有节点判断点是否落在(node.x, node.y, node.xnode.width, node.ynode.height)矩形内。这个检测如果你不想在主线程遍历所有节点可以在布局阶段构建一个空间索引比如四叉树但思维导图的节点数通常不超过1000线性遍历就够用了。第二缩放和平移。只需要在onDraw里对canvas做translate和scale并记录offsetX、offsetY、scaleFactor就能实现最基本的平移缩放。缩放时要同步调整文字大小和节点尺寸处理起来略微繁琐但核心的布局坐标不需要重新计算因为逻辑坐标始终是一致的。6.2 折叠与展开子节点的设计思维导图产品几乎都有折叠功能点击某个节点它的子节点暂时隐藏。当前的数据结构已经天然支持这个功能只需要给MindNode加一个boolean isExpanded字段布局和绘制时跳过被折叠节点的子节点即可。有个细节值得注意折叠状态下父节点的subTreeHeight不再是整棵子树的高度而应该等于它自身的高度。否则被折叠隐藏的子节点依然占据着空间导图会出现一大片空白。所以measureSubtree阶段要判断isExpanded折叠时直接返回node.height。6.3 我对这套算法组合的真实体会在Android端做思维导图最大的感受是递归算法让代码结构和数据结构保持了一致性堆栈则在关键环节提供了安全兜底。现在回过头看坚持在布局阶段使用递归、在绘制和清除阶段使用显式栈是一个经得起测试的工程决策。尤其是清除节点时用栈实现遍历回收避免了很多深层递归导致的崩溃问题。如果在项目初期把这些算法选型都想透彻后面的开发会顺利很多。希望这篇分享能帮到正在做自定义View树形控件、或者准备做思维导图产品的开发者少走几步弯路。本文还有配套的精品资源点击获取