每日分享
The first step to accepting yourself is to stop comparing yourself to others.
接受自己的第一步就是停止将自己和别人进行比较。
小闫语录：
每个人都喜欢将自己和其他人进行比较，换来的却是无尽的烦恼。因为在比较的过程中，往往迷失了最初的自己。将他人作为自己的榜样，为自己提供前进的动力，这样无可厚非。但请不要妄自菲薄，弄丢了真实的你。将自己的弱点与他人的优点比较，只能垂头丧气。深受一些鸡汤的毒害，也许你认为努力了就一定成功，奋斗了就一定能超越他人，他人能做到的你一定能做到。但是你忽略了一件事，一只小鸡，即使被人从悬崖上丢下去，它也不会像老鹰一样展翅翱翔。了解自己，正视自己，接受自己，成就自己。
一条插播
在进行树的讲解之前，先插播一个小的知识点（并不是广告，不要害怕）。这个知识点和树没有关系，是突然想到的一个知识点。那就是重载。
重载存在于静态语言中，是面向对象编程中一个重要的概念。它指的是多个相同函数名的函数，根据传入的参数个数，参数类型而执行不同的功能。函数重载实质上是为了解决编程中参数可变不统一的问题。
那么作为动态语言的python有重载吗？各说纷纭。我们从概念入手，『相同函数名的函数』在python中是不存在的，函数会根据从上到下的执行顺序发生覆盖。『传入的参数个数』也由于python的传参方式，可以限定在一个函数实施。『参数类型』因为python中不需要声明变量类型，所以函数可以接受任何类型的参数，也就无法根据参数类型来支持重载。
python中的传参方式有默认参数/可变参数/可变关键字参数。我们可以通过设置缺省值，让原本两个参数，只传一个参数即可。
所以说，python中本身就不需要重载。如果非要用这个重载的话，也是有解决办法的。python3.4中就提供了一个转发机制可以实现重载。
from functools import singledispatch @singledispatch def function(obj): print('%r'%(obj)) @function.register(int) def function_test(obj): print('Integer: %d' % (obj)) @function.register(str) def function_test(obj): print('String: %s' % (obj)) @function.register(list) def function_test(obj): print('List: %r' % (obj)) if __name__ == "__main__": function(1) function('hello') function([1,2,3])
结果为：
Integer: 1 String: hello List: [1, 2, 3]
树的介绍
树分为无序树和有序树。树中任意节点的子节点之间没有顺序关系，称为无序树。相反，有顺序关系就是有序树。
1.有序树
二叉树：每个节点最多有两个子树。
- 完全二叉树：二叉树，除最底层外，其他各层节点数目均已达到最大值，且最底层所有节点从左向右连续地紧密排列。不能左边的还没挂满，右边的已经挂了一些节点。
- 满二叉树：非叶节点都挂满了元素。也就是叶节点都在最底层的完全二叉树。
- 排序二叉树：根节点左边小于根节点，右边的大于根节点。也称为二叉查找树、二叉搜索树、有序二叉树。时间复杂度是
O(logn) - 平衡二叉树（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树。
霍夫曼树：用于信息的编码和数据压缩。带权路径最短的二叉树称为哈夫曼树或最优二叉树。
B树：对读写操作进行优化的自平衡二叉查找树，能够保持数据有序，拥有的子树多于两个。（排序多叉平衡树）
2.树的存储
树的存储可以采用顺序存储和链式存储。将数据结构存储在固定的数组中，虽然在遍历速度上有一定的优势，但是所占空间比较大，是非主流的存储方式。二叉树通常以链式存储。在链式存储时，有个小缺陷，就是指针域指针个数不定。由于对节点的个数无法掌握，常见的树的存储都将多叉树转换成二叉树进行处理，子节点个数最多为2。
链式存储数据时每个结点有两部分，一部分存储数据，一部分存储指针，即指向下一个元素存储位置。我们可以设计下面这样的二叉链表存储。
| lchild | data | rchild |
| 左孩子指针 | 数据域 | 右孩子指针 |
3.树的应用场景
1.路由协议使用了树的算法。
2.MySQL数据库索引使用了树结构。
3.文件系统的目录结构。
4.很多经典的AI算法都是树搜索。比如决策树。
4.MySQL索引
假如我们执行下面的一个SQL语句：
select *from students where name = xxx;
它会进行全表扫描，对比名字是否相等，如果数据量大，IO量也会很大，IO影响比较大。但是通过索引字段来查询，就要快的多。MySQL索引多采用B+树，下面就来回答为什么。
索引是有序的；索引是单独的文件；如果通过索引字段查询会先扫描索引区。
首先说一下B树，网上有大量介绍B树的文章，因此本文只简单的做一个介绍。B树是一种多路搜索树，它的每个节点可以拥有多个子节点，M路的B树最多能拥有M个孩子节点。那么为什么设计成多路的呢？这是为了降低树的高度，而且路数越多，树的高度越低，查询效率就高，但是不能无限多路，那样B树会退化成一个有序的数组。B树在文件系统的索引上用的比较多，这是考虑到文件系统和数据库都存在硬盘上，涉及到IO。当数据量大的时候很难一次性将所有的数据加载进内存，就更别提查询了。那怎么办？多路存储优势就显现了，每次只需加载B树的一个节点。虽然内存中红黑树比B树效率高，但是涉及到磁盘操作，B树要更胜一筹。
再来说一下B+树。B+树是对B树的改良，它将所有的数据存在叶子节点，叶子节点之间还加了指针，构成了有序链表。这样一来呢，就有一个极大的优点，就是只需遍历叶子节点就能遍历所有的数据。
面试题：B+树的时间复杂度为log(n)，hash时间复杂度为O(1)，那么为什么MySQL还要使用B+树而不是hash呢？
答：这与使用场景有关，hash虽然快，但是适合查询单条数据。我们使用MySQL时，常常需要查询大量的数据，这时候由于B+树叶子节点保存了所有数据，还是有序链表，它的查询效率就要高的多了。而且数据库的索引保存在硬盘中，我们需要考虑到往内存中加载的情况。数据量大的时候，无法一次性加载入内存，就无法查询了。B+树可以分批加载，每次只加载一个节点，解决了上面的问题，而且由于树的高度很低，查询效率也高的多的多。
二叉树
二叉树上面也提到了，就是每个节点最多有两个子树的树结构，通常被称为“左子树”和“右子树”。
它有很多性质，我们需要掌握两个：
性质1:在二叉树的第i层上至多有 2^(i-1)个结点（i>0）
性质2:深度为k的二叉树至多有 2^k-1个结点（k>0）
深度就是树中节点的最大层次。也称为树的高度。
1.二叉树的实现
我们先定义一个节点类，用来创建节点对象。节点包含数据域和指针域。数据域用来保存数据，指针域保存左孩子和右孩子的指针。
class Node(object): def __init__(self,item): self.item = item self.lchild = None self.rchild = None
然后再定义二叉树，一开始为空，实现添加节点的方法。
添加元素的时候，我们可以先创建一个队列。然后从根节点开始检查。根节点为空则将元素添加到根节点位置，根节点不为空则将根节点添加进队列。然后由根节点检查左孩子和右孩子，执行同样的操作。其实就是按照由上至下，从左往右的顺序检查树，将节点挂在为空的位置。
1. class BinaryTree(object): 2. def __init__(self): 3. self.root = None 4. 5. def add(self,item): 6. # 将数据保存成一个节点对象 7. node = Node(item) 8. # 如果根节点为空，将节点放在根节点位置 9. if self.root is None: 10. self.root = node 11. return 12. # 实现一个队列 13. queue = [self.root] 14. while queue: 15. # 为了先进先出，弹出第一个元素 16. cur = queue.pop(0) 17. # 如果左孩子为空，将节点挂到左孩子位置 18. if cur.lchild is None: 19. cur.lchild = node 20. return 21. # 左孩子不为空，将左孩子添加进队列 22. else: 23. queue.append(cur.lchild) 24. # 如果右孩子为空，将节点挂在右孩子位置 25. if cur.rchild is None: 26. cur.rchild = node 27. return 28. # 右孩子不为空，将右孩子添加进队列中 29. else: 30. queue.append(cur.rchild) 2.二叉树的遍历
二叉树因为是二维结构，具有纵向和横向两个方向，所以分为深度（高度）优先和广度（层次或者宽度）优先两种遍历方式。好像一张表，深度优先就是咱们按列遍历，广度优先则是按行遍历。
2.1广度优先遍历(层次优先遍历)
我们在上面二叉树类中定义一个广度优先的遍历方法。目的就是按照广度优先，将每一层的元素都遍历出来，先第一层再第二层。
def breadth_travel(self): # 如果根节点为空，树都没有，不用遍历了，直接返回即可。 if self.root is None: return # 如果有树，我们就要实现一个队列，将所有的节点都添加都队列中。 queue = [self.root] while queue: cur = queue.pop(0) print(cur.item) if cur.lchild is not None: queue.append(cur.lchild) if cur.rchild is not None: queue.append(cur.rchild)
travel[ˈtrævəl]：游历、旅行。我们引申为遍历。
breadth[brɛdθ]：宽度，广度。
2.2深度优先遍历
深度优先就是另一个维度优先的遍历方式。它按照根节点遍历的顺序分为三种方式：先序遍历、中序遍历和后序遍历。
先序遍历：根节点 --> 左子树 --> 右子树
中序遍历：左子树 --> 根节点 --> 右子树
后序遍历：左子树 --> 右子树 --> 根节点
2.2.1先序遍历
def pre_travel(self, node): # 设置递归退出条件 if node is None: return print(node.item) self.pre_travel(node.lchild) self.pre_travel(node.rchild)
我们先遍历根节点，然后将左孩子作为根节点遍历，再将右孩子作为根节点遍历，采用递归的方法，直至节点为空。
2.2.2中序遍历
def mid_travel(self, node): # 设置递归退出的条件 if node is None: return self.mid_travel(node.lchild) print(node.item) self.mid_travel(node.rchild)
2.2.3后序遍历
def post_travel(self, node): # 设置递归退出的条件 if node is None: return self.post_travel(node.lchild) self.post_travel(node.rchild) print(node.item)
post：在后面
注意
像这么基础的二叉树实现以及遍历，必须达到手写的程度。所以，努力练习吧，面试中基本是必考的内容。之前我一直不以为然，直到被问到，才发现自己是多么的蠢。
