Java中二叉树遍历的常用方法有哪些

这篇文章给大家分享的是有关Java中二叉树遍历的常用方法有哪些的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。

采用前序遍历、中序遍历、后续遍历实现时，即便采用不同的实现方式（递归方式、非递归），它们的算法结构是有很大的相似性。因而针对前三种的遍历我们会总结出对应通用的解决框架，便于在解决二叉树问题时进行使用。

递归方式

递归方式遍历二叉树时，无论是 前序遍历、中序遍历 还是 后续遍历 的方式，它们最大的区别就是对节点数据的访问位置不同。除此之外其结构完全一致，因而我们总结出如下的框架结构：

voidtraverse(TreeNoderoot){
//终止条件
if(root==null)return;
//前序遍历
traverse(root.left);
//中序遍历
traverse(root.right);
//后序遍历
}

对应注释的位置访问数据就可以实现不同的遍历方式。

例如，前序遍历：

voidtraverse(TreeNoderoot){
if(root==null)return;
visit(root);
traverse(root.left);
traverse(root.right);
}

同样的中序遍历：

voidtraverse(TreeNoderoot){
if(root==null)return;
traverse(root.left);
visit(root);
traverse(root.right);
}

后续遍历：

voidtraverse(TreeNoderoot){
if(root==null)return;
traverse(root.left);
traverse(root.right)
}

是否非常 easy！！

非递归方式

二叉树非递归遍历说实话有很多种实现方式，但本质上都是模拟整个遍历的过程来实现的。

为了便于理解，其中前序遍历、中序遍历、后序遍历我们采用一套类似的算法框架。

整个算法框架如下：

publicvoidtraverse(TreeNoderoot){
//边界判断
if(root==null){
return;
}
Stack<TreeNode>stack=newStack<>();
TreeNodecurrent=root;
while(current!=null||!stack.isEmpty()){
//节点非空时，证明父节点的左侧节点非空，直接入栈
if(current!=null){
//前序遍历visit(current)
stack.push(current);
current=current.left;
}else{
//节点为空，证明左侧节点为空，出栈，更换游标节点方向
current=stack.pop();
		//中续遍历visit(current);
current=current.right;
}
}
}

后序遍历它的遍历顺序为**"左--> 右--> 根"，较之与前序遍历的"根--> 左--> 右"，好像是有很大的相似性，我们能否针对上边的框架进行修改，使由前序遍历转换成后序遍历？？答案是肯定的，我们可以观察到，可以先求出遍历顺序是"根--> 右--> 左"**"的节点序列，再倒序，便刚好是后序遍历的顺序：左右根。而遍历顺序是根右左的话，很好办，从前序遍历的代码中改两行就是了。

故而，可以选择使用两个栈，其中一个用于遍历，另一个用于结果的倒序。

实现代码如下：

//使用双栈来实现后序遍历
publicvoidpostOrderTraverse(TreeNoderoot){
Stack<TreeNode>stack=newStack<>();
Stack<Integer>res=newStack<>();
TreeNodecur=root;
while(cur!=null||!stack.isEmpty()){
if(cur!=null){
stack.push(cur);
res.push(cur.val);
cur=cur.right;//修改处
}else{
cur=stack.pop();
cur=cur.left;//修改处
}
}
while(!res.isEmpty()){
visit(res.pop());
}
}

至此，非递归遍历完成，是不是也很 easy！！

下边我们可以看一下最后一种层次遍历

层次遍历

层次遍历本质上就是阉割版广度优先遍历，我们此处就直接给出 BFS 算法的框架：

/**
*给定起始节点start和目标节点target，返回其最短路径长度
**/
intBFS(Nodestart,Nodetarget){
Queue<Node>q;//核心数据结构
Set<Node>visited://某些情况下可以通过byte数组来进行代替
intstep=0;//记录扩散步数
//起始节点入队列
q.add(start);
visited.offer(start);
while(qnotempty){
//必须要用sz来保存q.size()，然后扩散sz不能直接使用q.size()
intsz=q.size();
//将队列中的节点进行扩散
for(inti=0;i<sz;i++){
Nodecur=q.poll();
//目标节点判断
if(curistarget){
returnstep;
}
//邻接结点入队列
for(Noden:cur.adjs){
//未访问节点入队列
if(nisnotintvisited){
visitd.add(n);
q.offer(n);
}
}
}
//更新步数
step++;
}
}

此处我们借助 BFS 的框架，直接给出其实现方法：

voidLevelOrder(TreeNoderoot){
//初始化栈，并放入
Queue<TreeNode>queue;
queue.add(root);
while(!queue.isEmpty()){
//出栈
TreeNodecur=queue.poll();
//访问节点
visit(cur);
//向下一层级扩散
if(cur.left!=null)queue.add(cur.left);
if(cur.right!=null)queue.add(cur.right);
}
}

较之于 BFS，我们会发现，层次遍历，少了好多东西，比如不需要 visited 来标记已访问的节点（二叉树本身结构的特点，不可能出现重复遍历），也不需要将队列中的节点进行扩散等。

感谢各位的阅读！关于“Java中二叉树遍历的常用方法有哪些”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！