- 浏览: 550115 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (267)
- 随笔 (4)
- Spring (13)
- Java (61)
- HTTP (3)
- Windows (1)
- CI(Continuous Integration) (3)
- Dozer (1)
- Apache (11)
- DB (7)
- Architecture (41)
- Design Patterns (11)
- Test (5)
- Agile (1)
- ORM (3)
- PMP (2)
- ESB (2)
- Maven (5)
- IDE (1)
- Camel (1)
- Webservice (3)
- MySQL (6)
- CentOS (14)
- Linux (19)
- BI (3)
- RPC (2)
- Cluster (9)
- NoSQL (7)
- Oracle (25)
- Loadbalance (7)
- Web (5)
- tomcat (1)
- freemarker (1)
- 制造 (0)
最新评论
-
panamera:
如果设置了连接需要密码,Dynamic Broker-Clus ...
ActiveMQ 集群配置 -
panamera:
请问你的最后一种模式Broker-C节点是不是应该也要修改持久 ...
ActiveMQ 集群配置 -
maosheng:
longshao_feng 写道楼主使用 文件共享 模式的ma ...
ActiveMQ 集群配置 -
longshao_feng:
楼主使用 文件共享 模式的master-slave,produ ...
ActiveMQ 集群配置 -
tanglanwen:
感触很深,必定谨记!
少走弯路的十条忠告
概述:
1、深度优先遍历(Depth-First-Search)常用的数据结构为栈,广度优先遍历(Breadth-First-Search)常用的数据结构为队列
2、深度优先遍历的思想是从上至下,对每一个分支一直往下一层遍历直到这个分支结束,然后返回上一层,对上一层的右子树这个分支继续深搜,直到一整棵树完全遍历,因此深搜的步骤符合栈后进先出的特点
广度优先遍历的思想是从左至右,对树的每一层所有结点依次遍历,当一层的结点遍历完全后,对下一层开始遍历,而下一层结点又恰好是上一层的子结点。因此广搜的步骤符合队列先进先出的思想
3、深度优先遍历:
对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次。对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次。
要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为前序遍历、中序遍历、后序遍历。
前序遍历:对任一子树,先访问根,然后遍历其左子树,最后遍历其右子树,前序就是根节点在最前:根->左->右。
中序遍历:对任一子树,先遍历其左子树,然后访问根,最后遍历其右子树,中序是根节点在中间:左->根->右。
后序遍历:对任一子树,先遍历其左子树,然后遍历其右子树,最后访问根,后序是根节点在最后:左->右->根。
除了利用栈以外,深度优先搜索也可以使用递归的方法。
4、广度优先遍历:
又叫层次遍历,从上往下对每一层依次访问,在每一层中,从左往右(也可以从右往左)访问结点,访问完一层就进入下一层,直到没有结点可以访问为止。又叫层次遍历,从上往下对每一层依次访问,在每一层中,从左往右(也可以从右往左)访问结点,访问完一层就进入下一层,直到没有结点可以访问为止。
5、深度优先搜索算法:不全部保留结点,占用空间少;有回溯操作(即有入栈、出栈操作),运行速度慢。
通常深度优先搜索法不全部保留结点,扩展完的结点从数据库中弹出删去,这样,一般在数据库中存储的结点数就是深度值,因此它占用空间较少。所以,当搜索树的结点较多,用其它方法易产生内存溢出时,深度优先搜索不失为一种有效的求解方法。
广度优先搜索算法:保留全部结点,占用空间大; 无回溯操作(即无入栈、出栈操作),运行速度快。
广度优先搜索算法,一般需存储产生的所有结点,占用的存储空间要比深度优先搜索大得多,因此,程序设计中,必须考虑溢出和节省内存空间的问题。但广度优先搜索法一般无回溯操作,即入栈和出栈的操作,所以运行速度比深度优先搜索要快些。
代码:
public class TreeTravel {
/**
* 前序遍历:递归法
*
* 递归的方法很容易实现,也很容易理解:我们先访问根节点,然后递归访问左子树,再递归访问右子树,即实现了根->左->右的访问顺序,
* 因为使用的是递归方法,所以每一个子树都实现了这样的顺序。
* @param root
* @return
*/
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
preorderHelper(root, result);
return result;
}
private void preorderHelper(TreeNode root, List<Integer> result) {
if (root == null) return;
result.add(root.val); // 访问根节点
preorderHelper(root.left, result); // 递归遍历左子树
preorderHelper(root.right, result); //递归遍历右子树
}
/**
* 前序遍历:迭代法
*
* 在迭代法中,我们使用栈来实现。由于出栈顺序和入栈顺序相反,所以每次添加节点的时候先添加右节点,再添加左节点。
* 这样在下一轮访问子树的时候,就会先访问左子树,再访问右子树:
*/
public List<Integer> preorderTraversal2(TreeNode root) {
List<Integer> result = new LinkedList<>();
if (root == null) return result;
Stack<TreeNode> toVisit = new Stack<>();
toVisit.push(root);
TreeNode cur;
while (!toVisit.isEmpty()) {
cur = toVisit.pop();
result.add(cur.val); // 访问根节点
if (cur.right != null) toVisit.push(cur.right); // 右节点入栈
if (cur.left != null) toVisit.push(cur.left); // 左节点入栈
}
return result;
}
/**
* 中序遍历:递归法
*
* 对于中序遍历,就是先访问左子树,再访问根节点,再访问右子树,即 左->根->右
*/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
inorderHelper(root, result);
return result;
}
private void inorderHelper(TreeNode root, List<Integer> result) {
if(root == null) return;
inorderHelper(root.left, result); // 递归遍历左子树
result.add(root.val); // 访问根节点
inorderHelper(root.right, result); // 递归遍历右子树
}
/**
* 中序遍历:迭代法
*
* 因为最先遇到的根节点不是最先访问的,我们需要先访问左子树,再回退到根节点,再访问根节点的右子树,
* 这里的一个难点是从左子树回退到根节点的操作,虽然可以用栈来实现回退,但是要注意在出栈时保存根节点的引用,
* 因为我们还需要通过根节点来访问右子树
*
* @param root
* @return
*/
public List<Integer> inorderTraversal2(TreeNode root) {
List<Integer> result = new LinkedList<>();
Stack<TreeNode> toVisit = new Stack<>();
TreeNode cur = root;
while (cur != null || !toVisit.isEmpty()) {
while (cur != null) {
toVisit.push(cur); // 添加根节点
cur = cur.left; // 循环添加左节点
}
cur = toVisit.pop(); // 当前栈顶已经是最底层的左节点了,取出栈顶元素,访问该节点
result.add(cur.val);
cur = cur.right; // 添加右节点
}
return result;
}
/**
* 后序遍历:递归法
*
* 对于后序遍历,就是先访问左子树,再访问右子树,再访问根节点,即 左->右->根
*/
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
postorderHelper(root, result);
return result;
}
private void postorderHelper(TreeNode root, List<Integer> result) {
if (root == null) return;
postorderHelper(root.left, result); // 遍历左子树
postorderHelper(root.right, result); // 遍历右子树
result.add(root.val); // 访问根节点
}
/**
* 后序遍历:迭代法
*
* 后序遍历在访问完左子树向上回退到根节点的时候不是立马访问根节点的,
* 而是得先去访问右子树,访问完右子树后在回退到根节点
*/
public List<Integer> postorderTraversal2(TreeNode root) {
List<Integer> result = new LinkedList<>();
Stack<TreeNode> toVisit = new Stack<>();
TreeNode cur = root;
TreeNode pre = null;
while (cur != null || !toVisit.isEmpty()) {
while (cur != null) {
toVisit.push(cur); // 添加根节点
cur = cur.left; // 递归添加左节点
}
cur = toVisit.peek(); // 已经访问到最左的节点了
//在不存在右节点或者右节点已经访问过的情况下,访问根节点
if (cur.right == null || cur.right == pre) {
toVisit.pop();
result.add(cur.val);
pre = cur;
cur = null;
} else {
cur = cur.right; // 右节点还没有访问过就先访问右节点
}
}
return result;
}
/**
* 广度优先遍历
*
* 广度优先遍历各个节点,需要使用到队列(Queue)这种数据结构,queue的特点是先进先出
*/
public ArrayList<Integer> wide(TreeNode root) {
ArrayList<Integer> lists=new ArrayList<Integer>();
if(root==null)
return lists;
Queue<TreeNode> queue=new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode node = queue.poll();
if(node.left!=null){
queue.offer(node.left);
}
if(node.right!=null){
queue.offer(node.right);
}
lists.add(node.val);
}
return lists;
}
}
1、深度优先遍历(Depth-First-Search)常用的数据结构为栈,广度优先遍历(Breadth-First-Search)常用的数据结构为队列
2、深度优先遍历的思想是从上至下,对每一个分支一直往下一层遍历直到这个分支结束,然后返回上一层,对上一层的右子树这个分支继续深搜,直到一整棵树完全遍历,因此深搜的步骤符合栈后进先出的特点
广度优先遍历的思想是从左至右,对树的每一层所有结点依次遍历,当一层的结点遍历完全后,对下一层开始遍历,而下一层结点又恰好是上一层的子结点。因此广搜的步骤符合队列先进先出的思想
3、深度优先遍历:
对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次。对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次。
要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为前序遍历、中序遍历、后序遍历。
前序遍历:对任一子树,先访问根,然后遍历其左子树,最后遍历其右子树,前序就是根节点在最前:根->左->右。
中序遍历:对任一子树,先遍历其左子树,然后访问根,最后遍历其右子树,中序是根节点在中间:左->根->右。
后序遍历:对任一子树,先遍历其左子树,然后遍历其右子树,最后访问根,后序是根节点在最后:左->右->根。
除了利用栈以外,深度优先搜索也可以使用递归的方法。
4、广度优先遍历:
又叫层次遍历,从上往下对每一层依次访问,在每一层中,从左往右(也可以从右往左)访问结点,访问完一层就进入下一层,直到没有结点可以访问为止。又叫层次遍历,从上往下对每一层依次访问,在每一层中,从左往右(也可以从右往左)访问结点,访问完一层就进入下一层,直到没有结点可以访问为止。
5、深度优先搜索算法:不全部保留结点,占用空间少;有回溯操作(即有入栈、出栈操作),运行速度慢。
通常深度优先搜索法不全部保留结点,扩展完的结点从数据库中弹出删去,这样,一般在数据库中存储的结点数就是深度值,因此它占用空间较少。所以,当搜索树的结点较多,用其它方法易产生内存溢出时,深度优先搜索不失为一种有效的求解方法。
广度优先搜索算法:保留全部结点,占用空间大; 无回溯操作(即无入栈、出栈操作),运行速度快。
广度优先搜索算法,一般需存储产生的所有结点,占用的存储空间要比深度优先搜索大得多,因此,程序设计中,必须考虑溢出和节省内存空间的问题。但广度优先搜索法一般无回溯操作,即入栈和出栈的操作,所以运行速度比深度优先搜索要快些。
代码:
public class TreeTravel {
/**
* 前序遍历:递归法
*
* 递归的方法很容易实现,也很容易理解:我们先访问根节点,然后递归访问左子树,再递归访问右子树,即实现了根->左->右的访问顺序,
* 因为使用的是递归方法,所以每一个子树都实现了这样的顺序。
* @param root
* @return
*/
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
preorderHelper(root, result);
return result;
}
private void preorderHelper(TreeNode root, List<Integer> result) {
if (root == null) return;
result.add(root.val); // 访问根节点
preorderHelper(root.left, result); // 递归遍历左子树
preorderHelper(root.right, result); //递归遍历右子树
}
/**
* 前序遍历:迭代法
*
* 在迭代法中,我们使用栈来实现。由于出栈顺序和入栈顺序相反,所以每次添加节点的时候先添加右节点,再添加左节点。
* 这样在下一轮访问子树的时候,就会先访问左子树,再访问右子树:
*/
public List<Integer> preorderTraversal2(TreeNode root) {
List<Integer> result = new LinkedList<>();
if (root == null) return result;
Stack<TreeNode> toVisit = new Stack<>();
toVisit.push(root);
TreeNode cur;
while (!toVisit.isEmpty()) {
cur = toVisit.pop();
result.add(cur.val); // 访问根节点
if (cur.right != null) toVisit.push(cur.right); // 右节点入栈
if (cur.left != null) toVisit.push(cur.left); // 左节点入栈
}
return result;
}
/**
* 中序遍历:递归法
*
* 对于中序遍历,就是先访问左子树,再访问根节点,再访问右子树,即 左->根->右
*/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
inorderHelper(root, result);
return result;
}
private void inorderHelper(TreeNode root, List<Integer> result) {
if(root == null) return;
inorderHelper(root.left, result); // 递归遍历左子树
result.add(root.val); // 访问根节点
inorderHelper(root.right, result); // 递归遍历右子树
}
/**
* 中序遍历:迭代法
*
* 因为最先遇到的根节点不是最先访问的,我们需要先访问左子树,再回退到根节点,再访问根节点的右子树,
* 这里的一个难点是从左子树回退到根节点的操作,虽然可以用栈来实现回退,但是要注意在出栈时保存根节点的引用,
* 因为我们还需要通过根节点来访问右子树
*
* @param root
* @return
*/
public List<Integer> inorderTraversal2(TreeNode root) {
List<Integer> result = new LinkedList<>();
Stack<TreeNode> toVisit = new Stack<>();
TreeNode cur = root;
while (cur != null || !toVisit.isEmpty()) {
while (cur != null) {
toVisit.push(cur); // 添加根节点
cur = cur.left; // 循环添加左节点
}
cur = toVisit.pop(); // 当前栈顶已经是最底层的左节点了,取出栈顶元素,访问该节点
result.add(cur.val);
cur = cur.right; // 添加右节点
}
return result;
}
/**
* 后序遍历:递归法
*
* 对于后序遍历,就是先访问左子树,再访问右子树,再访问根节点,即 左->右->根
*/
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
postorderHelper(root, result);
return result;
}
private void postorderHelper(TreeNode root, List<Integer> result) {
if (root == null) return;
postorderHelper(root.left, result); // 遍历左子树
postorderHelper(root.right, result); // 遍历右子树
result.add(root.val); // 访问根节点
}
/**
* 后序遍历:迭代法
*
* 后序遍历在访问完左子树向上回退到根节点的时候不是立马访问根节点的,
* 而是得先去访问右子树,访问完右子树后在回退到根节点
*/
public List<Integer> postorderTraversal2(TreeNode root) {
List<Integer> result = new LinkedList<>();
Stack<TreeNode> toVisit = new Stack<>();
TreeNode cur = root;
TreeNode pre = null;
while (cur != null || !toVisit.isEmpty()) {
while (cur != null) {
toVisit.push(cur); // 添加根节点
cur = cur.left; // 递归添加左节点
}
cur = toVisit.peek(); // 已经访问到最左的节点了
//在不存在右节点或者右节点已经访问过的情况下,访问根节点
if (cur.right == null || cur.right == pre) {
toVisit.pop();
result.add(cur.val);
pre = cur;
cur = null;
} else {
cur = cur.right; // 右节点还没有访问过就先访问右节点
}
}
return result;
}
/**
* 广度优先遍历
*
* 广度优先遍历各个节点,需要使用到队列(Queue)这种数据结构,queue的特点是先进先出
*/
public ArrayList<Integer> wide(TreeNode root) {
ArrayList<Integer> lists=new ArrayList<Integer>();
if(root==null)
return lists;
Queue<TreeNode> queue=new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode node = queue.poll();
if(node.left!=null){
queue.offer(node.left);
}
if(node.right!=null){
queue.offer(node.right);
}
lists.add(node.val);
}
return lists;
}
}
发表评论
-
java 类的加载 以及 ClassLoader
2020-04-16 09:43 340Class Loader 类加载器: 类加载器负责加载 ... -
Stack 的实现原理深入剖析
2020-04-06 13:26 428Stack 介绍: Stack是栈。 ... -
Vector 的实现原理深入剖析
2020-04-06 13:17 321Vector介绍: Vector 是矢量队列,它是JDK1. ... -
JDK 分析工具
2020-04-05 17:30 293常用分析工具: jps:显示指定系统中所有的HotSpot虚 ... -
Hashtable 的实现原理深入剖析
2020-02-18 20:59 424一、Hashtable的基本方法: 1、定义: HashT ... -
jdk 1.8 新特性
2020-02-17 13:43 2851、default关键字 ... -
Java IO 架构
2019-11-11 16:39 305主要两类: 磁盘I/O 网络I/O 基于字节 ... -
Java 数据结构与算法
2019-04-03 10:25 453程序=数据结构+算法 ... -
Java语言异常(Exception)
2018-10-09 11:40 498异常,是Java中非常常用 ... -
Java并发问题--乐观锁与悲观锁以及乐观锁的一种实现方式-CAS
2018-08-17 09:47 1426首先介绍一些乐观锁与 ... -
Java 高性能编程注意事项
2016-11-17 09:55 6071. 尽量在合适的场合使用单例 使用单例可以减轻加载的负担, ... -
Netty 解析
2017-03-07 13:47 1175Linux网络IO模型: Linux ... -
2016年Java 面试题总结
2016-01-18 13:34 54721多线程、并发及线程的基础问题: 1)Java 中能创建 vo ... -
java 内存模型
2015-12-29 13:44 773JAVA内存模型: Java内存 ... -
JVM 深入剖析
2015-12-29 12:51 1022JVM是JAVA虚拟机(JAVA Virtual Machin ... -
Java 并发编程_Synchronized
2015-12-16 12:42 824硬件的效率和一致性: 由于计算机的运算速度和它的存储和通讯子 ... -
Java 并发编程_Volatile
2015-12-15 13:42 586术语定义: 共享变量:在多个线程之间能够被共享的变量被称为共 ... -
Java 并发编程_ConcurrentLinkedQueue
2015-12-15 13:32 863ConcurrentLinkedQueue 的分析和使用: ... -
Java 并发编程_ConcurrentHashMap
2015-11-10 11:30 792ConcurrentHashMap 的分析和 ... -
JVM 垃圾回收原理
2015-10-29 13:38 454基本回收算法: 1.引用 ...
相关推荐
二叉树广度和深度优先遍历,通过递归算法实现二叉树的建立,利用递归算法实现深度优先遍历,使用队列实现广度优先遍历
实现二叉树的深度遍历广度遍历等关于二叉树的基本操作
主要介绍了Java实现二叉树的深度优先遍历和广度优先遍历算法,结合实例形式详细分析了二叉树的定义、深度优先遍历与广度优先遍历算法原理与相关操作实现技巧,需要的朋友可以参考下
二叉树的深度优先搜索与广度优先搜索的非递归方法实现
NULL 博文链接:https://redhacker.iteye.com/blog/413606
js代码-二叉树广度优先遍历
二叉树的先序,中序,后序递归,非递归遍历和广度优先遍历。此程序是用C语言写的。
主要介绍了PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次),结合实例形式详细分析了php针对二叉树的深度优先遍历与广度优先遍历相关操作技巧与注意事项,需要的朋友可以参考下
深度优先遍历的实现; 广度优先遍历的实现;
二叉树深度优先遍历、广度优先遍历{非递归}
本文实例讲述了python实现树的深度优先遍历与广度优先遍历。分享给大家供大家参考,具体如下: 广度优先(层次遍历) 从树的root开始,从上到下从左到右遍历整个树的节点 数和二叉树的区别就是,二叉树只有左右两个...
二叉树遍历广度优先
算法-二叉树的深度优先和广度优先遍历(包含源程序).rar
本文实例讲述了python实现树的深度优先遍历与广度优先遍历。分享给大家供大家参考,具体如下: 广度优先(层次遍历) 从树的root开始,从上到下从左到右遍历整个树的节点 数和二叉树的区别就是,二叉树只有左右两个...
本文实例讲述了PHP实现二叉树的深度优先与广度优先遍历方法。分享给大家供大家参考。具体如下: #二叉树的广度优先遍历 #使用一个队列实现 class Node { public $data = null; public $left = null; public $...
深度优先遍历和广度优先遍历三、面试题+励志 这不就是二叉树吗?嗯,风景都在提示我该学学二叉树了 一、什么是深度优先遍历 深度优先遍历算法是经典的图论算法。从某个节点v出发开始进行搜索。不断搜索直到该节点...
实现由先序、中序序列构造二叉树,由后序、中序序列构造二叉树,广度优先遍历以root为根结点的子树,中序遍历(递归,非递归)以root为根结点的子树
从顶点1出发,对它进行深度优先遍历得到的序列是( ① ),而进行广度优先遍历得到的顶点序列是( ② )。【中科院软件所 1999 六、2-(1)(2分)】 ①.A.1354267 B.1347652 C.1534276 D.1247653 E.以上答案均...