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

《Java数据结构与算法》第四篇（三）二叉树遍历详解_CSDN文章

news 2026/6/1 0:22:24

Java数据结构之树：二叉树的三种遍历方法详解（递归与非递归实现）

一、二叉树遍历的定义与重要性

二叉树遍历（Binary Tree Traversal）是指按照某种顺序访问二叉树中的所有节点，使得每个节点都被访问一次且仅一次。遍历是二叉树最基本、最重要的操作，是后续进行二叉树搜索、修改、删除等操作的基础。

根据访问节点的顺序不同，二叉树的遍历主要分为三种方式：

前序遍历（Preorder Traversal）：根节点 → 左子树 → 右子树
中序遍历（Inorder Traversal）：左子树 → 根节点 → 右子树
后序遍历（Postorder Traversal）：左子树 → 右子树 → 根节点

每种遍历方式都有递归和非递归两种实现方法。递归实现简洁易懂，而非递归实现通过使用栈（Stack）数据结构来模拟递归过程，空间效率更高。

二、前序遍历（DLR）详解

2.1 前序遍历的定义

前序遍历（DLR，Data-Left-Right）是二叉树遍历中最直观的方式。其遍历规则为：

首先访问根节点
然后遍历左子树
最后遍历右子树

对于测试用例ABD##E##C##构建的二叉树：

A / \ B C / \ D E

前序遍历的结果为：A B D E C

2.2 递归实现

publicvoidDLR(BiTreeNoderoot){if(root!=null){System.out.print(root.data+" ");// 访问根节点DLR(root.lchild);// 遍历左子树DLR(root.rchild);// 遍历右子树}}

代码分析：

递归实现非常简洁，只有三行核心代码
时间复杂度：O(n)，每个节点访问一次
空间复杂度：O(h)，h为树的高度，递归调用栈的深度

2.3 非递归实现（数组模拟栈）

publicvoidDLR2(){BiTreeNodestack[]=newBiTreeNode[20];// 使用数组模拟栈inttop=0;BiTreeNodecurr=root;while(curr!=null||top>0){if(curr!=null){System.out.print(curr.data+" ");// 访问当前节点stack[top++]=curr;// 当前节点入栈curr=curr.lchild;// 转向左子树}if(top>0){curr=stack[--top];// 出栈curr=curr.rchild;// 转向右子树}}}

2.4 非递归实现（Java Stack类）

publicStringDLR3(){StringBuilderresult=newStringBuilder();if(root==null){return"";}Stack<BiTreeNode>stack=newStack<>();stack.push(root);// 根节点入栈while(!stack.isEmpty()){BiTreeNodecurr=stack.pop();result.append(curr.data+" ");// 访问当前节点// 右子树先入栈（后处理）if(curr.rchild!=null){stack.push(curr.rchild);}// 左子树后入栈（先处理）if(curr.lchild!=null){stack.push(curr.lchild);}}returnresult.toString();}

注意：这里右子树先入栈，左子树后入栈，因为栈是后进先出（LIFO）的数据结构，这样才能保证先处理左子树。

三、中序遍历（LDR）详解

3.1 中序遍历的定义

中序遍历（LDR，Left-Data-Right）的特点是：

首先遍历左子树
然后访问根节点
最后遍历右子树

对于同一棵二叉树，中序遍历的结果为：D B E A C

重要特性：对于二叉搜索树（BST），中序遍历会得到有序的节点序列。

3.2 递归实现

publicvoidLDR(BiTreeNoderoot){if(root!=null){LDR(root.lchild);// 先遍历左子树System.out.print(root.data);// 再访问根节点LDR(root.rchild);// 最后遍历右子树}}

3.3 非递归实现

publicStringLDR2(){StringBuilderresult=newStringBuilder();if(root==null){return"";}Stack<BiTreeNode>stack=newStack<>();BiTreeNodecurr=root;while(!stack.isEmpty()||curr!=null){// 一直向左走到底while(curr!=null){stack.push(curr);curr=curr.lchild;}// 弹出栈顶节点并访问curr=stack.pop();result.append(curr.data+" ");// 转向右子树curr=curr.rchild;}returnresult.toString();}

算法思路：

从根节点开始，将路径上的所有节点入栈，直到最左边的叶子节点
弹出栈顶节点并访问
转向该节点的右子树，重复上述过程

四、后序遍历（LRD）详解

4.1 后序遍历的定义

后序遍历（LRD，Left-Right-Data）的顺序为：

首先遍历左子树
然后遍历右子树
最后访问根节点

对于同一棵二叉树，后序遍历的结果为：D E B C A

应用场景：后序遍历常用于需要先处理子节点再处理父节点的场景，如计算目录大小、释放树形结构内存等。

4.2 递归实现

publicvoidLRD(BiTreeNoderoot){if(root!=null){LRD(root.lchild);// 先遍历左子树LRD(root.rchild);// 再遍历右子树System.out.print(root.data);// 最后访问根节点}}

4.3 非递归实现（双栈法）

publicStringLRD2(){StringBuilderresult=newStringBuilder();if(root==null){return"";}Stack<BiTreeNode>stack1=newStack<>();// 辅助栈Stack<BiTreeNode>stack2=newStack<>();// 结果栈stack1.push(root);while(!stack1.isEmpty()){BiTreeNodecurr=stack1.pop();stack2.push(curr);// 将节点放入结果栈// 左子树先入栈if(curr.lchild!=null){stack1.push(curr.lchild);}// 右子树后入栈if(curr.rchild!=null){stack1.push(curr.rchild);}}// 从结果栈中弹出得到后序序列while(!stack2.isEmpty()){BiTreeNodecurr=stack2.pop();result.append(curr.data+" ");}returnresult.toString();}

4.4 非递归实现（单栈法）

publicStringLRD3(){StringBuilderresult=newStringBuilder();if(root==null){return"";}Stack<BiTreeNode>stack=newStack<>();BiTreeNodecurr=root;BiTreeNodeprev=null;// 记录上一个访问的节点while(!stack.isEmpty()||curr!=null){if(curr!=null){stack.push(curr);curr=curr.lchild;}else{BiTreeNodetemp=stack.peek();// 如果右子树存在且未被访问if(temp.rchild!=null&&prev!=temp.rchild){curr=temp.rchild;}else{// 访问该节点result.append(temp.data+" ");prev=stack.pop();}}}returnresult.toString();}

五、完整代码实现与测试

5.1 二叉树节点类

classBiTreeNode{chardata;// 节点数据BiTreeNodelchild,rchild;// 左右孩子指针// 默认构造函数publicBiTreeNode(){}// 带参数的构造函数publicBiTreeNode(chardata){this.data=data;lchild=null;rchild=null;}// 完整构造函数publicBiTreeNode(chardata,BiTreeNodelchild,BiTreeNoderchild){this.data=data;this.lchild=lchild;this.rchild=rchild;}}

5.2 二叉树的构建

publicvoidcreateBiTree(Stringinput){pi=0;root=createBiTreeHelper(input);num=countNodes(root);}privateBiTreeNodecreateBiTreeHelper(Stringinput){if(pi>=input.length()||input.charAt(pi)=='#'){pi++;returnnull;// #表示空节点}BiTreeNoderoot=newBiTreeNode(input.charAt(pi));++pi;root.lchild=createBiTreeHelper(input);// 递归构建左子树root.rchild=createBiTreeHelper(input);// 递归构建右子树returnroot;}