一、二分查找

1、思想

二分查找又被称为折半查找,优点就是比较次数少,查找速度快,平均性能好,但其缺点是要求待查表为有序表假设表中的元素是按照升序排列的,将表中间位置记录的关键字与查找的关键字作比较,如果两者相等,则查找成功;否者就利用中间位置记录分为前、后两个子表,如果中间位置的关键字大于查找关键字,则进一步查找前一个子表,否者就查找后一个子表,然后重复即可

2、实现

1
2
3
4
5
6
7
8
9
10
11
12
def binary_search(alist,item):
'''二分查找'''
n = len(alist)
if n > 0:
mid = n/2
if alist[mid] == item:
return True
elif item < alist[mid]:
binary_search(alist[:mid],item)
else:
binary_search(alist[mid+1:],item)
return False

3、时间复杂度问题

  • 关于时间复杂度的问题,首先讨论最坏的情况,就是进行到最后一步才找到元素item,在这种情况下因为是二分查找法,每次都是对半的,所以一共有O(log n)
  • 最优时间复杂度:O(1)

二、树

1、概念

它是另外一种数据结构,但元素之间的关系并不是线性结构,而是一种更为复杂的结构;但是它有以下特征: 1、如果他的结构不为空,则其中就存在着唯一的起始节点,称之为树根root;2、每个节点有零个或多个子节点;3、没有父节点的节点成为根节点;4、每一个非根节点有且只有一个父节点;5、除了根节点之外,每个子节点可以分为多个不相交的子树······

2、常用术语名称

  • 节点的度:一个节点含有的子树的个数称为该节点的度
  • 树的度:一棵树中,最大的节点的度
  • 叶子节点或终节点:度为零的节点
  • 父节点:若一个节点含有子节点,则这个节点就称为该子节点的父节点
  • 节点的层次:从根节点开始定义起,根为第一层,根的子节点为第二层,以此类推······
  • 树的高度或深度:树中节点的最大层次

3、树的分类

  • 无序树:树中任意节点的子节点之间没有顺序关系,也叫做自由树

  • 有序树:树中任意节点的子节点之间有顺序关系

    • 二叉树:每个节点最多含有两个子树的树

      • 完全二叉树:对于一颗二叉树,假设其深度为d,除了第d层外,其他各层的节点数目均已经达到最大值,且第d层所有节点从左向右连续的紧密排列;==满二叉树==的定义是所有叶节点都在最底层的完全二叉树;

      • 平衡二叉树<AVL树>:当且仅当任何节点的两棵子树得到高度差不超过2的二叉树

      • 排序二叉树(二叉查找树,binary search tree):也称为二叉搜索树、有序二叉树

![20190330](C:/Users/DELL/Desktop/markdown%E5%AD%A6%E4%B9%A0%E6%96%87%E6%A1%A3/20190330.jpg)

​      
  • 霍夫曼树:用于信息编码,待权路径最短的二叉树称为哈夫曼树或者是最优二叉树

  • B树:一种对读写操作进行优化的自平衡的二叉查找树,能够爆出数据有序,拥有多余两个子树;


树的应用场景

1、xml、html等标签的关系

2、路由协议运用了树的算法

3、mysql数据库索引

4、文件系统的目录结构

5、AI算法,机器学习中的 decision tree等

三、二叉树

1、性质

  • 在二叉树的第i层最多有2 ^i-1^ 个节点
  • 深度为k的二叉树最多有(2 ^k^ -1)个节点
  • 对于任意一颗二叉树,如果叶子节点数为N ~0~ ,而度数为2的节点的总数为N ~2~ ,则有N ~0~ = N ~2~ + 1;

2、实现

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
class Node(object):
'''构造节点'''
def __init__(self,item):
'''构造左右孩子'''
self.elem = item
self.lchild = None
self.rchild = None
class Tree(object):
'''二叉树'''
def __init__(self):
self.root = None
def add(self,item):
node = Node(item)
queue = [self.root]
if self.root is None:
self.root = node
return
# 判断队列是否为空
while queue:
# 取出当前节点
cur_node = queue.pop()
# 判断当前节点的左右子树是否为空
if cur_node.lchild is None:
cur_node.lchild = node
return
else:
queue.append(cur_node.lchild)
if cur_node.right is None:
cur_node.rchild = node
return
else:
queue.append(cur_node.right)

四、广度遍历

1、思想

这种遍历方法就是按照路径长度由远及近地访问节点,也即是说按照二叉树的层次遍历访问层中的每一个节点;==这种遍历无法使用递归==;在这种宽度优先遍历中,只规定了逐层访问,并没有规同一层的节点访问顺序,但从算法的角度上,必须规定一个顺序,常见的是在每一层里都从左往右逐个访问;==实现这一算法是用队列作为缓存;==

2、实现

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
class Node(object):
'''构造节点'''
def __init__(self,item):
'''构造左右孩子'''
self.elem = item
self.lchild = None
self.rchild = None
class Tree(object):
'''二叉树'''
def __init__(self):
self.root = None
def add(self,item):
node = Node(item)
queue = [self.root]
if self.root is None:
self.root = node
return
# 判断队列是否为空
while queue:
# 取出当前节点
cur_node = queue.pop(0)
# 判断当前节点的左右子树是否为空
if cur_node.lchild is None:
cur_node.lchild = node
return
else:
queue.append(cur_node.lchild)
if cur_node.right is None:
cur_node.rchild = node
return
else:
queue.append(cur_node.right)
def breath_travel(self):
'''广度优先遍历'''
if self.root is None:
return
queue = [self.root]
while queue:
cur_node = queue.pop(0)
print(cur_node.elem)
if cur_node.lchild is not None:
queue.append(cur_node.lchild)
if cur_node.rchild is not None:
queue.append.rchild(cur_node.rchild)

五、深度优先遍历

1、思想

深度优先遍历不同于广度优先遍历,其遍历有三种不同的方式:

先序遍历[^脚注1]中序遍历[^脚注2]后序遍历[^脚注3]

2、实现

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Node(object):
'''构造节点'''
def __init__(self,item):
'''构造左右孩子'''
self.elem = item
self.lchild = None
self.rchild = None
class Tree(object):
'''二叉树'''
def __init__(self):
self.root = None
def add(self,item):
node = Node(item)
queue = [self.root]
if self.root is None:
self.root = node
return
# 判断队列是否为空
while queue:
# 取出当前节点
cur_node = queue.pop(0)
# 判断当前节点的左右子树是否为空
if cur_node.lchild is None:
cur_node.lchild = node
return
else:
queue.append(cur_node.lchild)
if cur_node.right is None:
cur_node.rchild = node
return
else:
queue.append(cur_node.right)
def breath_travel(self):
'''广度优先遍历'''
if self.root is None:
return
queue = [self.root]
while queue:
cur_node = queue.pop(0)
print(cur_node.elem)
if cur_node.lchild is not None:
queue.append(cur_node.lchild)
if cur_node.rchild is not None:
queue.append.rchild(cur_node.rchild)
def preorder(self,node):
'''先序遍历'''
# 判断节点是否为空
if node is None:
return
print(node.elem) # 打印根节点
self.preorder(node.lchild) # 递归打印左子树
self.preorder(node.rchild) # 递归打印右子树
def inorder(self,node):
'''中序遍历'''
# 判断节点是否为空
if node is None:
return
self.inorder(node.lchild) # 递归打印左子树
print(node.elem) # 打印根节点
self.inorder(node.rchild) # 递归打印右子树
def postorder(self,node):
'''后序遍历'''
# 判断节点是否为空
if node is None:
return
self.postorder(node.lchild) # 递归打印左子树
self.postorder(node.rchild) # 递归打印右子树
print(node.elem) # 打印根节点

六、哈夫曼树

1、思想

设有实数集
$$
W = {w_0,w_1,w_2,\cdots,w_{m-1}}
$$
T是一颗扩充二叉树,其 m 个外部节点分别为以 w ~i~ 为权,而且T的带权外部路径长度 WPL在所有这样的扩充二叉树中达到最小,则称 T 为数据集 W 的 最优二叉树或者是哈夫曼树

Click Here and Learn More

2、实现

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
class BinTNode():
def __init__(self,item,leftchild=None,
rightchild=None):
self.elem = item
self.leftchild = leftchild
self.rightchild = rightchild
class HTNode(BinTNode): # 这里继承了BinTNode类,定义了一个专门为构建哈夫曼树的节点类,特点就是增加了一个小于的比较操作
def __lt__(self,othernodes):
return self.elem < othernode.elem
# 这里定义了一个专门为哈夫曼算法服务的优先队列类,其中增加了一个检查队列中元素个数的操作
class HuffmanPrioQ(PrioQueue):
def number(self):
return len(self._elems)


def HuffmanTree(weights):
tree = HuffmanPrioQ()
for w in weights:
tree.enqueue(HTNode(w))
while tree.number() > 1:
t1 = tree.dequeue()
t2 = tree.dequeue()
x = t1.elem + t2.elem
tree.enqueue(HTNode(x,t1,t2))
return tree.dequeue

算法复杂度:

第一个循环构造了m颗二叉树,并把他们加入大序列中,按照上面的写法则时间复杂度为O(m log m),因为加入一个元素需要O(log m)次筛选

第二个循环需要m-1次,每次减少一颗树。其中构造一颗新树的时间与m是无关的,是O(1)复杂度的操作。每次迭代需要把一颗新的树加入到优先队列,需要O(log m)复杂度的时间,整个循环就是O(m log m)时间;

3、树、森林、二叉树的关系

实际上是一种一一对应的关系,可以把任何一个(有序)树林映射到一颗二叉树上,而其逆映射把这颗二叉树映射回原来的树林,映射关系如下:

  • 顺序连接同一节点的各个子节点(它们原来在原树林里的兄弟节点),作为这些节点的右分支的边(也就是说,将树/森林中下一兄弟最为二叉树的右分支)
  • 保留每个节点到其第一个子节点的连接作为该节点的左分支,并删去这个节点到它节点的其他子节点的连接(即是说原森林里第一个子节点作为二叉树里的左分支)

[^脚注1]: 先序遍历方式:根 —>左—>右
[^脚注2]: 中序遍历方式:左 —>根—>右

[^脚注3]: 后序遍历方式:左 —>右—>根