老程序员回炉补基础三二叉树——从递归遍历到非递归实现树是最让我感到脑力不够用的数据结构。递归遍历还好一旦去掉递归用栈模拟脑子里就像在走迷宫。但正是这种烧脑的过程让我对递归的本质有了真正深入的理解。二叉树节点publicclasstNodeT{privateTdata;privatetNodeTleftnull;privatetNodeTrightnull;privatetNodeTparentnull;publictNode(Tdata){this.datadata;}// getter/setter 省略...}一、递归遍历三种经典方式递归遍历是二叉树最基础的入门。publicclassmTreeT{privatetNodeTrootnull;// 前序遍历根 - 左 - 右publicvoidprescan(tNodeTr){if(r!null){System.out.print(r.getData(),);prescan(r.getLeft());prescan(r.getRight());}}// 中序遍历左 - 根 - 右publicvoidoscan(tNodeTr){if(r!null){oscan(r.getLeft());System.out.print(r.getData(),);oscan(r.getRight());}}// 后序遍历左 - 右 - 根publicvoidbscan(tNodeTr){if(r!null){bscan(r.getLeft());bscan(r.getRight());System.out.print(r.getData(),);}}}三种遍历的本质区别唯一区别就是访问根节点的时机1 / \ 2 3 / \ 4 5遍历方式访问顺序结果前序根→左→右1,2,4,5,3中序左→根→右4,2,5,1,3后序左→右→根4,5,2,3,1二、层序遍历BFS层序遍历用队列实现一层一层地输出publicvoidlscan(tNodeTr)throwsException{mQueuetNodeTlnewmQueuetNodeT();l.inQueue(newqNodetNodeT(r));while(l.getCurrSize()0){tNodeTtempl.outQueue().getData();System.out.print(temp.getData(),);if(temp.getLeft()!null)l.inQueue(newqNodetNodeT(temp.getLeft()));if(temp.getRight()!null)l.inQueue(newqNodetNodeT(temp.getRight()));}}这里直接复用了上一篇手写的mQueue。根入队→出队打印→左右孩子入队→循环。简单直观。三、非递归遍历用栈模拟递归这是我花时间最多的部分。递归遍历3分钟就能写完非递归遍历我写了整整一个下午。3.1 非递归前序遍历publicvoidprescanS(tNodeTr){System.out.print(r.getData(),);mStacktNodeTs1newmStacktNodeT();tNodeTpr;// 沿左子树一路到底边走边打印右孩子入栈while(p.getLeft()!null){System.out.print(p.getLeft().getData(),);if(p.getRight()!null)s1.push(newsNotetNodeT(p.getRight()));pp.getLeft();}// 弹栈处理每棵被暂存的右子树while(!s1.isNull()){ps1.pop().getData();if(p!null){System.out.print(p.getData(),);while(p.getLeft()!null){System.out.print(p.getLeft().getData(),);if(p.getRight()!null)s1.push(newsNotetNodeT(p.getRight()));pp.getLeft();}}}}思路前序遍历是根→左→右。沿左子树一路到底每遇到一个节点就打印这就是根同时把右孩子压栈保存等左子树走完了再处理右子树。3.2 非递归中序遍历publicvoidoscanS(tNodeTr){mStacktNodeTs1newmStacktNodeT();s1.push(newsNotetNodeT(r));tNodeTpr,qr;// 先沿左子树全部压栈while(p.getLeft()!null){s1.push(newsNotetNodeT(p.getLeft()));pp.getLeft();}while(!s1.isNull()){ps1.pop().getData();if(p!null){System.out.print(p.getData(),);// 弹出时才打印qp.getRight();if(q!nullq.getLeft()!null){s1.push(newsNotetNodeT(p.getRight()));while(q!nullq.getLeft()!null){s1.push(newsNotetNodeT(q.getLeft()));qq.getLeft();}}else{if(p.getRight()!null)s1.push(newsNotetNodeT(p.getRight()));}}}}思路中序遍历是左→根→右。先把左子树全部压栈然后弹一个打印一个每弹出一个节点就处理它的右子树同样先把右子树的左链路全部压栈。3.3 非递归后序遍历publicvoidbscanS(tNodeTr){mStacktNodeTs1newmStacktNodeT();s1.push(newsNotetNodeT(r));tNodeTpr,qr;while(p.getLeft()!null){s1.push(newsNotetNodeT(p.getLeft()));pp.getLeft();}while(!s1.isNull()){ps1.pop().getData();// 有右孩子且未处理 → 需要先处理右子树if(p!nullp.getRight()!null){// 压入一个只含数据、没有子节点的标记节点s1.push(newsNotetNodeT(newtNodeT(p.getData())));qp.getRight();if(q!nullq.getLeft()!null){s1.push(newsNotetNodeT(p.getRight()));while(q!nullq.getLeft()!null){s1.push(newsNotetNodeT(q.getLeft()));qq.getLeft();}}else{if(p.getRight()!null)s1.push(newsNotetNodeT(p.getRight()));}}else{// 没有右孩子或是标记节点 → 打印System.out.print(p.getData(),);}}}思路后序遍历是左→右→根是最难的非递归遍历。核心难点是弹出栈顶节点时不知道它的右子树是否已经处理过了。我的解决方案是引入一个标记节点当弹出节点有右孩子时不直接打印而是把一个只含数据、不含子节点的副本压回栈中然后先处理右子树。下次弹到这个标记节点时它没有右孩子直接打印。三种非递归遍历对比遍历何时打印栈的作用难度前序入栈前就打印保存右子树简单中序弹栈时打印保存左链路中等后序弹栈且右子树处理完才打印保存待回溯节点困难四、由前序中序还原二叉树这是树的另一个经典问题给定前序遍历和中序遍历序列还原出原始二叉树。publicvoidcreateByPreAndMid(tNodeTr,Stringpre,Stringmid){if(pre.length()0){intcpre.indexOf(,);StringsR;if(c0){sRpre.substring(0,c);}else{sRpre;}r.setData((T)sR);// 在中序序列中找到根的位置划分左右子树cmid.indexOf(,sR,);StringsmL,smR,spL,spR,a;if(c0){cmid.indexOf(sR,);smL;if(c0){smR;}else{smRmid.substring(c1sR.length(),mid.length());}}else{smLmid.substring(0,c);smRmid.substring(c2sR.length(),mid.length());}// ... 根据 smL 的长度从 pre 中截取对应的左子树前序序列// 递归构建左右子树if(spL!nullspL.length()0){tNodeTtnewtNodeT(null);r.setLeft(t);createByPreAndMid(t,spL,smL);}if(spR!nullspR.length()0){tNodeTtnewtNodeT(null);r.setRight(t);createByPreAndMid(t,spR,smR);}}}核心原理前序1,2,4,8,16,17,9,18,19,5,10,20,11,3,6,12,13,7,14,15 中序16,8,17,4,18,9,19,2,20,10,5,11,1,12,6,13,3,14,7,15前序的第一个元素一定是根1在中序中找到根的位置左边是左子树的中序右边是右子树的中序根据左子树的节点数量从前序序列中截取对应长度得到左子树的前序递归处理左右子树实现中的坑这个实现是所有代码中最复杂的部分之一mTree.java:69-154字符串的切割处理很容易出错。因为我的输入格式是逗号分隔的字符串而不是字符数组所以边界处理第一个元素、最后一个元素需要特别小心。说实话这段代码写得不够优雅。如果重新来过我会用字符数组或者 List 作为输入而不是用字符串截取。但这也正是学习过程的真实写照——先求正确再求优雅。五、计算树的高度publicintgetLevel(tNodeTr){intleft0,right0;if(rnull){return0;}else{leftgetLevel(r.getLeft())1;rightgetLevel(r.getRight())1;}returnleftright?left:right;}简洁的递归树的高度 max(左子树高度, 右子树高度) 1。架构师视角为什么树这么重要应用场景背后的树结构MySQL 索引B 树Redis 有序集合跳表类似平衡树Java HashMapJDK 8红黑树链表转树Java ConcurrentHashMap红黑树文件系统目录多叉树XML/HTML DOMDOM 树编译器 AST抽象语法树不理解二叉树遍历你就无法理解 B 树的范围查询为什么高效不理解树的递归结构你就无法理解 AST 是怎么被解析器构建和遍历的。学习感悟二叉树是我觉得最值的章节。非递归遍历逼迫我彻底理解了递归的本质——递归就是系统帮你维护了一个栈。当你自己用栈来模拟递归时你会发现前序遍历为什么简单因为先处理自己这件事很直觉 || ZK 集群选举 | ZAB 协议树形 |理解了二叉树的遍历才能理解索引为什么用 B 树而不是哈希表理解了递归才能理解分布式系统的调用链路树。下一篇预告《老程序员回炉补基础四图——BFS、DFS 与拓扑排序》