描述树

有这么一个二叉树

上面图片由graphviz生成，描绘该树的.dot文件内容如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

digraph G {
    node [shape = record ,height=.1];
    node0[label = "<f0> |<f1> A|<f2> "];
    node1[label = "<f0> |<f1> B|<f2> "];
    node2[label = "<f0> |<f1> C|<f2> "];
    node3[label = "<f0> |<f1> D|<f2> "];
    node4[label = "<f0> |<f1> E|<f2> "];
    node5[label = "<f0> |<f1> F|<f2> "];
    node6[label = "<f0> |<f1> G|<f2> "];
    node7[label = "<f0> |<f1> H|<f2> "];
    node8[label = "<f0> |<f1> I|<f2> "];
    "node0":f0 -> "node1":f1;
    "node0":f2 -> "node2":f1;
    "node1":f2 -> "node3":f1;
    "node2":f0 -> "node4":f1;
    "node2":f2 -> "node5":f1;
    "node4":f0 -> "node6":f1;
    "node5":f0 -> "node7":f1;
    "node5":f2 -> "node8":f1;
}

生成树图：dot -Tgif btree.dot -o btree.gif

该树用Python描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class TreeNode(object):
    def __init__(self,data,left=None,right=None):
        self.data = data
        self.left = left
        self.right = right

    def __str__(self):
        return str(self.data)

def create_btree():
    A,B,C,D,E,F,G,H,I = [TreeNode(x) for x in 'ABCDEFGHI']
    A.left  = B
    A.right = C
    B.right = D
    C.left  = E
    C.right = F
    E.left  = G
    F.left  = H
    F.right = I
    return A

类TreeNode用来描述二叉树结构。create_btree函数用来生成上图描述的树，并返回根节点。

深度优先搜索

递归遍历二叉树

前序遍历

1
2
3
4
5
6
7

# Depth-first Search
def preorder(node):
    if node is None:
        return
    print(node.data)
    preorder(node.left)
    preorder(node.right)

中序遍历

1
2
3
4
5
6

def inorder(node):
    if node is None:
        return
    inorder(node.left)
    print(node.data)
    inorder(node.right)

后序遍历

1
2
3
4
5
6

def postorder(node):
    if node is None:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.data)

迭代遍历二叉树

前序遍历

1
2
3
4
5
6
7
8
9
10
11
12

def preorder_iter(root):
    s = []
    node = root
    while True:
        while node:
            print(node)
            s.append(node)
            node = node.left

        if not s:
            break
        node = s.pop().right

广度优先搜索

层序遍历

用队列实现，子节点插后面，子节点的子节点也插在队列后面，从队列左边访问，永远都是层数高的在前面，实现层序遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# Breadth-first Search
from collections import deque

def level_order(node):
    s = deque()
    while True:
        print(node)
        if node.left:
            s.append(node.left)
        if node.right:
            s.append(node.right)
        if not s:
            break
        node = s.popleft()

运行、结果

1
2
3
4
5
6
7
8
9
10
11
12
13

if __name__ == '__main__':
    root = create_btree()
    print('preorder:')
    preorder(root)
    print('inorder:')
    inorder(root)
    print('postorder:')
    postorder(root)
    print('preorder_iter')
    preorder_iter(root)
    print('level_order')
    level_order(root)

结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

preorder:
A
B
D
C
E
G
F
H
I
inorder:
B
D
A
G
E
C
H
F
I
postorder:
D
B
G
E
H
I
F
C
A
preorder_iter
A
B
D
C
E
G
F
H
I
level_order
A
B
C
D
E
F
G
H
I

参考资料

Tree Traversal
Binay Tree

来自 AT&T 实验室。

有时候需要做一些图，比如流程图，数据结构图之类的。自己画吧，不工整，排版又头疼。最后发现了一款这玩意。

一些用这个工具做的效果在这里

http://www.graphviz.org/Gallery.php

参考资料

下载地址
帮助文档
CSDN一些应用示例
dotguide
Python生成Btree

环境： Python 3.5

列表解析和生成器

假设要生成一个1到10000的列表a，供其它功能去遍历它的话。

用Python列表解析的话，如下：

1

a = [ x for x in range(1,10000)]

但是有这么一个情况。我每次也不是非要遍历完这个列表，而且某些情况我可能根本不会用到这个列表。

但是一开始就定义好这个列表。它是会即时生成这个列表。如果这个表很大，毫无疑问比较浪费时间，和占用内存。

应对上述的问题，可以用生成器来解决。

1

a = ( x for x in range(1,10000))

语法上和列表解析的差别主要就是一个是用[],一个是用()

同样，可以用for去遍历它

1
2
3

for n in a:
    print(n)

另外可以通过next属性去访问它的值。

1
2
3
4
5
6
7
8
9
10

# python 2.x  属性是 next()
# python 3.x  属性是 __next()
# 所以建议用next()获取 比较通用点。
whlie True:
    try:
        n = next(a)
        print('n:', n)
    except StopIteration as e:
        print('Generator return value:', e.value)
        break

Generator function

现在知道了( x for x in range(1,10000))这种生成器形式。但是我想要生成更复杂点的数据怎么办？

比如斐波那契数列。这个时候就用到yield了，通过yield去生成生成器的数据。简单点理解，它就是普通函数的return，只不过yield是专门将数据返回给生成器。

1
2
3
4
5
6

# 生成10位fabnacci数列
def fab():
    a,b=1,1
    for i in range(1,10):
        yield a
        a,b=b,a+b

console查看类型如下：

1
2
3
4
5

In [2]: fabnacci = fab()

In [3]: type(fabnacci)
Out[3]: generator

打印数据：

1
2
3
4
5
6
7
8
9
10
11
12

In [6]: for i in fabnacci:
        print(i)   
1
1
2
3
5
8
13
21
34

生产者消费者模型 协程

关于对生成器的应用，一个很好的例子是实现生产者消费者模型

执行由串行变成并行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def consumer(name):
    print("I'm crazy {name},I'm ready to kill some mother fucker.".format(name=name))
    while True:
        fucker = yield
        print('{name}:{fucker} guys has been killed.'.format(name=name,fucker=fucker))

def producer():
    tom = consumer('Tom')
    bob = consumer('Bob')
    next(tom)
    next(bob)
    for i in range(1,10):
        tom.send(i)
        bob.send(i)

producer()

Out:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

I'm crazy Tom,I'm ready to kill some mother fucker.
I'm crazy Bob,I'm ready to kill some mother fucker.
Tom:1 guys has been killed.
Bob:1 guys has been killed.
Tom:2 guys has been killed.
Bob:2 guys has been killed.
Tom:3 guys has been killed.
Bob:3 guys has been killed.
Tom:4 guys has been killed.
Bob:4 guys has been killed.
Tom:5 guys has been killed.
Bob:5 guys has been killed.
Tom:6 guys has been killed.
Bob:6 guys has been killed.
Tom:7 guys has been killed.
Bob:7 guys has been killed.
Tom:8 guys has been killed.
Bob:8 guys has been killed.
Tom:9 guys has been killed.
Bob:9 guys has been killed.

可迭代对象和迭代器

• 可以迭代的主要分两种，一个是可迭代对象（Iterable）的和迭代器（Iterator）。

• 迭代器一定是可迭代对象，可迭代对象不一定是迭代器。

• 可迭代对象都可以用for x in xx:语句来遍历对象。

• 而迭代器还可以用next()函数逐个访问下一个值。遍历结束会遇到StopIteration异常。

• 可以看做迭代器是可迭代对象一个更高级的实现。

如何判断

1. 可以用isinstance函数来查看。

记得先导入Iterable，Iterator。

1
2

from collections import Iterable
from collections import Iterator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

In [19]: fabnacci = fab()

In [20]: a = [ x for x in range(1,10000)]

In [21]: isinstance(fabnacci,Iterable)
Out[21]: True

In [22]: isinstance(fabnacci,Iterator)
Out[22]: True

In [23]: isinstance(a,Iterable)
Out[23]: True

In [24]: isinstance(a,Iterator)
Out[24]: False

2. 可以用dir函数查看是否有next的方法

如果存在就是迭代器。

如何转换

用iter()函数。可以将iterable的数据变为iterator。

之前的话，一直在阿里云申请免费的赛门铁克的SSL证书。但是如果站点多，又有不同客户的话，全放一个地方其实也不太合适，另外申请时间也稍微慢点，要等个好几分钟，有时候半个小时。管理起来比较麻烦。

所以再三考虑，使用了let’s encrypted这货也是免费的。更加极客点，相对来讲，权威性没赛门铁克那么高，不过都得到大部分浏览器厂商的认可，所以还是能用的。

由于开放了申请接口，所以部分工具或者网站源码集成了申请证书的功能。我知道的有 cPanel，宝塔，WordPress之类的。

let’s encrypted 证书有效期只有60天，还是蛮短的。不过好在它提供了很多好用的脚本或者程序来提供我们续签，整体来说还是比较方便的。

ACME是它一个提供用来辅助申请的脚本，大大简化了申请流程，有些做到可视化，还算是比较方便的。涵盖了各种语言。

ACME客户端列表

我的话用 ACME.sh

测试SSL强度

nginx如果有配置限制了 .* 目录的访问的话，要修改确保 web目录下 .well-known 目录下的内容可访问。

昨天有开发叫把部署时候，替换配置文件原本用cp换成ln。说是为了修改配置方便。

但是如果一个目录有很多个配置，含子目录，用ln -r是不行的。逐个ln很是麻烦。

不过，开发说啥就是啥。。。

但是今天一些URL访问出现异常。

大致错误如下。

1

PHP message: PHP Fatal error:  require(): Failed opening required '/wwwroot/resources_do_not_delete/xxxx/frontend/web/../../common/config/bootstrap.php' (include_path='.:/app/php56/lib/php') in /wwwroot/resources_do_not_delete/xxxx/frontend/web/index.php on line 7" while reading response header from upstream, client: 14.xxx.xxx.180, server: qdtest.laoganbu.cn, request: "GET /help-web/index HTTP/1.1", upstream: "fastcgi://127.0.0.1:9000", host: "xxx.xxx.cn"

发现php文件 require文件的时候，路径跑到被链接的文件目录去了。而我们所需要的是获取链接文件所在的目录下的文件。

知道问题就好办了。把ln -s改为ln -d硬链接。

可以自己写个php，然后分别用这两种方式做链接到web目录。

1
2
3

<?
    echo __DIR__;
?>

usage： ln -[s|d] 源文件 链接文件

测试结果如下：
ln -s : 源文件所在的目录
ln -d : 链接文件所在的目录

今天遇到php用 file_get_contents 函数获取 https 链接的数据的时候，遇到如下错误。

1

operation failed with code 1. OpenSSL Error messages:error:14090086:SSL routines:SSL3_GET_SERVER_CERTIFICATE:certificate verify failed

我服务器环境是 Centos 7.

检查已经安装了 openssl包，并在php.ini中开启了 php_openssl 模块。测试发现问题依旧，最后在stackoverflow上找到了答案。

在php.ini中增加一行

openssl.cafile=/etc/pki/tls/certs/ca-bundle.crt

至于如果不确定php的配置文件位置，最好用phpinfo函数打印出来看看。如果机子只有单个环境 直接执行 php -i | grep config 找。

机子Ubuntu，之前一直用的rdesktop连接的远程桌面。

由于是命令行，加上不常用，总会经常性忘记命令参数，又要查阅帮助，不慎其烦。而且也不能保存密码。

于是苦苦搜寻，还真找到一款满意的工具。支持 RDP和SSH协议。

似乎前身就是 csclient

官网：http://www.remmina.org/

源码:https://github.com/FreeRDP/Remmina/wiki

安装

1
2
3

sudo apt-add-repository ppa:remmina-ppa-team/remmina-next
sudo apt-get update
sudo apt-get install remmina remmina-plugin-rdp libfreerdp-plugins-standard

用法：

图形简单清晰，不用介绍

FantasyShooter

入门必搞的太空射击小游戏。

如果还没安装pygame模块的

sudo pip install pygame or pip install -r requirements.txt

安装好模块后直接 python fantasyshooter.py 即可进行激情射击。

目前实现：

• 敌机
• 炸弹
• 战机
• 子弹
• 统计分数和miss数

项目代码下载地址

None

None一句话就是有点类似其它语言的NULL。是个无类型的值。None等于False。

Dictionaries 字典类型。

其实就是常见的 Key => Value 键值对类型，当索引的key不存在的时候，会抛出KeyError

类型实例

1
2
3
4

mydict = {'a':1,'b':2}

print(mydict['a'])
1

字典类型的key必须是不可以变的。

字典的赋值十分简单，无论key存在与否，都可以直接赋值。存在的话就改变值，不存在就自动新建一个。

判断key是否存在 in 和 not in

例子：

1
2
3
4
5
6
7
8

nums = { 
    1:'a',
    2:'b',
    3:'c',
 }
print(1 in nums)
print(a not in nums)
print(3 in nums)

结果：

1
2
3

True
True
True

字典一个比较有用的函数 get

当你访问一个不存在的key的时候，它会返回一个特殊值None，还可以自定义缺省值，找不到就返回某个值。

例子：

1
2
3
4
5
6
7
8

nums = { 
    1:'a',
    2:'b',
    3:'c',
 }
print(nums.get(1))
print(nums.get(4))
print(nums.get(4,"字典里没有4"))

结果：

1
2
3
4

a
None
字典里没有4

由于list的实现不是传统意义上的链表实现，采用的是在一块连续的内存空间。所以在Insert的时候，经常要将插入的位置右边的数据挪一下。而append并不需要。

所以能用append的尽量用append。