在此可输入您对该资料的评论~
(window.slotbydup=window.slotbydup || []).push({
id: '4540180',
container: s,
size: '250,200',
display: 'inlay-fix'
资料评价：
所需积分：1JAVA获取某段时间内的所有日期
package Datess.//生成一年的日期;
import java.text.SimpleDateF
import java.util.ArrayL
import java.util.C
import java.util.D
import java.util.L
public class OneYearDate {
public static void main(String[] args) throws Exception {
// TODO Auto-generated method stub
Calendar cal = Calendar.getInstance();
String start = &&;
String end = &&;
SimpleDateFormat sdf = new SimpleDateFormat(&yyyyMMdd&);
Date dBegin = sdf.parse(start);
Date dEnd = sdf.parse(end);
List & Date & lDate = findDates(dBegin, dEnd);
for (Date date: lDate) {
System.out.println(sdf.format(date));
System.out.println(&lDate大小：& + lDate.size());
//JAVA获取某段时间内的所有日期
public static List & Date & findDates(Date dBegin, Date dEnd) {
List lDate = new ArrayList();
lDate.add(dBegin);
Calendar calBegin = Calendar.getInstance();
// 使用给定的 Date 设置此 Calendar 的时间
calBegin.setTime(dBegin);
Calendar calEnd = Calendar.getInstance();
// 使用给定的 Date 设置此 Calendar 的时间
calEnd.setTime(dEnd);
// 测试此日期是否在指定日期之后
while (dEnd.after(calBegin.getTime())) {
// 根据日历的规则，为给定的日历字段添加或减去指定的时间量
calBegin.add(Calendar.DAY_OF_MONTH, 1);
lDate.add(calBegin.getTime());如何在有限的时间内获取更多的干货？
如何在有限的时间内获取更多的干货？
既然| 如此 | 选择文、秉一桌上的书已经积了灰，新的书还在不断的填充中...拼命刷着热门话题，生怕自己错过任何一个热点...在信息如此之多、内容如此“疯狂”的时代，你的心是不是越来越浮躁，越来越觉得缺点什么？信息爆炸的时代，我们有太多获取知识，信息的渠道和平台，但我们却忽视了理解性的阅读，往往比前者更重要。面对信息爆炸的时代，个人如何自处。如何用好信息。但又不被信息淹没呢？一、适当减少关注量，取消一些你已经许久没看的订阅号吧，好好清理一下你浏览器的收藏夹吧，真正回到原点，即为了目的而去关注。你需要获取什么信息？你再去通过各种途径寻找信息。改变自己的心态，并非信息浏览过了里面的知识就变成了自己的，要有一个消化思考的过程后才算是真正的将过去花在这个信息上的时间的价值体现出来。因此，面对信息自己首先不要贪婪。二、着重培养分析能力，思考逻辑，合理提取有效信息，建立知识树，理性分析一下，哪一块是自己真正需要并要花大把时间来进行的，哪些占用时间多但却不是很重要，如此按照价值/时间来计算，严格把这个数值高的安排大部分时间，然后严格执行。三、总结和输出。信息有如大海，知识就是淡水。我们如何从信息中提取知识。定期的对已有的，记录下的或者收藏下的信息进行总结和输出。总结输出的一个原因是为了让信息变成你脑中的知识，并能够不假思索的用出来。NO我们的日常时间有限，获取知识信息时间更是没有多少，懂得如何处理获取有价值的信息，会让我们的生活过的更好，离我们的梦想更近一步。关注&秉一”关注成长，不负青春。
本文仅代表作者观点，不代表百度立场。系作者授权百家号发表，未经许可不得转载。
百家号 最近更新：
简介: 专注于小企业对B2B信息发布技巧总结
作者最新文章二叉树的三种遍历方式（递归、非递归和Morris遍历）_Linux编程_Linux公社-Linux系统门户网站
你好，游客
二叉树的三种遍历方式（递归、非递归和Morris遍历）
二叉树遍历是二叉树的最基本的操作，其实现方式主要有三种：
非递归遍历
Morris遍历
递归遍历的实现非常容易，非递归实现需要用到栈。而Morris算法可能很多人都不太熟悉，其强大之处在于只需要使用O(1)的空间就能实现对二叉树O(n)时间的遍历。
二叉树结点的定义
每个二叉树结点包括一个值以及左孩子和右孩子结点，其定义如下：
class TreeNode {
TreeNode *left, *right;
TreeNode(int val) {
this-&val = val;
this-&left = this-&right = NULL;
二叉树的遍历
二叉树的遍历，就是按照某条搜索路径访问树中的每一个结点，使得每个结点均被访问一次，而且仅被访问一次。常见的遍历次序有：
先序遍历：先访问根结点，再访问左子树，最后访问右子树
中序遍历：先访问左子树，再访问根结点，最后访问右子树
后序遍历：先访问左子树，再访问右子树，最后访问根结点
下面介绍，二叉树3种遍历方式的实现。
递归实现非常简单，按照遍历的次序，对当前结点分别调用左子树和右子树即可。
void preOrder(TreeNode *root) {
if(root == NULL)
cout && root-&val && endl;
preOrder(root-&left);
preOrder(root-&right);
void inOrder(TreeNode *root) {
if(root == NULL)
inOrder(root-&left);
cout && root-&val && endl;
inOrder(root-&right);
void postOrder(TreeNode *root) {
if(root == NULL)
postOrder(root-&left);
postOrder(root-&right);
cout && root-&val && endl;
复杂度分析
二叉树遍历的递归实现，每个结点只需遍历一次，故时间复杂度为O(n)。而使用了递归，最差情况下递归调用的深度为O(n)，所以空间复杂度为O(n)。
非递归遍历
二叉树遍历的非递归实现，可以借助栈。
将根结点入栈；
每次从栈顶弹出一个结点，访问该结点；
把当前结点的右孩子入栈；
把当前结点的左孩子入栈。
按照以上顺序入栈，这样出栈顺序就与先序遍历一样：先根结点，再左子树，最后右子树。
void preOrder2(TreeNode *root) {
if(root == NULL)
stack&TreeNode *& stk;
stk.push(root);
while(!stk.empty()) {
TreeNode *pNode = stk.top();
stk.pop();
cout && pNode-&val && endl;
if(pNode-&right != NULL)
stk.push(pNode-&right);
if(pNode-&left != NULL)
stk.push(pNode-&left);
初始化一个二叉树结点pNode指向根结点；
若pNode非空，那么就把pNode入栈，并把pNode变为其左孩子；（直到最左边的结点）
若pNode为空，弹出栈顶的结点，并访问该结点，将pNode指向其右孩子（访问最左边的结点，并遍历其右子树）
void inOrder2(TreeNode *root) {
if(root == NULL)
stack&TreeNode *& stk;
TreeNode *pNode = root;
while(pNode != NULL || !stk.empty()) {
if(pNode != NULL) {
stk.push(pNode);
pNode = pNode-&left;
pNode = stk.top();
stk.pop();
cout && pNode-&val && endl;
pNode = pNode-&right;
设置两个栈stk, stk2；
将根结点压入第一个栈stk；
弹出stk栈顶的结点，并把该结点压入第二个栈stk2；
将当前结点的左孩子和右孩子先后分别入栈stk；
当所有元素都压入stk2后，依次弹出stk2的栈顶结点，并访问之。
第一个栈的入栈顺序是：根结点，左孩子和右孩子；于是，压入第二个栈的顺序是：根结点，右孩子和左孩子。因此，弹出的顺序就是：左孩子，右孩子和根结点。
void postOrder2(TreeNode *root) {
if(root == NULL)
stack&TreeNode *& stk, stk2;
stk.push(root);
while(!stk.empty()) {
TreeNode *pNode = stk.top();
stk.pop();
stk2.push(pNode);
if(pNode-&left != NULL)
stk.push(pNode-&left);
if(pNode-&right != NULL)
stk.push(pNode-&right);
while(!stk2.empty()) {
cout && stk2.top()-&val && endl;
stk2.pop();
另外，二叉树的后序遍历的非递归实现，也可以只使用一个栈来实现。
void postOrder2(TreeNode *root) {
if(root == NULL)
stack&TreeNode *& stk;
stk.push(root);
TreeNode *prev = NULL;
while(!stk.empty()) {
TreeNode *pNode = stk.top();
if(!prev || prev-&left == pNode || prev-&right == pNode) {
// traverse down
if(pNode-&left)
stk.push(pNode-&left);
else if(pNode-&right)
stk.push(pNode-&right);
cout && pNode-&val &&
stk.pop();
else if(pNode-&left == prev) {
// traverse up from left
if(pNode-&right)
stk.push(pNode-&right);
/* else if(pNode-&right == prev) { // traverse up from right
cout && pNode-&val &&
stk.pop();
cout && pNode-&val && endl;
stk.pop();
prev = pNode;
复杂度分析
二叉树遍历的非递归实现，每个结点只需遍历一次，故时间复杂度为O(n)。而使用了栈，空间复杂度为二叉树的高度，故空间复杂度为O(n)。
Morris遍历
Morris遍历算法最神奇的地方就是，只需要常数的空间即可在O(n)时间内完成二叉树的遍历。O(1)空间进行遍历困难之处在于在遍历的子结点的时候如何重新返回其父节点？在Morris遍历算法中，通过修改叶子结点的左右空指针来指向其前驱或者后继结点来实现的。
如果当前结点pNode的左孩子为空，那么输出该结点，并把该结点的右孩子作为当前结点；
如果当前结点pNode的左孩子非空，那么就找出该结点在中序遍历中的前驱结点pPre
当第一次访问该前驱结点pPre时，其右孩子必定为空，那么就将其右孩子设置为当前结点，以便根据这个指针返回到当前结点pNode中，并将当前结点pNode设置为其左孩子；
当该前驱结点pPre的右孩子为当前结点，那么就输出当前结点，并把前驱结点的右孩子设置为空（恢复树的结构），将当前结点更新为当前结点的右孩子
重复以上两步，直到当前结点为空。
void inOrder3(TreeNode *root) {
if(root == NULL)
TreeNode *pNode = root;
while(pNode != NULL) {
if(pNode-&left == NULL) {
cout && pNode-&val && endl;
pNode = pNode-&right;
TreeNode *pPre = pNode-&left;
while(pPre-&right != NULL && pPre-&right != pNode) {
pPre = pPre-&right;
if(pPre-&right == NULL) {
pPre-&right = pNode;
pNode = pNode-&left;
pPre-&right = NULL;
cout && pNode-&val && endl;
pNode = pNode-&right;
因为只使用了两个辅助指针，所以空间复杂度为O(1)。对于时间复杂度，每次遍历都需要找到其前驱的结点，而寻找前驱结点与树的高度相关，那么直觉上总的时间复杂度为O(nlogn)。其实，并不是每个结点都需要寻找其前驱结点，只有左子树非空的结点才需要寻找其前驱，所有结点寻找前驱走过的路的总和至多为一棵树的结点个数。因此，整个过程每条边最多走两次，一次使定位到该结点，另一次是寻找某个结点的前驱，所以时间复杂度为O(n)。
如以下一棵二叉树。首先，访问的是根结点F，其左孩子非空，所以需要先找到它的前驱结点（寻找路径为B-&D-&E），将E的右指针指向F，然后当前结点为B。依然需要找到B的前驱结点A，将A的右指针指向B，并将当前结点设置为A。下一步，输出A，并把当前结点设置为A的右孩子B。之后，会访问到B的前驱结点A指向B，那么令A的右指针为空，继续遍历B的右孩子。依次类推。
与中序遍历类似，区别仅仅是输出的顺序不同。
void preOrder3(TreeNode *root) {
if(root == NULL)
TreeNode *pNode = root;
while(pNode) {
if(pNode-&left == NULL) {
cout && pNode-&val && endl;
pNode = pNode-&right;
TreeNode *pPre = pNode-&left;
while(pPre-&right != NULL && pPre-&right != pNode)
pPre = pPre-&right;
if(pPre-&right == NULL) {
pPre-&right = pNode;
cout && pNode-&val && endl;
pNode = pNode-&left;
pPre-&right = NULL;
pNode = pNode-&right;
先建立一个临时结点dummy，并令其左孩子为根结点root，将当前结点设置为dummy；
如果当前结点的左孩子为空，则将其右孩子作为当前结点；
如果当前结点的左孩子不为空，则找到其在中序遍历中的前驱结点
如果前驱结点的右孩子为空，将它的右孩子设置为当前结点，将当前结点更新为当前结点的左孩子；
如果前驱结点的右孩子为当前结点，倒序输出从当前结点的左孩子到该前驱结点这条路径上所有的结点。将前驱结点的右孩子设置为空，将当前结点更新为当前结点的右孩子。
重复以上过程，直到当前结点为空。
void reverse(TreeNode *p1, TreeNode *p2) {
if(p1 == p2)
TreeNode *x = p1;
TreeNode *y = p1-&right;
while(true) {
TreeNode *temp = y-&right;
y-&right = x;
if(x == p2)
void printReverse(TreeNode *p1, TreeNode *p2) {
reverse(p1, p2);
TreeNode *pNode = p2;
while(true) {
cout && pNode-&val && endl;
if(pNode == p1)
pNode = pNode-&right;
reverse(p2, p1);
void postOrder3(TreeNode *root) {
if(root == NULL)
TreeNode *dummy = new TreeNode(-1);
dummy-&left = root;
TreeNode *pNode = dummy;
while(pNode != NULL) {
if(pNode-&left == NULL)
pNode = pNode-&right;
TreeNode *pPrev = pNode-&left;
while(pPrev-&right != NULL && pPrev-&right != pNode)
pPrev = pPrev-&right;
if(pPrev-&right == NULL) {
pPrev-&right = pNode;
pNode = pNode-&left;
printReverse(pNode-&left, pPrev);
pPrev-&right = NULL;
pNode = pNode-&right;
本文永久更新链接地址：
相关资讯 & & &
& (05月22日)
& (02月27日)
& (07月30日)
& (05月14日)
& (01月28日)
　　　同意评论声明
　　　发表
尊重网上道德，遵守中华人民共和国的各项有关法律法规
承担一切因您的行为而直接或间接导致的民事或刑事法律责任
本站管理人员有权保留或删除其管辖留言中的任意内容
本站有权在网站内转载或引用您的评论
参与本评论即表明您已经阅读并接受上述条款