二叉树的四种遍历方式

1、前序遍历 前序遍历即先遍历完左子树，再访问父节点，最后遍历完右子树

public class T1 { static class Node { int val; Node left; Node right; public Node(int val,Node left,Node right) { this.left=left; this.right=right; this.val=val; } } public static void main(String[] args) { Node node1=new Node(7, null, null); Node node2=new Node(6, null, null); Node node3=new Node(5, null, null); Node node4=new Node(4, null, node1); Node node5=new Node(3, node2, null); Node node6=new Node(2, node4, node3); Node node7=new Node(1, node6, node5); printTree(node7); } static void printTree(Node node) { System.out.print(node.val+" "); if(node.left!=null) { printTree(node.left); } if(node.right!=null) { printTree(node.right); } } }

2、后序遍历 即先遍历完左子树，再遍历完右子树，最后访问父节点

static void printTree(Node node) { if(node.left!=null) { printTree(node.left); } if(node.right!=null) { printTree(node.right); } System.out.print(node.val+" "); }

3、中序遍历

static void printTree(Node node) { if(node.left!=null) { printTree(node.left); } System.out.print(node.val+" "); if(node.right!=null) { printTree(node.right); } }

4、层序遍历

static void printTree(Node node) { if(node==null) return; Queue<Node> q=new LinkedList<Node>(); q.offer(node); while(!q.isEmpty()) { int end=q.size(); int cnt=0; while(++cnt<=end) { Node head=q.poll(); System.out.print(head.val+" "); if(head.left!=null) q.offer(head.left); if(head.right!=null) q.offer(head.right); } System.out.println(); } }