树的四种遍历方式

目录

• 树的四种遍历方式
• • 先序遍历
  • 中序遍历
  • 后序遍历
  • 层序遍历

树的四种遍历方式

树的遍历方式一般来说有四种：

• 先序遍历
• 中序遍历
• 后序遍历
• 层序遍历

只有层序遍历是属于广度优先搜索，剩下三个都是深度优先搜索的。

先序遍历

以最简单的二叉树进行遍历测试，可能在树的构建上很粗糙，主要表达遍历树的思想。

• 树的结构类

package com.hnu;//数据结构树，封装
public class TreeNode {//结点值public int val;//左孩子public TreeNode left;//右孩子public TreeNode right;//结点初始化public TreeNode(int val) {this.val = val;}
}

package com.hnu;public class Main {//构造一棵树public static void main(String[] args) {TreeNode root = new TreeNode(1);TreeNode node2 = new TreeNode(2);TreeNode node3 = new TreeNode(3);TreeNode node4 = new TreeNode(4);TreeNode node5 = new TreeNode(5);TreeNode node6 = new TreeNode(6);TreeNode node7 = new TreeNode(7);root.left = node2;root.right = node3;node2.left = node4;node2.right = node5;node3.left = node6;node3.right = node7;preOrderTraversal(root);}//先序遍历   根，左孩子，右孩子public static void preOrderTraversal(TreeNode root){if(root == null){return;}System.out.print(root.val+" ");preOrderTraversal(root.left);preOrderTraversal(root.right);    }
}

中序遍历

• 只修改遍历方法即可

//中序遍历   左孩子，根，右孩子public static void preOrderTraversal(TreeNode root){if(root == null){return;}preOrderTraversal(root.left);System.out.print(root.val+" ");preOrderTraversal(root.right);    }

后序遍历

• 一样修改遍历方法

//后序遍历   左孩子，右孩子，根public static void preOrderTraversal(TreeNode root){if(root == null){return;}preOrderTraversal(root.left);preOrderTraversal(root.right);  System.out.print(root.val+" ");}

层序遍历

• 因为先进去的结点要先出来，所以采用队列辅助遍历

  package com.hnu;import java.util.*;public class Main {//构造一棵树public static void main(String[] args) {TreeNode root = new TreeNode(1);TreeNode node2 = new TreeNode(2);TreeNode node3 = new TreeNode(3);TreeNode node4 = new TreeNode(4);TreeNode node5 = new TreeNode(5);TreeNode node6 = new TreeNode(6);TreeNode node7 = new TreeNode(7);root.left = node2;root.right = node3;node2.left = node4;node2.right = node5;node3.left = node6;node3.right = node7;System.out.println(preOrderTraversal(root));}//层序遍历    每一层的结点遍历public static List<Integer> preOrderTraversal(TreeNode root){//辅助遍历Queue<TreeNode> queue = new LinkedList();//存储遍历的结点值List<Integer> array = new ArrayList<>();//遍历到末尾，返回if(root == null){return array;}//加入根queue.offer(root);//队列不空，一直循环while(!queue.isEmpty()){//取出结点TreeNode cur = queue.poll();//加入值array.add(cur.val);//左子树不空就加入队列，实现循环if(cur.left != null){queue.offer(cur.left);}//右子树不空就加入队列，实现循环if(cur.right != null){queue.offer(cur.right);}}//最后返回遍历后得到的值return array;}
  }
  

  

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！