这篇文章主要介绍了java栈如何实现二叉树的非递归遍历，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。
计算
安全
数据库
网络和加速
企业服务
class Node{
public int val;
public Node left;
public Node right;
public Node(int v) {
val=v;
left=null;
right=null;
}
}
public class Main {
public static void main(String[] args) {
Node head =new Node(0);
Node node1=new Node(1);
Node node2=new Node(2);
Node node3=new Node(3);
Node node4=new Node(4);
Node node5=new Node(5);
Node node6=new Node(6);
head.left=node1;
head.right=node2;
node1.left=node3;
node1.right=node4;
node2.left=node5;
node2.right=node6;
pos2(head);
pos1(head);
in(head);
}
思想和流程
弹出就打印
如果有右子树，就压入
如果有左子树，就压入
public static void pos1(Node h) {
System.out.print("先序遍历 ");
if(h!=null) {
Stack<Node>stack =new Stack<Node>();
stack.push(h);
while(!stack.isEmpty()) {
h=stack.pop();
System.out.print(h.val+" ");
if(h.right!=null) {
stack.push(h.right);
}
if(h.left!=null) {
stack.push(h.left);
}
}
}
System.out.println();
}后序遍历
前序遍历的顺序是父节点，左，右，而后序遍历的顺序是左，右，父节点，也就是说前序遍历左右替换之后就是后序遍历的倒过来。所以只要把前序遍历时候左右子节点压栈的顺序调换一下，再用另一个栈储存，然后再弹出就是后序遍历了。在此代码就不多写了。
中序遍历
思路和流程
弹出就打印
整条左边界依次入栈
上一条件无法继续，弹出打印，开始右子树
public static void in(Node h) {
System.out.print("中序遍历 ");
if(h!=null) {
Stack<Node>stack =new Stack<Node>();
while(!stack.isEmpty()||h!=null) {
if(h!=null) {
stack.push(h);
h=h.left;
}else {
h=stack.pop();
System.out.print(h.val+" ");
h=h.right;
}
}
}
System.out.println();
}后序遍历变体
用一个Stack实现
思路是左节点没处理就处理左节点，左节点处理过了就处理右节点，右节点处理完了就返回。
public static void pos2(Node h) {
if(h!=null) {
Stack<Node>stack =new Stack<Node>();
stack.push(h);
Node c=null;//用c记录上一次被打印的节点
while(!stack.isEmpty()) {
c=stack.peek();
if(c.left!=null&&h!=c.left&&h!=c.right) {
stack.push(c.left);
}else if(c.right!=null&&h!=c.right) {
stack.push(c.right);
}else {
System.out.print(stack.pop().val+" ");
h=c;//记录本次被打印的节点
}
}
}
}打印结果
感谢你能够认真阅读完这篇文章，希望小编分享的“java栈如何实现二叉树的非递归遍历”这篇文章对大家有帮助，同时也希望大家多多支持亿速云，关注亿速云行业资讯频道，更多相关知识等着你来学习!
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
