服务器之家

服务器之家 > 正文

java栈实现二叉树的非递归遍历的示例代码

时间:2021-08-26 11:38     来源/作者:LuckyCCat

一般来说遍历二叉树用到递归,但是用Stack进行遍历也是一个不错的方法。

二叉树设置

  1. class Node{
  2. public int val;
  3. public Node left;
  4. public Node right;
  5.  
  6. public Node(int v) {
  7. val=v;
  8. left=null;
  9. right=null;
  10. }
  11. }
  12.  
  13. public class Main {
  14. public static void main(String[] args) {
  15. Node head =new Node(0);
  16. Node node1=new Node(1);
  17. Node node2=new Node(2);
  18. Node node3=new Node(3);
  19. Node node4=new Node(4);
  20. Node node5=new Node(5);
  21. Node node6=new Node(6);
  22. head.left=node1;
  23. head.right=node2;
  24. node1.left=node3;
  25. node1.right=node4;
  26. node2.left=node5;
  27. node2.right=node6;
  28. pos2(head);
  29. pos1(head);
  30. in(head);
  31. }

java栈实现二叉树的非递归遍历的示例代码

前序遍历

思想和流程

  • 弹出就打印
  • 如果有右子树,就压入
  • 如果有左子树,就压入
  1. public static void pos1(Node h) {
  2. System.out.print("先序遍历 ");
  3. if(h!=null) {
  4. Stack<Node>stack =new Stack<Node>();
  5. stack.push(h);
  6. while(!stack.isEmpty()) {
  7. h=stack.pop();
  8. System.out.print(h.val+" ");
  9. if(h.right!=null) {
  10. stack.push(h.right);
  11. }
  12. if(h.left!=null) {
  13. stack.push(h.left);
  14. }
  15. }
  16. }
  17. System.out.println();
  18. }

后序遍历

前序遍历的顺序是父节点,左,右,而后序遍历的顺序是左,右,父节点,也就是说前序遍历左右替换之后就是后序遍历的倒过来。所以只要把前序遍历时候左右子节点压栈的顺序调换一下,再用另一个栈储存,然后再弹出就是后序遍历了。在此代码就不多写了。

中序遍历

思路和流程

  • 弹出就打印
  • 整条左边界依次入栈
  • 上一条件无法继续,弹出打印,开始右子树
  1. public static void in(Node h) {
  2. System.out.print("中序遍历 ");
  3. if(h!=null) {
  4. Stack<Node>stack =new Stack<Node>();
  5. while(!stack.isEmpty()||h!=null) {
  6. if(h!=null) {
  7. stack.push(h);
  8. h=h.left;
  9. }else {
  10. h=stack.pop();
  11. System.out.print(h.val+" ");
  12. h=h.right;
  13. }
  14. }
  15. }
  16. System.out.println();
  17. }

后序遍历变体

用一个Stack实现
思路是左节点没处理就处理左节点,左节点处理过了就处理右节点,右节点处理完了就返回。

  1. public static void pos2(Node h) {
  2. if(h!=null) {
  3. Stack<Node>stack =new Stack<Node>();
  4. stack.push(h);
  5. Node c=null;//用c记录上一次被打印的节点
  6. while(!stack.isEmpty()) {
  7. c=stack.peek();
  8. if(c.left!=null&&h!=c.left&&h!=c.right) {
  9. stack.push(c.left);
  10. }else if(c.right!=null&&h!=c.right) {
  11. stack.push(c.right);
  12. }else {
  13. System.out.print(stack.pop().val+" ");
  14. h=c;//记录本次被打印的节点
  15. }
  16. }
  17. }
  18. }

打印结果

java栈实现二叉树的非递归遍历的示例代码

到此这篇关于java栈实现二叉树的非递归遍历的文章就介绍到这了,更多相关java实现二叉树的非递归遍历内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家!

原文链接:https://blog.csdn.net/VanGotoBilibili/article/details/115029281

相关文章

热门资讯

yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
2021年耽改剧名单 2021要播出的59部耽改剧列表
2021年耽改剧名单 2021要播出的59部耽改剧列表 2021-03-05
返回顶部