devbox
秋刀鱼在做梦
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

二叉树的五种遍历方式_二叉树的遍历

作者：秋刀鱼在做梦 | 2024-06-28 07:37:47

赞

踩

二叉树的遍历

目录

1、前序遍历

（1）递归实现前序遍历

（2）非递归实现前序遍历

 2、中序遍历

（1）递归实现中序遍历

（2）非递归实现中序遍历

 3、后序遍历

（1）递归实现后序遍历

（2）非递归实现后序遍历

4、层序遍历

5、之字形遍历

二叉树是一种重要的数据结构，其遍历方式分为：深度遍历和广度遍历，深度遍历有前序、中序以及后序三种遍历方法，广度遍历即就是层次遍历。如下图：

  1. class TreeNode{
  2.     int val;
  3.     TreeNode left;
  4.     TreeNode right;
  5.  
  6.     public TreeNode(){
  7.     }
  8.  
  9.     public TreeNode(int val) {
  10.         this.val = val;
  11.     }
  12.  
  13.     public TreeNode(int val, TreeNode left, TreeNode right) {
  14.         this.val = val;
  15.         this.left = left;
  16.         this.right = right;
  17.     }
  18. }

1、前序遍历

遍历顺序：根节点---左子树---右子树

如上图，遍历结果应该为：12457836

（1）递归实现前序遍历

  1.     /**
  2.      * 递归实现前序遍历
  3.      * @param treeNode  树的根节点
  4.      */
  5.     public static void preOrder1(TreeNode treeNode){
  6.         // 若根节点为空，直接返回
  7.         if(treeNode == null){
  8.             return;
  9.         }
  10.         //打印根节点
  11.         System.out.print(treeNode.val + "\t");
  12.         // 遍历根节点的左子树
  13.         preOrder1(treeNode.left);
  14.         // 遍历根节点的右子树
  15.         preOrder1(treeNode.right);
  16.     }

（2）非递归实现前序遍历

非递归实现可以通过辅助栈或者辅助队列实现。以下代码为辅助栈的实现方式：

  1.     /**
  2.      * 非递归实现前序遍历
  3.      * @param treeNode  根节点
  4.      */
  5.     public static void preOrder2(TreeNode treeNode){
  6.         // 如果根节点为空，直接返回。
  7.         if(treeNode == null){
  8.             return;
  9.         }
  10.         // 辅助栈
  11.         Stack<TreeNode> stack = new Stack<>();
  12.         // 根节点入栈
  13.         stack.push(treeNode);
  14.         // 当栈不为空
  15.         while(!stack.isEmpty()){
  16.             //取出栈顶元素
  17.             TreeNode node = stack.pop();
  18.             //打印根节点
  19.             System.out.print(node.val + "\t");
  20.             // 如果使用的是辅助栈，则先将根节点的右子节点入栈；如果是辅助队列，则先将根节点的左子节点入队列。因为栈是先进后出，队列是先进入=先出
  21.             if(node.right != null){
  22.                 stack.push(node.right);
  23.             }
  24.             // 根节点的右子节点入栈
  25.             if(node.left != null){
  26.                 stack.push(node.left);
  27.             }
  28.         }
  29.     }

 2、中序遍历

遍历顺序：左子树---根节点---右子树

如上图，遍历结果应该为：42758136

（1）递归实现中序遍历

  1.     /**
  2.      * 递归实现中序遍历
  3.      * @param treeNode  树的根节点
  4.      */
  5.     public static void inOrder1(TreeNode treeNode){
  6.         // 若根节点为空，直接返回
  7.         if(treeNode == null){
  8.             return;
  9.         }
  10.         // 遍历根节点的左子树
  11.         inOrder1(treeNode.left);
  12.         //打印根节点
  13.         System.out.print(treeNode.val + "\t");
  14.         // 遍历根节点的右子树
  15.         inOrder1(treeNode.right);
  16.     }

（2）非递归实现中序遍历

  1.     /**
  2.      * 非递归实现中序遍历
  3.      * @param treeNode  根节点
  4.      */
  5.     public static void inOrder2(TreeNode treeNode){
  6.         // 如果根节点为空，直接返回。
  7.         if(treeNode == null){
  8.             return;
  9.         }
  10.         // 辅助栈
  11.         Stack<TreeNode> stack = new Stack<>();
  12.         // 临时指针
  13.         TreeNode cur = treeNode;
  14.         // 当栈不为空
  15.         while(cur != null || !stack.isEmpty()){
  16.             // 左节点入栈
  17.             while(cur != null){
  18.                 stack.push(cur);
  19.                 cur = cur.left;
  20.             }
  21.             //取出栈顶元素
  22.             cur = stack.pop();
  23.             //打印左节点
  24.             System.out.print(cur.val + "\t");
  25.             // 指向右节点
  26.             cur = cur.right;
  27.         }
  28.     }

 3、后序遍历

遍历顺序：左子树---右子树---根节点

如上图，遍历结果应该为：47852631

（1）递归实现后序遍历

  1.     /**
  2.      * 递归实现后序遍历
  3.      * @param treeNode  树的根节点
  4.      */
  5.     public static void postOrder1(TreeNode treeNode){
  6.         // 若根节点为空，直接返回
  7.         if(treeNode == null){
  8.             return;
  9.         }
  10.         // 遍历根节点的左子树
  11.         postOrder1(treeNode.left);
  12.  
  13.         // 遍历根节点的右子树
  14.         postOrder1(treeNode.right);
  15.         //打印根节点
  16.         System.out.print(treeNode.val + "\t");
  17.     }

（2）非递归实现后序遍历

 

  1.     /**
  2.      * 非递归实现后序遍历
  3.      * @param treeNode  根节点
  4.      */
  5.     public static void postOrder2(TreeNode treeNode){
  6.         // 如果根节点为空，直接返回。
  7.         if(treeNode == null){
  8.             return;
  9.         }
  10.         // 辅助栈
  11.         Stack<TreeNode> stack = new Stack<>();
  12.         // 临时指针
  13.         TreeNode cur = treeNode, pre = null;
  14.         // 当栈不为空
  15.         while(cur != null || !stack.isEmpty()){
  16.             // 左节点入栈
  17.             while(cur != null){
  18.                 stack.push(cur);
  19.                 cur = cur.left;
  20.             }
  21.             //取出栈顶元素
  22.             cur = stack.get(stack.size()-1);
  23.             if(cur.right == null || pre == cur.right){
  24.                 stack.pop();
  25.                 System.out.print(cur.val + "\t");
  26.                 pre = cur;
  27.                 cur = null;
  28.             }else{
  29.                 // 指向右节点
  30.                 cur = cur.right;
  31.             }
  32.         }
  33.     }

4、层序遍历

遍历顺序：逐层遍历

如上图，遍历结果应该为：12345678。通过辅助队列，在取出节点的同时，将当前节点的左右节点分别入队。

  1.     /**
  2.      * 层序遍历
  3.      * @param treeNode
  4.      */
  5.     public static void levelOrder(TreeNode treeNode){
  6.         //根节点为空，直接返回
  7.         if(treeNode == null){
  8.             return;
  9.         }
  10.         //辅助队列
  11.         Queue<TreeNode> queue = new LinkedList<>();
  12.         //根节点入队列
  13.         queue.offer(treeNode);
  14.         //当栈不为空
  15.         while(!queue.isEmpty()){
  16.             //取出队首元素
  17.             TreeNode node = queue.poll();
  18.             System.out.print(node.val + "\t");
  19.             //将节点的左节点入队
  20.             if(node.left != null){
  21.                 queue.offer(node.left);
  22.             }
  23.             //节点的右节点入队
  24.             if(node.right != null){
  25.                 queue.offer(node.right);
  26.             }
  27.         }
  28.     }

 

5、之字形遍历

这是牛客上的一道题。这个之字形遍历也可理解为Z字形遍历，以上树为例，其遍历结果为：1，3，2，4，5，6，8，7。本质还是二叉树的层序遍历，只不过在便利的时候，要将偶数层的节点逆序。

代码：

  1. import java.util.*;
  2.  
  3. /*
  4. public class TreeNode {
  5.     int val = 0;
  6.     TreeNode left = null;
  7.     TreeNode right = null;
  9.     public TreeNode(int val) {
  10.         this.val = val;
  12.     }
  14. }
  15. */
  16. public class Solution {
  17.     public ArrayList<ArrayList<Integer> > Print(TreeNode root) {
  18.         //存储结果
  19.         ArrayList<ArrayList<Integer>> result = new ArrayList<>();
  20.         //如果根节点为空，则直接返回
  21.         if(root == null){
  22.             return result;
  23.         }
  24.         //辅助队列
  25.         Queue<TreeNode> queue = new LinkedList<>();
  26.         //根节点入队
  27.         queue.offer(root);
  28.         //是否转向
  29.         boolean flag = false;
  30.         while(!queue.isEmpty()){
  31.             //获取队列长度
  32.             int size = queue.size();
  33.             //存储每一层的遍历结果
  34.             ArrayList<Integer> list = new ArrayList<>();
  35.             for(int i=0; i < size; i++){
  36.                 //取出队列元素
  37.                 TreeNode node = queue.poll();
  38.                 if(node == null){
  39.                     continue;
  40.                 }
  41.                 if(!flag){
  42.                     list.add(node.val);
  43.                 }else{
  44.                     list.add(0, node.val);
  45.                 }
  46.                 //左右节点各入队
  47.                 queue.offer(node.left);
  48.                 queue.offer(node.right);
  49.             }
  50.             //如果有值，存入结果集
  51.             if(list.size() > 0){
  52.                 result.add(list);
  53.             }
  54.             //转向
  55.             flag = !flag;
  56.         }
  57.         return result;
  58.     }
  59.  
  60. }

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号