Android自绘树形控件：递归布局与显式栈清除的实战方案

简介：面向Android初中级开发者的思维导图实现项目，围绕递归算法与堆栈数据结构解决节点绘制与清除问题，覆盖自定义View绘图、触摸事件交互、树形数据模型、布局管理、动画效果及性能优化等核心知识点。项目为完整Android Studio工程，共43个文件，压缩包约279KB，主要包含5个Java源码、11个XML布局、12张项目截图以及Gradle构建配置、README说明等；其中Java源码涵盖节点模型与绘制逻辑，XML布局对应界面结构，截图便于对照运行效果。目录清晰，可对照代码理解整体实现流程。已有259人浏览学习。通过该工程，读者能掌握递归遍历树节点与堆栈回溯清除节点的具体写法，理解onDraw递归绘制与onTouchEvent交互的配合方式。同时可参考节点折叠、展开、删除等场景的数据结构设计与动画处理细节，适合希望提升Android自定义控件和算法应用能力的开发者。

1. 把递归和栈揉进同一个思维导图控件：先想清楚再动手

做 Android 自绘控件的人多少会遇到“树形结构怎么画”这个问题。某次接了个类似思维导图的活儿，本以为只是onDraw里画几个矩形和线，结果第一次递归调完就崩了：节点多时掉帧、深层树直接栈溢出、清除节点时界面残留半边。最后收敛下来的方案，正是标题里那套组合拳——递归算法负责“画”，堆栈负责“清”。这套思路不仅适用于思维导图，任何树形结构自绘（流程图、目录树、家族谱）都能直接套。适合正在做自定义 View、被树形绘制和内存回收折磨的 Android 开发同学，尤其是想把“能跑”变成“跑得稳”的阶段。

2. 数据模型先行：树节点和坐标系的定义决定了递归能不能写顺

2.1 TreeNode 节点结构：宽高、层级、子节点列表一个都不能少

递归绘制的前提是数据结构长得足够“树”。我见过很多人一上来就画，画到一半发现需要层级信息、需要知道父节点是谁，只能回去改模型。先把这个类定义好，后面所有逻辑都会顺很多。

public class MindNode { public String id; public String text; public float x, y; // 节点左上角坐标，布局阶段计算 public float width, height; // 节点的宽高，测量阶段确定 public int depth; // 层级，根节点为 0，决定 x 坐标的偏移量 public MindNode parent; // 父节点引用，清除和回溯时用 public List<MindNode> children = new ArrayList<>(); // 业务数据透传，比如备注、颜色标记 public Object extra; public MindNode(String id, String text) { this.id = id; this.text = text; } public boolean isRoot() { return parent == null; } }

字段说明：

• x, y存的是节点左上角坐标，不是中心点。绘制矩形方便，但后面画连线和命中检测时要做一次“中心点换算”，换算逻辑集中写一个getCenterX()/getCenterY()方法，避免到处改。
• width和height在onMeasure或布局阶段用Paint.measureText()结合“文字宽度 + 左右 padding”算出，不要在onDraw里每次测量，那是卡顿的头号来源。
• depth很重要，它是布局时 x 坐标的基准。思维导图常见的“根在左、子节点向右铺开”的布局，x 就是depth * (levelWidth + levelGap)，y 则由递归计算出的子树高度决定。

2.2 布局阶段的递归：子树高度计算与 y 坐标分配

绘制前必须先知道每个节点的坐标。这一步我用递归，因为树的结构天然适合自底向上算：一个节点的 y 坐标，取决于它的子节点们占了多少高度。这是整个控件里最典型、也最值得写对的一段递归代码。

// 递归计算以 node 为根的子树总高度，并给节点分配 y 坐标 private float layoutSubTree(MindNode node, float x, float targetY) { node.x = x; node.y = targetY; if (node.children.isEmpty()) { return node.height; } float childrenTotalHeight = 0; List<Float> childHeights = new ArrayList<>(); for (MindNode child : node.children) { float childHeight = layoutSubTree(child, x + LEVEL_WIDTH + LEVEL_GAP, targetY + childrenTotalHeight); childrenTotalHeight += childHeight; childHeights.add(childHeight); } // 把父节点移动到子树的垂直中心位置 float childrenHeight = childrenTotalHeight; float maxChildHeight = Collections.max(childHeights); float centerOffset = (childrenHeight - node.height) / 2f; node.y = targetY + centerOffset; // 返回整棵子树的实际占用高度（取最宽的值，保证兄弟节点不重叠） return Math.max(node.height, childrenHeight); }

这段逻辑有几个关键点：

• 第一个递归调用传入的是targetY + childrenTotalHeight，含义是“当前子节点排在上一个子节点下面”，这样兄弟节点在 y 方向上天然错开。
• 返回值为Math.max(node.height, childrenHeight)，原因是一个叶子节点高度可能比它所有子节点加起来还高，这时以父节点高度为准，否则兄弟子树会重叠。
• LEVEL_WIDTH和LEVEL_GAP是两个常量，分别表示每层横向递进的宽度和层间距。我通常取LEVEL_WIDTH = 260f（用 dp 转 px），这样在常规手机屏幕上二层到三层之间能放下标签文字。

这里有个新手容易犯的错：Collections.max(childHeights)在子节点为空时不会触发，因为空 children 已经在前面 return 了，所以安全。但如果你重构代码，把叶子判断去掉，这里就会NoSuchElementException，务必留意。

3. 递归绘制：onDraw 里画节点、画连线、画层级

3.1 绘制主入口与递归 draw 方法

布局阶段算好了坐标，onDraw里就能安心递归绘制了。绘制递归和布局递归是两套递归，但结构几乎一样，只是职责不同：布局递归管“坐标”，绘制递归管“形象”。

@Override protected void onDraw(Canvas canvas) { super.onDraw(canvas); if (root == null) return; // 先画连线，再画节点，保证连线不会被节点遮挡 drawConnections(canvas, root); drawNodeRecursive(canvas, root); } private void drawNodeRecursive(Canvas canvas, MindNode node) { // 画节点背景（圆角矩形） RectF rect = new RectF(node.x, node.y, node.x + node.width, node.y + node.height); canvas.drawRoundRect(rect, NODE_CORNER_RADIUS, NODE_CORNER_RADIUS, nodeBgPaint); // 画文字，文字基线需要偏移到垂直居中 float textX = node.x + NODE_PADDING_LEFT; float textY = node.y + (node.height - textPaint.getTextSize()) / 2f + TEXT_BASELINE_OFFSET; canvas.drawText(node.text, textX, textY, textPaint); // 递归子节点 for (MindNode child : node.children) { drawNodeRecursive(canvas, child); } }

代码说明：

• 先画连线后画节点，这是个顺序问题。如果先画节点，连线从节点下面穿过时会把文字盖住，视觉上很脏。
• TEXT_BASELINE_OFFSET是Paint.FontMetrics里ascent的绝对值，具体值由textPaint.getFontMetrics()在初始化时取出。直接getTextSize() / 2会让文字偏上，因为基线在字符下部，这个坑后面详细说。
• nodeBgPaint和textPaint都是成员变量，永远不要在onDraw里 new Paint。每帧几毫秒的绘制时间里，对象分配会导致 GC 频繁触发，帧率曲线会像锯齿一样。

3.2 连线绘制：三次贝塞尔还是折线？

思维导图的连线样式，市面上主流是两种：平滑的贝塞尔曲线，和带圆角的折线。贝塞尔看起来高级，但控制点算不好就会画出“穿过节点”的诡异曲线。我最终选的是简单的“垂直出线 + 水平折线”，代码短、不容易出错、视觉也不差。

private void drawConnection(Canvas canvas, MindNode parent, MindNode child) { float startX = parent.x + parent.width; float startY = parent.getCenterY(); float endX = child.x; float endY = child.getCenterY(); // 控制点取起点和终点的水平中心位置，形成“先横后竖再横”的折线 float midX = (startX + endX) / 2f; Path path = new Path(); path.moveTo(startX, startY); path.cubicTo(midX, startY, midX, endY, endX, endY); canvas.drawPath(path, connectionPaint); }

参数说明：

• midX取水平中点，两个控制点(midX, startY)和(midX, endY)都在中线上，画出的曲线是“水平段很短的 S 形”，比直线柔和，也不会像全曲线那样弯曲过度。
• 如果你的节点框比较宽，建议把midX改成startX + (endX - startX) * 0.4f，让曲线更早拐弯，避免在父节点区域横向拉太长。
• connectionPaint建议设置setStrokeWidth(2f)和setAntiAlias(true)，颜色略浅于节点背景色（比如#CCCCCC到#E0E0E0之间），太深会抢文字注意力。

3.3 绘制相关的参数清单与调优建议

这些参数全部抽成常量或直接放styles.xml里用资源引用，方便后续主题换肤。不要在onDraw里读资源，context.getColor()每次调用有开销，初始化时取一次存成员变量即可。血泪经验：换肤功能上线后可可可测出每次绘制多耗时 0.3ms，帧率直接掉到 55 帧以下。

4. 堆栈式清除：为什么删除节点不能用递归

4.1 显式栈遍历删除整棵子树

标题里“堆栈解决清除”不是噱头。删除一个节点意味着要把它的所有后代全部移除，否则子节点飘在界面上就是“鬼影”。递归删除当然能写，但树下脏数据多、深度大时，递归的调用栈高度不可控——主线程栈默认只有 1MB，一次删除操作压进去几百层栈帧，轻则 ANR，重则StackOverflowError。用显式栈改成“手动管理遍历顺序”，彻底避免这个问题。

public void removeNodeWithStack(MindNode target) { if (target == null || root == null) return; // 先把目标节点从父节点的 children 里摘掉，防止遍历时“回头” if (target.parent != null) { target.parent.children.remove(target); } else { root = null; // 删除根节点，整棵树清空 return; } // 用栈做后序遍历：保证先删子节点，再删父节点 Deque<MindNode> stack = new ArrayDeque<>(); stack.push(target); while (!stack.isEmpty()) { MindNode node = stack.pop(); for (MindNode child : node.children) { stack.push(child); } // 断开父子引用，便于 GC 回收 node.children.clear(); node.parent = null; } // 通知 View 重绘 notifyDataChanged(); }

代码逻辑说明：

• 为什么用Deque而不是Stack？java.util.Stack继承自Vector，所有方法都加了 synchronized 锁，单线程下白白损耗性能。ArrayDeque是纯数组实现，push/pop都是 O(1) 且无锁。
• 弹出节点后先压入它的子节点，再清理自己的子列表。这个顺序保证遍历到某个节点时，它所有后代已经在栈里排队等着被弹出了，不会出现“孩子没删、爹先没了”的悬空引用。
• remove()操作只摘除直接父子的关联。如果目标节点不是根，它的子节点列表已经在 while 循环里逐个断开了，不需要额外处理。

4.2 撤销栈与重做栈：给清除操作留后悔药

用户删错节点是高频操作，比删对更常见。这个控件我加了“撤销/重做”两个栈，把删除操作本身变成入栈记录，撤销时把记录的节点重新插回父节点。

private final Deque<RemoveAction> undoStack = new ArrayDeque<>(); private final Deque<RemoveAction> redoStack = new ArrayDeque<>(); public void removeNodeWithUndo(MindNode target) { RemoveAction action = new RemoveAction(target, target.parent, target.parent.children.indexOf(target)); removeNodeWithStack(target); undoStack.push(action); redoStack.clear(); // 新操作发生后，重做历史失效 } public void undo() { RemoveAction action = undoStack.pop(); if (action == null) return; // 把节点插回原来的位置 action.parent.children.add(action.childIndex, action.node); action.node.parent = action.parent; redoStack.push(action); notifyDataChanged(); }

关于撤销栈的几个工程细节：

• RemoveAction只是个简单的 POJO，持有三个字段：节点引用、父节点引用、在父节点 children 中的原始索引。索引很重要，否则撤销时节点会跑到列表末尾，顺序乱了。
• undoStack和redoStack的深度建议限制在 30 左右。思维导图节点动辄几千个，无限保留历史会让内存膨胀，实测 30 层足够覆盖绝大部分误操作场景。
• 撤销恢复节点后，递归绘制不用重跑。因为节点坐标没变，但如果布局算法是动态的（比如子节点增删后整树重排），撤销后必须重新layoutSubTree，否则节点会画在旧坐标上，重叠错位。

我这里布局是静态的（只在setData时算一次），所以撤销比较简单。如果你的版本做了动态增删重排，那撤销要连带重算坐标，写起来会多一个layoutFlag标记。

4.3 命中检测：栈遍历换成现实触摸场景

清除操作得先知道用户点的是哪个节点。递归遍历做命中检测也行，但配合“栈”的思路，我一般直接用同一套ArrayDeque遍历，做到逻辑统一。

public MindNode hitTest(float touchX, float touchY) { if (root == null) return null; Deque<MindNode> stack = new ArrayDeque<>(); stack.push(root); while (!stack.isEmpty()) { MindNode node = stack.pop(); if (touchX >= node.x && touchX <= node.x + node.width && touchY >= node.y && touchY <= node.y + node.height) { return node; } // 子节点入栈 for (MindNode child : node.children) { stack.push(child); } } return null; }

说明：

• 这里的“命中”范围是整个节点矩形。如果节点密集，可以给矩形做 4dp 的膨胀：touchX >= node.x - 4 && touchX <= node.x + node.width + 4，提升点击容错率。
• 栈遍历是深度优先，如果节点有重叠区域，先弹出的子节点会先命中，后弹出的父节点次之，天然满足“优先选中子节点”的直觉。
• 触摸事件里记得先做坐标转换。如果外层 ScrollView 或 ViewPager 拦截了事件，MotionEvent的坐标可能是相对于父容器的，需要view.getLocationOnScreen()换算后再传给hitTest。这个坑在真机上偶发，调试时看坐标对不上就先怀疑这里。

5. 避坑手册：递归绘制和栈清除的五个实战坑

5.1 onDraw 里 charSequence 分配导致掉帧

现象：节点数超过 300 后，滑动时帧率从 60fps 掉到 30fps 左右，用systrace看到 GC 频繁触发。

原因：drawText传进去String，而String是从HashMap取值拼接的。在onDraw里做字符串拼接或substring，每帧都会分配新对象，GC 压力集中在绘制线程。

解决：把所有节点的绘制文本在数据加载阶段预处理成StaticLayout或PrecomputedText缓存。文字不变时用TextPaint的静态StaticLayout直接绘制，不走drawText的实时测量。我这版因为文字简洁，退而求其次：用SpannableString缓存，onDraw里直接canvas.drawText(cachedText, ...)，不再做拼接。

5.2 递归深度过大直接栈溢出

现象：树深度超过 800 层（研发自测故意挂了个深链），一调用layoutSubTree就崩，Logcat报StackOverflowError。

原因：主线程默认栈空间约 1MB，每层递归栈帧约 1~2KB，800 层就逼近极限。思维导图的业务数据不太可能这么深，但用户导入外部数据时不可控。

解决：布局阶段改用显式栈做迭代化后序遍历。和前面清除逻辑类似：先压栈，弹出节点时计算其子树高度。代码结构上把“递归”改成“栈模拟递归”，写完很快，收益是彻底摆脱深度限制。绘制递归保留，因为用户能看到的层数有限，绘制阶段递归深度等于当前可见层级，一般不到 50 层。

5.3 文字基线偏移导致文字不在节点垂直中心

现象：节点背景矩形画好后，文字明显偏上，距离顶部有 4~5px 空隙，底部贴边。

原因：canvas.drawText(text, x, y, paint)的y是文字基线的位置，不是文字顶部的 y。直接node.y + node.height / 2 + textSize / 2算出来的是“文字中线的上沿”，视觉上就偏上了。

解决：用Paint.FontMetrics里的ascent和descent算基线偏移：

Paint.FontMetrics fm = textPaint.getFontMetrics(); float baseline = (node.y + node.height - fm.ascent - fm.descent) / 2f; canvas.drawText(node.text, node.x + NODE_PADDING_LEFT, baseline, textPaint);

这个公式是baseline = centerY - (ascent + descent) / 2，ascent为负数，descent为正数，最终算出的偏移量能让文字在视觉上稳稳居中。从那以后我每次写自绘控件都先写一行Paint.FontMetrics测试，不再凭感觉调 1px 2px。

5.4 贝塞尔控制点错误导致连线穿过其他节点

现象：三层以上的节点，连线会斜着穿过中间的兄弟节点区域，视觉上一团乱麻。

原因：控制点取的是(startX + endX) / 2f，但startY和endY可能相差很大（比如父节点在顶部，子节点在底部），曲线会在中部横向甩出去，正好穿过中间层的节点。

解决：控制点不再取单一midY，而是把曲线拆成“两段式”——先从父节点中心竖直走到midY，再水平走到子节点中心。用Path.cubicTo传入(startX, midY, midX, endY, endX, endY)，让曲线只在水平方向上有大弧度，垂直方向是直的。改完后再没出现过穿越节点的情况。

5.5 栈清除后节点引用残留导致内存泄漏

现象：反复增删节点后，Activity退出时LeakCanary报告某个节点被View持有，无法回收。

原因：删除节点时，node.parent = null和children.clear()都做了，但如果还有某个HashMap以id为 key 持有节点引用，它就成了 GC Root 路径上的一环。常见场景是“按 id 查找节点”的业务缓存没清。

解决：维护一个Map<String, MindNode> idIndex时，在removeNodeWithStack里同步idIndex.remove(node.id)。如果节点还有业务回调（比如点击事件监听器持有条件），也要一并置空。建议统一走releaseNode(node)方法，里面集中处理引用断开，不散落在各处。

6. 进阶技巧：用同一套栈把绘制和清除统一起来

思路收束一下：绘制用递归，清除用栈，其实两者能统一。核心是把drawNodeRecursive改成显式栈实现的先序遍历——这样做有两个直接收益：第一，绘制本身不再受深度限制；第二，和清除逻辑共用同一套遍历骨架，代码量更少、维护成本更低。

private void drawNodeWithStack(Canvas canvas) { Deque<MindNode> stack = new ArrayDeque<>(); stack.push(root); while (!stack.isEmpty()) { MindNode node = stack.pop(); // 画节点和连线的逻辑，和递归版完全一致 drawNode(canvas, node); if (node.parent != null) { drawConnection(canvas, node.parent, node); } // 注意压栈顺序：先压右子节点，后压左子节点 // 这样弹出时先处理左子树，保持从左到右的绘制顺序 List<MindNode> children = node.children; for (int i = children.size() - 1; i >= 0; i--) { stack.push(children.get(i)); } } }

压栈顺序是这段代码的灵魂：ArrayDeque是后进先出，想先画左子节点，就得最后压它，所以循环从尾部往前压。如果不关心绘制顺序，只求遍历完整，那随便压都行；但思维导图需要从左到右的视觉顺序，这个倒序压栈的技巧值得单独记下来。

实际验证方法：写一个深度 50 层的测试用例，节点总数为 2000+，对比递归版和栈版的耗时。递归版在真机上偶尔触发 GC 卡顿，栈版全程稳定 60fps。更直观的验证方式是加一个 “调试深度” 开关：把树深度改成 1000 层，递归版直接崩，栈版照常绘制——这个实验能让你彻底信服“手工栈 + 迭代”的价值。

从那以后，我每次写树形自绘控件都强制走一遍这个流程：先定死 TreeNode 的引用关系，布局用递归算坐标，绘制按需选递归或栈，删除和撤销一律显式栈。这套配置让我在三个项目里都没再为树深度和 GC 问题返工，希望帮到你。

本文还有配套的精品资源，点击获取