当前位置：首页 > news >正文

03-二叉树——从递归遍历到非递归实现

news 2026/5/7 4:20:03

老程序员回炉补基础（三）：二叉树——从递归遍历到非递归实现

树是最让我感到"脑力不够用"的数据结构。递归遍历还好，一旦去掉递归用栈模拟，脑子里就像在走迷宫。但正是这种"烧脑"的过程，让我对递归的本质有了真正深入的理解。

二叉树节点

publicclasstNode<T>{privateTdata;privatetNode<T>left=null;privatetNode<T>right=null;privatetNode<T>parent=null;publictNode(Tdata){this.data=data;}// getter/setter 省略...}

一、递归遍历（三种经典方式）

递归遍历是二叉树最基础的入门。

publicclassmTree<T>{privatetNode<T>root=null;// 前序遍历：根 -> 左 -> 右publicvoidprescan(tNode<T>r){if(r!=null){System.out.print(r.getData()+",");prescan(r.getLeft());prescan(r.getRight());}}// 中序遍历：左 -> 根 -> 右publicvoidoscan(tNode<T>r){if(r!=null){oscan(r.getLeft());System.out.print(r.getData()+",");oscan(r.getRight());}}// 后序遍历：左 -> 右 -> 根publicvoidbscan(tNode<T>r){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(tNode<T>r)throwsException{mQueue<tNode<T>>l=newmQueue<tNode<T>>();l.inQueue(newqNode<tNode<T>>(r));while(l.getCurrSize()>0){tNode<T>temp=l.outQueue().getData();System.out.print(temp.getData()+",");if(temp.getLeft()!=null)l.inQueue(newqNode<tNode<T>>(temp.getLeft()));if(temp.getRight()!=null)l.inQueue(newqNode<tNode<T>>(temp.getRight()));}}

这里直接复用了上一篇手写的mQueue。根入队→出队打印→左右孩子入队→循环。简单直观。

三、非递归遍历（用栈模拟递归）

这是我花时间最多的部分。递归遍历3分钟就能写完，非递归遍历我写了整整一个下午。

3.1 非递归前序遍历

publicvoidprescanS(tNode<T>r){System.out.print(r.getData()+",");mStack<tNode<T>>s1=newmStack<tNode<T>>();tNode<T>p=r;// 沿左子树一路到底，边走边打印，右孩子入栈while(p.getLeft()!=null){System.out.print(p.getLeft().getData()+",");if(p.getRight()!=null)s1.push(newsNote<tNode<T>>(p.getRight()));p=p.getLeft();}// 弹栈，处理每棵被暂存的右子树while(!s1.isNull()){p=s1.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(newsNote<tNode<T>>(p.getRight()));p=p.getLeft();}}}}

思路：前序遍历是"根→左→右"。沿左子树一路到底，每遇到一个节点就打印（这就是"根"），同时把右孩子压栈保存（等左子树走完了再处理右子树）。

3.2 非递归中序遍历

publicvoidoscanS(tNode<T>r){mStack<tNode<T>>s1=newmStack<tNode<T>>();s1.push(newsNote<tNode<T>>(r));tNode<T>p=r,q=r;// 先沿左子树全部压栈while(p.getLeft()!=null){s1.push(newsNote<tNode<T>>(p.getLeft()));p=p.getLeft();}while(!s1.isNull()){p=s1.pop().getData();if(p!=null){System.out.print(p.getData()+",");// 弹出时才打印q=p.getRight();if(q!=null&&q.getLeft()!=null){s1.push(newsNote<tNode<T>>(p.getRight()));while(q!=null&&q.getLeft()!=null){s1.push(newsNote<tNode<T>>(q.getLeft()));q=q.getLeft();}}else{if(p.getRight()!=null)s1.push(newsNote<tNode<T>>(p.getRight()));}}}}

思路：中序遍历是"左→根→右"。先把左子树全部压栈，然后弹一个打印一个，每弹出一个节点就处理它的右子树（同样先把右子树的左链路全部压栈）。

3.3 非递归后序遍历

publicvoidbscanS(tNode<T>r){mStack<tNode<T>>s1=newmStack<tNode<T>>();s1.push(newsNote<tNode<T>>(r));tNode<T>p=r,q=r;while(p.getLeft()!=null){s1.push(newsNote<tNode<T>>(p.getLeft()));p=p.getLeft();}while(!s1.isNull()){p=s1.pop().getData();// 有右孩子且未处理 → 需要先处理右子树if(p!=null&&p.getRight()!=null){// 压入一个只含数据、没有子节点的"标记节点"s1.push(newsNote<tNode<T>>(newtNode<T>(p.getData())));q=p.getRight();if(q!=null&&q.getLeft()!=null){s1.push(newsNote<tNode<T>>(p.getRight()));while(q!=null&&q.getLeft()!=null){s1.push(newsNote<tNode<T>>(q.getLeft()));q=q.getLeft();}}else{if(p.getRight()!=null)s1.push(newsNote<tNode<T>>(p.getRight()));}}else{// 没有右孩子或是标记节点 → 打印System.out.print(p.getData()+",");}}}

思路：后序遍历是"左→右→根"，是最难的非递归遍历。核心难点是：弹出栈顶节点时，不知道它的右子树是否已经处理过了。

我的解决方案是引入一个标记节点：当弹出节点有右孩子时，不直接打印，而是把一个"只含数据、不含子节点"的副本压回栈中，然后先处理右子树。下次弹到这个标记节点时，它没有右孩子，直接打印。

三种非递归遍历对比

遍历	何时打印	栈的作用	难度
前序	入栈前就打印	保存右子树	简单
中序	弹栈时打印	保存左链路	中等
后序	弹栈且右子树处理完才打印	保存待回溯节点	困难

四、由前序+中序还原二叉树

这是树的另一个经典问题：给定前序遍历和中序遍历序列，还原出原始二叉树。

publicvoidcreateByPreAndMid(tNode<T>r,Stringpre,Stringmid){if(pre.length()>0){intc=pre.indexOf(",");StringsR="";if(c>=0){sR=pre.substring(0,c);}else{sR=pre;}r.setData((T)sR);// 在中序序列中找到根的位置，划分左右子树c=mid.indexOf(","+sR+",");StringsmL="",smR="",spL="",spR="",a="";if(c<0){c=mid.indexOf(sR+",");smL="";if(c<0){smR="";}else{smR=mid.substring(c+1+sR.length(),mid.length());}}else{smL=mid.substring(0,c);smR=mid.substring(c+2+sR.length(),mid.length());}// ... 根据 smL 的长度从 pre 中截取对应的左子树前序序列// 递归构建左右子树if(spL!=null&&spL.length()>0){tNode<T>t=newtNode<T>(null);r.setLeft(t);createByPreAndMid(t,spL,smL);}if(spR!=null&&spR.length()>0){tNode<T>t=newtNode<T>(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(tNode<T>r){intleft=0,right=0;if(r==null){return0;}else{left=getLevel(r.getLeft())+1;right=getLevel(r.getRight())+1;}returnleft>right?left:right;}

简洁的递归：树的高度 = max(左子树高度, 右子树高度) + 1。

架构师视角：为什么树这么重要？

应用场景	背后的树结构
MySQL 索引	B+ 树
Redis 有序集合	跳表（类似平衡树）
Java HashMap（JDK 8+）	红黑树（链表转树）
Java ConcurrentHashMap	红黑树
文件系统目录	多叉树
XML/HTML DOM	DOM 树
编译器 AST	抽象语法树