二叉树的遍历

二叉树

    二叉树（Binary tree）是树形结构的一个重要类型，二叉树的特点是每个结点最多只能有两棵子树，且有左右之分，下图所示就是一棵二叉树。    

先序遍历

    前序遍历（DLR）是二叉树遍历的一种，也叫做先根遍历、前序遍历、前序周游，可记做根左右。前序遍历首先访问根结点，然后遍历左子树，最后遍历右子树。     对于上图中的二叉树，先序遍历结果为：1、2、4、5、3、6、7

中序遍历

    中序遍历（LDR）是二叉树遍历的一种，也叫做中根遍历、中序周游。可记做左根右，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。     对于上图中的二叉树，中序遍历结果为：4、2、5、1、6、3、7

后序遍历

    后序遍历（LRD）是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根。后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点。     对于上图中的二叉树，后序遍历结果为：4、5、2、6、7、3、1

 

遍历算法java代码实现

树的类结构

public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } }

递归版本

/** * 先序遍历 * @param treeNode 根节点 */ public void preOrderTraversal(TreeNode treeNode) { if (treeNode == null) { return; } System.out.println(treeNode.val); preOrderTraversal(treeNode.left); preOrderTraversal(treeNode.right); } /** * 中序遍历 * @param treeNode 根节点 */ public void inOrderTraversal(TreeNode treeNode) { if (treeNode == null) { return; } inOrderTraversal(treeNode.left); System.out.println(treeNode.val); inOrderTraversal(treeNode.right); } /** * 后序遍历 * @param treeNode 根节点 */ public void postOrderTraversal(TreeNode treeNode) { if (treeNode == null) { return; } postOrderTraversal(treeNode.left); postOrderTraversal(treeNode.right); System.out.println(treeNode.val); }

非递归版本

/** * 先序遍历 * * @param treeNode 根节点 */ public void preOrderTraversal(TreeNode treeNode) { if (treeNode == null) { return; } Deque<TreeNode> deque = new LinkedList<>(); deque.offerLast(treeNode); while (!deque.isEmpty()) { treeNode = deque.pollLast(); System.out.println(treeNode.val); if (treeNode.right != null) { deque.offerLast(treeNode.right); } if (treeNode.left != null) { deque.offerLast(treeNode.left); } } } /** * 中序遍历 * * @param treeNode 根节点 */ public void inOrderTraversal(TreeNode treeNode) { if (treeNode == null) { return; } Deque<TreeNode> deque = new LinkedList<>(); deque.offerLast(treeNode); while (!deque.isEmpty()) { if (treeNode != null && treeNode.left != null) { treeNode = treeNode.left; deque.offerLast(treeNode); continue; } treeNode = deque.pollLast(); System.out.println(treeNode.val); if (treeNode.right != null) { deque.offerLast(treeNode.right); treeNode = treeNode.right; } else { treeNode = null; } } } /** * 后序遍历 * * @param treeNode 根节点 */ public void postOrderTraversal(TreeNode treeNode) { if (treeNode == null) { return; } Deque<TreeNode> deque1 = new LinkedList<>(); Deque<Integer> deque2 = new LinkedList<>(); deque1.offerLast(treeNode); while (!deque1.isEmpty()) { treeNode = deque1.pollLast(); deque2.offerFirst(treeNode.val); if (treeNode.left != null) { deque1.offerLast(treeNode.left); } if (treeNode.right != null) { deque1.offerLast(treeNode.right); } } deque2.stream().forEach(System.out::println); }