Loading... ## 二叉树遍历 **1.以根访问顺序决定是什么“序”遍历(仅适用于前序,中序,后序)** **2.左子树优先于右子树(一般遍历均满足此条件)** ---------- ## DFS深度优先搜索 Depth-First-Search。 一种用于遍历或搜索树或图的算法。这个算法会尽可能深的搜索树的分支。 一般步骤(非递归方法会用到栈)为 1. 首先将根节点放入stack中。 2. 从stack中取出第一个节点,并检验它是否为目标。 * 如果找到目标,则结束搜寻并回传结果。 * 否则将它某一个尚未检验过的直接子节点加入stack中。 3. 重复步骤2。 4. 如果不存在未检测过的直接子节点。 * 将上一级节点加入stack中。 * 重复步骤2。 5. 重复步骤4。 6. 若stack为空,表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。 #### 1.前序遍历 符合DFS深度优先搜索的一种二叉树遍历算法。 先访问根节点,再前序遍历左节点,再前序遍历右节点。 * 递归实现 ```java public class BinaryTreeNode { public int val; public BinaryTreeNode left; public BinaryTreeNode right; public BinaryTreeNode(int val){ this.val = val; left = null; right = null; } public static void preorderTraversal(BinaryTreeNode root){ if(root == null){ return; } System.out.println(root.val); preorderTraversal(root.left); preorderTraversal(root.right); } } ``` * 非递归实现 ```java public static void preorderTraversal(BinaryTreeNode root){ if(root == null){ return; } // Stack<BinaryTreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()){ BinaryTreeNode node = stack.pop(); System.out.println(node.val); if(node.right != null){ stack.push(node.right); } if(node.left != null){ stack.push(node.left); } } } ``` * 实测 ```java /****** 3 / \ 1 4 / \ / \ -1 2 ******/ //打印的结果为:3 1 -1 2 4 BinaryTreeNode.preorderTraversal(root); ``` #### 2.中序遍历 符合DFS深度优先搜索的一种二叉树遍历算法。 先中序遍历左子树,再访问根节点,再中序遍历右节点。 * 递归实现 ```java public static void inorderTraversal(BinaryTreeNode root){ if(root == null){ return; } inorderTraversal(root.left); System.out.println(root.val); inorderTraversal(root.right); } ``` * 实测 ```java /*************************** 3 / \ 1 4 / \ / \ -1 2 *************************/ //打印的结果为:-1 1 2 3 4 //可以看出中序遍历能将二叉搜索树按大小顺序遍历 BinaryTreeNode.inorderTraversal(root); ``` #### 3.后序遍历 符合DFS深度优先搜索的一种二叉树遍历算法。 先后序遍历左子树,再后序遍历右子树,再访问根节点。 * 递归实现 ```java public static void postorderTraversal(BinaryTreeNode root){ if(root == null){ return; } postorderTraversal(root.left); postorderTraversal(root.right); System.out.println(root.val); } ``` * 实测 ```java /*************************** 3 / \ 1 4 / \ / \ -1 2 *************************/ //打印的结果为:-1 2 1 4 3 BinaryTreeNode.postorderTraversal(root); ``` ---------- ## BFS广度优先搜索 Breadth-First Search。简单的说,BFS是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。 一般步骤为 1. 首先将根节点放入队列中。 2. 从队列中取出第一个节点,并检验它是否为目标。 * 如果找到目标,则结束搜索并回传结果。 * 否则将它所有尚未检验过的直接子节点加入队列中。 3. 若队列为空,表示整张图都检查过了——亦即图中没有欲搜索的目标。结束搜索并回传“找不到目标”。 4. 重复步骤2。 #### 1.层次遍历 符合广度优先搜索的一种二叉树遍历算法。 ```java public static void levelOrderTraversal(BinaryTreeNode root){ if(root == null){ return; } Queue<BinaryTreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()){ System.out.println(queue.peek().val); BinaryTreeNode node = queue.peek(); if(node.left != null){ queue.offer(node.left); } if(node.right != null){ queue.offer(node.right); } queue.poll(); } } ``` * 实测 ```java /*************************** 3 / \ 1 4 / \ / \ -1 2 *************************/ //打印结果为:3 1 4 -1 2 BinaryTreeNode.levelOrderTraversal(root); ``` 最后修改:2020 年 07 月 07 日 09 : 17 AM © 允许规范转载