1. 说在前面二叉树到底卡了多少人二叉树这玩意儿几乎是每个学编程的人绕不过去的坎。我见过太多人链表玩得贼溜一到二叉树就懵了。为什么因为链表是线性的你顺着next指针一路走就行但二叉树是分叉的你得同时处理往左走和往右走两条路再加上递归、栈、队列这些概念搅在一起脑子不够用很正常。但二叉树又是真的重要。文件系统目录、编译器语法树、数据库索引、路由表、哈夫曼编码、决策树底层全是二叉树或者它的变种。你写代码写得再花哨不懂树结构很多场景就是玩不转。这篇文章只讲两件事怎么创建一棵二叉树怎么把树在终端里用文本显示出来。别小看这两件事——创建是基础显示是调试的命根子。你连自己建的树长啥样都看不见后面什么遍历、查找、删除全是扯淡。2. 创建二叉树先搞懂你手里有什么2.1 链式存储的基本结构先搞清楚一码事我们说的创建二叉树到底创建的是什么二叉树的存储方式有两种主流方案一个是顺序存储用数组一个是链式存储用节点和指针。数组方案适合完全二叉树比如堆排序里那种因为父子关系可以用下标算出来左孩子是2*i1右孩子是2*i2。但普通二叉树用数组存中间会空出大量空洞浪费空间不说代码读起来也费劲。所以绝大多数场景我们用链式存储。一个节点就是一组数据加左右两个指针结构体长这样typedef struct TreeNode { int data; struct TreeNode* left; struct TreeNode* right; } TreeNode;如果是C你可以顺手用模板template typename T struct TreeNode { T data; TreeNodeT* left; TreeNodeT* right; TreeNode(T val) : data(val), left(nullptr), right(nullptr) {} };注意如果不写构造函数每次你得手动初始化left和right为nullptr。这个坑我踩过无数次漏掉一次遍历时野指针直接崩。2.2 递归创建为什么递归是顺理成章的创建二叉树用的最多的方式是从扩展前序遍历序列重建。啥叫扩展前序就是普通的先序遍历序列把空节点用一个特殊符号标记出来比如#。举个例子一棵简单的二叉树1 / \ 2 3 / \ 4 5它的前序遍历是1, 2, 4, 5, 3。但光靠这个序列你没法确定树长什么样因为1, 2, 4, 5, 3可以对应好几种不同的树形。为了让序列唯一确定一棵树我们加入空节点标记1, 2, 4, #, #, 5, #, #, 3, #, #这里每个#代表一个空子树位置。这样我们就能根据这个序列重建出唯一的树。递归创建的核心逻辑其实就一句话读到一个值就创建一个节点然后递归创建左子树和右子树读到空标记就返回空指针。TreeNode* createTreeByPreorder(int arr[], int* idx, int len) { if (*idx len) return NULL; if (arr[*idx] -1) { // 用-1代表空节点 (*idx); return NULL; } TreeNode* node (TreeNode*)malloc(sizeof(TreeNode)); node-data arr[*idx]; (*idx); node-left createTreeByPreorder(arr, idx, len); node-right createTreeByPreorder(arr, idx, len); return node; }用的时候int arr[] {1, 2, 4, -1, -1, 5, -1, -1, 3, -1, -1}; int idx 0; TreeNode* root createTreeByPreorder(arr, idx, 11);为什么用指针idx而不是直接传int因为递归调用时下标要递增如果传的是值拷贝每一层递归用的都是自己的局部下标返回时并不会更新你永远只会在同一个位置反复读取。这个问题在C和C里面特别容易犯Java、Python这类语言则没这个烦恼因为它们下标是引用类型或者你在外部封装一层就行。2.3 层级创建用队列搭积木除了递归还有一种很实用的创建方式层序创建。就是你给我一个序列我按从上到下、从左到右的顺序把节点一个一个挂上去。和递归不同层级创建不需要通过数组上下标推算父子关系而是用队列先进先出来模拟逐层建设的过程TreeNode* buildTreeByLevel(int arr[], int n) { if (n 0) return NULL; TreeNode** nodes (TreeNode**)malloc(sizeof(TreeNode*) * n); for (int i 0; i n; i) { if (arr[i] -1) { nodes[i] NULL; } else { nodes[i] (TreeNode*)malloc(sizeof(TreeNode)); nodes[i]-data arr[i]; nodes[i]-left nodes[i]-right NULL; } } for (int i 0; i n; i) { if (nodes[i] NULL) continue; int leftIdx 2 * i 1; int rightIdx 2 * i 2; if (leftIdx n) nodes[i]-left nodes[leftIdx]; if (rightIdx n) nodes[i]-right nodes[rightIdx]; } return nodes[0]; }这种方式的好处是你给的数组天然就是一棵树从上到下、从左到右的映射代码写起来也不容易绕晕。对于完全二叉树尤其方便直接在数组下标里找孩子就行。缺点是如果树是稀疏的数组里会填充大量空节点浪费空间。2.4 用户交互式创建边输入边建树有些教材喜欢让用户从键盘输入每读一个数据就创建节点遇到特定字符就返回空。这种写法在教学演示里很常见实际项目里少用——毕竟没有人愿意在命令行里手敲一长串序列去建一棵树。但你面试或考试时可能被要求写这种我贴一段代码供参考TreeNode* inputTree() { string s; cin s; if (s #) return NULL; TreeNode* node new TreeNode(stoi(s)); node-left inputTree(); node-right inputTree(); return node; }递归结构一目了然但使用体验真的挺原始只适合学习阶段或者OJ题目的格式要求。3. 文本显示为什么值得单独拿出来聊我刚学二叉树那会儿最痛苦的不是建树也不是遍历而是调试。建完树之后我想看看树长什么样结果只能通过遍历结果印出来比如前序遍历: 1 2 4 5 3 中序遍历: 4 2 5 1 3 后序遍历: 4 5 2 3 1你说这能看出结构吗能看出来一丁点但非常吃力。一旦树深了、节点多了根本分不清谁是谁的左孩子、谁是谁的右孩子。打印遍历序列只能验证遍历逻辑对不对没法直观看到树长什么样。所以我在实际做项目、写算法题的时候一定会写一个文本显示函数。把树用类似下面这种形式打出来1 / \ / \ 2 3 / \ / \ 4 5 6 7这种形式的输出在终端里一看就知道树长什么样调试效率直线提升。而且它不依赖任何第三方图形库纯文本就能搞定这在写OJ题、调试本地代码、甚至写课程报告的时候都特别实用。3.1 核心难点怎么算每个节点的坐标要把树打印成上面的形状你得先想明白一件事每个节点应该放在哪一行的哪个位置。两个核心参数行号就是节点所在的深度根在第0层往下递增。列号节点在这一行里的横向位置。列号怎么定如果你观察上面的输出会发现一个规律每个节点的中心位置正好等于它的左子树最右节点的位置和右子树最左节点的位置的中间点。换句话说你要想精确排布得先知道左子树和右子树各自占多宽。3.2 一种足够好用的简单方案直接精确计算每个节点的坐标有点繁琐我近几年在实际中用得最多的反而是一种足够好的方案构建一个二维字符画布按递归方式填充节点。步骤分三步走计算树的高度确认需要多少行画布。给每个节点分配列位置用递归让每个节点落在左右子树中点。填充画布逐行输出。先看树高度的计算int height(TreeNode* root) { if (root NULL) return 0; int leftH height(root-left); int rightH height(root-right); return (leftH rightH ? leftH : rightH) 1; }再看横向位置的分配。注意这里把每个位置横向步长设为2的整数倍这样比较美观void assignPos(TreeNode* node, int depth, int pos, vectorvectorstring board) { if (node nullptr) return; board[depth][pos] to_string(node-data); assignPos(node-left, depth 1, pos - (1 (height(node-left) - 1)), board); assignPos(node-right, depth 1, pos (1 (height(node-right) - 1)), board); }呃这套方案虽然可行但里面牵扯到多次求高度写起来并不轻松而且边界情况容易出错如单支树、只有右子树的树。后来我换了思路直接用中序遍历下标来定位每个节点。3.3 中序下标定位法我的主要方案中序遍历的特点是左根右。如果你把一棵二叉树的中序遍历结果写出来会发现每个节点在序列里的位置就是它在水平方向上的坐标如果每个节点宽度一致的话。这个思路帮我省去了大量计算。比如下面这棵树4 / \ 2 6 / \ / \ 1 3 5 7中序遍历结果是1 2 3 4 5 6 7。你会发现节点4正好在中间左边三个节点、右边三个节点。这个排列天然符合内聚的树形展示。那么具体怎么做呢第一步中序遍历整棵树给每个节点一个水平索引0到n-1。第二步按照节点的深度和水平索引把节点字符串放进一个二维矩阵中。第三步在节点之间画斜线和竖线把父子关系连起来。不过在实践中画连线这个环节真的很容易翻车尤其是字符宽度不对齐的时候。所以我的建议是先不画连线只显示节点的位置这已经能看清楚树的形状了。void inorderIndex(TreeNode* node, int idx, unordered_mapTreeNode*, int posMap) { if (!node) return; inorderIndex(node-left, idx, posMap); posMap[node] idx; inorderIndex(node-right, idx, posMap); } void printTreeText(TreeNode* root, int height, int totalWidth) { vectorvectorstring canvas(height, vectorstring(totalWidth * 2 1, )); queuepairTreeNode*, int q; // pair: 节点, 深度 q.push({root, 0}); unordered_mapTreeNode*, int posMap; int idx 0; inorderIndex(root, idx, posMap); while (!q.empty()) { auto [node, depth] q.front(); q.pop(); if (!node) continue; int col posMap[node]; canvas[depth][col * 2] to_string(node-data); q.push({node-left, depth 1}); q.push({node-right, depth 1}); } for (auto row : canvas) { for (auto cell : row) cout cell; cout endl; } }这段代码打印出来是这个效果节点数值两位数时对齐问题还比较粗糙但结构能看到4 2 6 1 3 5 7节点的前进位置和层次关系一眼就能看出来调试够用了。3.4 更精细的显示包含连线的版本只有节点位置看起来还是不够直观尤其是树的深度超过三层之后很难判断某个节点到底是上一行哪个节点的孩子。所以我一般会给文本显示加上连线。核心思路是在相邻两层之间插入一行专门画连线的行斜杠或竖线。规则如下父节点在画布的中心位置p。左孩子中心位置为l右孩子中心位置为r。连接线的行里在(p l) / 2位置放/在(p r) / 2位置放\中间用-连起来。代码示意void drawConnection(vectorstring line, int parentPos, int childPos, char slash) { int start min(parentPos, childPos); int end max(parentPos, childPos); for (int i start; i end; i) { if (i parentPos) continue; if (i (parentPos childPos) / 2) line[i] slash; else line[i] -; } }这样打印出来就是下面这种效果4 / \ / \ 2 6 / \ / \ 1 3 5 7细看你会发现连线的斜线位置大概在两个节点的中间偏移一点。如果你把每个节点占位固定为3个字符比如数值左补空格到3位那么斜线的位置偏移量是可以精确算出来的。这里有个要点数值位数不一样的时候画出来的斜线会歪所以尽量固定每个节点的显示宽度比如用setw(4)格式化。3.5 为什么很多教材不给你这种打印代码说句实在话很多教材和网课讲二叉树就停在遍历那章打印文本显示功能要么不讲要么只给一张截图。原因是写一个健壮的打印函数比写十遍前序遍历要麻烦得多而且它涉及字符串排版这类非算法内容授课老师觉得浪费时间。但作为学习者或者从业者我强烈建议你把这块补上。我的理由很简单你写二叉树算法题的时候能快速看到每一步中间状态脑子不用空转。你调试AVL树、红黑树的时候没有可视化旋转操作根本看不出问题。你写课程设计、实验报告的时候一个漂亮的文本树截图比罗列一万字更有说服力。4. 完整示例创建 显示的实战综合我直接把一份可运行的完整程序拆解出来。这份代码我改过很多遍实际写题、写课设的时候都用过基本稳定。下面以C为例#include iostream #include vector #include queue #include string #include iomanip #include cmath using namespace std; struct TreeNode { int val; TreeNode *left, *right; TreeNode(int v) : val(v), left(nullptr), right(nullptr) {} }; // 1. 用扩展前序序列创建二叉树-1表示空 TreeNode* buildByPre(vectorint data, int idx) { if (idx data.size() || data[idx] -1) { idx; return nullptr; } TreeNode* node new TreeNode(data[idx]); node-left buildByPre(data, idx); node-right buildByPre(data, idx); return node; } // 2. 计算树高用于确定画布行数 int getHeight(TreeNode* root) { if (!root) return 0; return 1 max(getHeight(root-left), getHeight(root-right)); } // 3. 中序遍历打点给每个节点一个水平坐标 void inorderMark(TreeNode* node, int cnt, vectorint pos) { if (!node) return; inorderMark(node-left, cnt, pos); pos.push_back(cnt); cnt; inorderMark(node-right, cnt, pos); } // 4. 层序遍历填充画布 void printTree(TreeNode* root) { int h getHeight(root); if (h 0) return; // 统计节点个数 int totalCount 0; queueTreeNode* countQ; countQ.push(root); while (!countQ.empty()) { TreeNode* cur countQ.front(); countQ.pop(); totalCount; if (cur-left) countQ.push(cur-left); if (cur-right) countQ.push(cur-right); } // 中序标号给每个节点一个水平位置 vectorint seq; int cnt 0; inorderMark(root, cnt, seq); // 用层序遍历映射节点到画布坐标 int width totalCount * 2 2; vectorvectorstring board(h, vectorstring(width, )); queuepairTreeNode*, int q; q.push({root, 0}); int curIndex 0; while (!q.empty()) { auto [node, depth] q.front(); q.pop(); if (!node) continue; int col0 seq[curIndex]; board[depth][col0 * 2] to_string(node-val); q.push({node-left, depth 1}); q.push({node-right, depth 1}); } // 打印画布 for (int i 0; i h; i) { for (int j 0; j width; j) { cout board[i][j]; } cout endl; } } int main() { vectorint data {1, 2, 4, -1, -1, 5, -1, -1, 3, -1, -1}; int idx 0; TreeNode* root buildByPre(data, idx); printTree(root); return 0; }代码有很多地方可以根据实际需求微调比如用char画斜线还是用/和\配合连字符节点之间用两个空格还是一个tab空树怎么显示等等。我这里给的是最基础的可运行版本保证你抄下来直接能跑。4.1 这份代码的关键设计点中序标号为什么是正确的水平坐标因为中序遍历天然把一棵树按从左到右的顺序输出。如果两个节点在中序序列里有先后关系那么它们在画布上一定有左右关系。这种坐标分配方式和树的宽度优先布局是兼容的只要你不去画连线单纯看位置关系它是最简单、最不容易出错的。层序遍历的作用是什么层序遍历保证每一层的节点从左到右顺序打印。你配合中序坐标生成二维数组时根本不用管父子连线问题先占位后显示逻辑非常清晰。left和right为空时要不要占位如果你打印的是满二叉树每一层的空位都是自然占好的看起来会很舒服。但如果你打印的是只有右孩子的树比如退化成链表的树那么左侧会空出一大片。这是正常的也是你肉眼判断树形的重要线索——如果打印出来的树左边大量空位说明这棵树严重右倾这时候大概率是插入逻辑写歪了。5. 常见的坑打印不对先查这三处我在写这套打印代码和调试二叉树的时候反复翻车。总结一下典型问题5.1 节点值位数不一时画布对不齐你建树时存的是int有的值是1有的是10有的是100。如果用to_string(node-val)直接放进字符串画布你会发现第二层的节点和第三层的节点横向错位因为10占两格1占一格。解决办法很粗暴格式化每个节点为固定宽度比如统一占3格string formatVal(int v) { string s to_string(v); while (s.size() 3) s s; return s; }当然如果节点数量级大到三位数甚至四位宽度也要跟着调整。我在代码里通常设为4宁可宽松一点也不要挤在一起。5.2 递归建树时下标不更新看这段错误示范TreeNode* build(int arr[], int idx, int n) { if (idx n) return NULL; ... TreeNode* left build(arr, idx 1, n); TreeNode* right build(arr, idx 1, n); }看起来好像没问题其实大错特错。因为你传的是值每层递归都有自己的idx副本你idx1传给下一层但下一层递归返回后当前层的idx并没有改变。左子树和右子树建的时候用的是同一个位置数组根本不会被向后读取。正确做法是传指针或引用TreeNode* build(int arr[], int* idx, int n) { if (*idx n) return NULL; ... TreeNode* left build(arr, idx, n); TreeNode* right build(arr, idx, n); }C里也可以用int idx写起来更省事。这个坑极其隐蔽因为代码编译不会报错运行也不会立刻崩溃只是树建出来完全不符合预期。5.3 空节点用0还是-1很多人习惯用0表示空节点。这有个隐患如果二叉树里允许存储0值比如树的节点值范围包含0那你的系统就无法区分值为0的节点和空节点。所以我的建议是除非题目明确规定0代表空否则用-1或者用一个特殊常数比如INT_MIN。如果节点的值可能出现任意整数那你最好改用结构体加布尔标志位或者用字符串序列null来标记空节点。这个问题在OJ题里见得特别多一不注意就超时或者越界。5.4 打印出来的树斜线是歪的画连线的时候如果每个节点宽度不统一或者跨度为偶数时(parentPos childPos) / 2是小数那么斜线就是歪的。想要看到漂亮的树形图最简单的办法是不画连线只靠位置分布来辨认结构。实际上你会发现在文本模式下位置排布已经足够传递信息了。如果一定要连线建议节点占位统一4个字符并且横向间隔也统一为4的倍数这样斜线偏移基本是可控的。6. 显示功能的进阶用文本模拟更多树结构学会了基础打印一个很自然的扩展是支持打印带括号的前缀表达式树或者JSON风格的树结构。6.1 括号嵌套式显示对于不想追求图形化输出的场景你可以用嵌套括号来表示树。比如1(2(4,5),3)这种表示法简洁、省空间特别适合单元测试里断言树的结构。它的实现也很简单本质上就是递归输出void printWithParen(TreeNode* node) { if (!node) { cout null; return; } cout node-val; if (node-left || node-right) { cout (; printWithParen(node-left); cout ,; printWithParen(node-right); cout ); } }输出结果1(2(4,5),3)。看完这个字符串你虽然看不到图的形状但恢复树结构却是完全没问题的——因为它本身就是一棵树的序列化表示。6.2 层序序列化另一个常用到爆的文本显示格式是层序序列化。比如LeetCode风格的[1,2,3,null,null,4,5]这种格式的好处是机器可读、便于网络传输或存储坏处是人眼读起来依然不够直观。所以我在本地调试时通常同时打印两种层序序列化用于断言图形化文本用于肉眼观察。vectorint levelOrderSerialize(TreeNode* root) { vectorint res; queueTreeNode* q; q.push(root); while (!q.empty()) { TreeNode* cur q.front(); q.pop(); if (!cur) { res.push_back(-1); } else { res.push_back(cur-val); q.push(cur-left); q.push(cur-right); } } // 去掉末尾多余的-1 while (!res.empty() res.back() -1) res.pop_back(); return res; }6.3 左旋90度的树横着打印有些终端宽度大竖直打印树会占用很多行而横着打印也是一种选择。所谓横着打印就是让根在左侧子节点往右延伸7 / 3 / \ 1 5实现方法从根出发右子树在先、左子树在后逆中序递归输出。每个深度前面加一圈缩进。这样树的结构同样一目了然而且实现代码比自上而下的画布方案还要短void printTreeHorizontal(TreeNode* node, int level) { if (!node) return; printTreeHorizontal(node-right, level 1); for (int i 0; i level; i) cout ; cout node-val endl; printTreeHorizontal(node-left, level 1); }这个函数我经常用在调试红黑树旋转的时候——横着打一眼就能看到左边多深、右边多深比自上而下排版更节省脑力。7. 实际排错一个案例带你走一遍我记得有一次写一个表达式树求值的作业建树后一运行就崩百思不得其解。当时我的代码里建树用的是值传递下标第5.2节那个坑导致左右子树全部变成同一个节点递归无限膨胀栈溢出崩了。我当时就是用文本打印函数输出了如下内容5 5 5 5所有节点全是5这明显不对。如果我只打印遍历序列看到的是5 5 5 5根本分辨不出问题。但图形化显示帮我迅速锁定了每次读取的都是同一个位置这个bug。还有一个经典案例在某个课程设计里写删除二叉树节点删完后打印出来的树中间少了一层我一开始以为是删除逻辑错检查半天没问题。后来发现是我的显示函数里层序遍历把空节点也push进了队列导致画布下标错位。所以不要轻易相信输出有时候是显示代码的问题不是树本身的问题。排查这类问题我有一个固定流程先打印层序序列化数组验证树结构和理论一致。再用图形化打印看节点位置是否合理。如果两者出现矛盾先信任序列化数组因为它的逻辑最简单、最容易人工核验。最后再检查显示代码的宽度计算和下标索引。8. 从创建和显示延伸出去你还能拿它做什么把创建和显示这关过了之后你应该趁热打铁把下面这几个方向都补一补。它们全都依托于你已经掌握的建树和遍历基础遍历的三种递归写法前序、中序、后序务必做到随手能写还要能解释清楚递归栈的变化。这是所有二叉树算法的基础。非递归遍历参考栈指针的思路尤其是中序和前序非递归写法能帮你在OJ题中避免递归栈溢出。层序遍历用队列实现这个在求树宽、求层平均值、之字形打印等题目中都要用到。树的序列化和反序列化这是创建显示的进阶应用。你学会了文本显示自然能理解序列化的重要性——网络传输、持久化、测试中构造树全都要靠它。二叉树的重建给定前序中序或者后序中序重建二叉树的题目面试几乎必考。你如果亲手写过创建二叉树的代码这一题上手会快很多因为它们本质上是同一套递归思维。我个人在带新人的时候第一课就让他们把创建 文本显示这个小工具写进自己的代码库。往后做任何需要二叉树的题目第一件事就是把它调出来把测试用例的树可视化再基于可视化去调逻辑。这么做的效率比对着编译器空想高十倍。说到底二叉树没有多玄乎它就是把数据组织成了左小右大或父子层级的结构。难的地方在于你脑子里能不能看到那棵树。写一个文本显示函数就是逼自己把树的形状真正画出来。画出来了你会觉得二叉树不过如此。