这篇文章主要介绍了java栈如何实现二叉树的非递归遍历,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。二叉树设置class node{public int&
这篇文章主要介绍了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栈如何实现二叉树的非递归遍历”这篇文章对大家有帮助,同时也希望大家多多支持编程网,关注编程网精选频道,更多相关知识等着你来学习!
--结束END--
本文标题: java栈如何实现二叉树的非递归遍历
本文链接: https://www.lsjlt.com/news/268775.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-05-05
2024-05-05
2024-05-05
2024-05-05
2024-05-05
2024-05-05
2024-05-05
2024-05-05
2024-05-05
2024-05-05
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0