Greenhats の Blog.

算法笔记(python)

Python 算法
2025/02/10
loading

算法笔记(python)(非原创)

作者：春华秋实

一、算法引入

1、时间复杂度与大O表示法

实现算法的执行时间可以反应算法的效率，即算法的优劣。

单纯依靠运行的时间比较算法的优劣不一定是客观准确的。

同一段程序在不同机器上的运行时间不同，但是执行基本运算的数量是大体相同。、

基本运算的数量总和叫做时间复杂度。

“大O记法”：对于单调的整数函数f，如果存在一个整数函数g和实常数c>0，使得对于充分大的n总有 f(n)\leq c\times g(n) ，就是函数g是f的一个渐近函数（忽略常数），记为 f(n) = O(g(n)) 。也就是说，在趋向无穷的极限意义下，函数f的增长速度收到函数g的约束，亦即函数f与函数g的特征相似。

时间复杂度：假设存在函数g，使得算法A处理规模为n的问题示例所用时间为 T(n) = O(g(n)) ，则称 O(g(n)) 为算法A的渐进时间复杂度，简称时间复杂度，记为 T(n) 。

  • 算法完成工作最少需要多少基本步骤，即最优时间复杂度
  • 算法完成工作最多需要多少基本步骤，即最坏时间复杂度（主要关注）
  • 算法完成工作平均需要多少基本步骤，即平均时间复杂度。

2、时间复杂度的几条基本计算规则

  1. 基本操作，即只有常数项，认为其时间复杂度为O(1)。
  2. 顺序结构，时间复杂度按加法进行计算。
  3. 循环结构，时间复杂度按乘法进行计算。
  4. 分支结构，时间复杂度取最大值。
  5. 判断一个算法的效率时，往往只需要关注操作数量的最高次项，其他次要项和常数项可以忽略。
  6. 在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度。

常见时间复杂度

执行次数函数举例 阶 非正式术语
12 O(1) 常数阶
2n+3 O(n) 线性阶
3n2 + 2n + 1 O(n2) 平方阶
5log2n + 20 O(logn) 对数阶
2n+3nlog2n+19 O(nlogn) nlogn阶
6n3+2n2+3n+4 O(n3) 立方阶
2n O(2n) 指数阶

注意：经常把 log_{2}n （以2为底的对数）简写成logn

3、常见时间复杂度之间的关系：

O(1)<O(logn)<O(n)<O(nlogn)<O(n^{2})<O(n^{3})<O(2^{n})<O(n!)<O(n^{n})

4、python内置类型性能分析

timeit模块可以用来测试一小段python代码的执行速度

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
def test1():                                                   
    l = []                                                     
    for i in range(1000):                                      
        l = l + [i]                                            
                                                               
def test2():                                                   
    l = []                                                     
    for i in range(1000):                                      
        l.append(i)                                            
                                                               
def test3():                                                   
    l = [i for i in range(1000)]                               
                                                               
def test4():                                                   
    l = list(range(1000))                                      
                                                               
from timeit import Timer                                       
                                                               
t1 = Timer(stmt="test1()", setup="from __main__ import test1") 
print("concat test1", t1.timeit(number=1000), "seconds")       
                                                               
t2 = Timer(stmt="test2()", setup="from __main__ import test2") 
print("concat test2", t2.timeit(number=1000), "seconds")       
                                                               
t3 = Timer(stmt="test3()", setup="from __main__ import test3") 
print("concat test3", t3.timeit(number=1000), "seconds")       
                                                               
t4 = Timer(stmt="test4()", setup="from __main__ import test4") 
print("concat test4", t4.timeit(number=1000), "seconds")       

# 输出：
concat test1 0.5512763329970767 seconds
concat test2 0.028967999998712912 seconds
concat test3 0.013255332996777724 seconds
concat test4 0.006944332999410108 seconds

5、数据结构

数据时一个抽象的概念，将其进行分类后得到程序设计语言中的基本类型。数据元素之间不是独立的，存在特定的关系，这些关系便是结构。数据结构指数据对象中数据元素之间的关系。

算法与数据结构的区别：数据结构只是静态的描述了数据元素之间的关系，高效的程序需要在数据结构的基础上设计和选择算法。

程序 = 数据结构 + 算法

总结：算法是为了解决实际问题而设计的，数据结构是算法需要处理的问题载体。

线性表：

  • 顺序表：将元素顺序的存放在一块连续的存储区域里，元素间的顺序关系有它们的存储顺序自然表示。
  • 链表：将元素存放在通过链接构造起来的一系列存储块中。

二、抽象数据类型（Abstract Data Type)

1、顺序表

**顺序表的结构：一个顺序表的完整部分包括两部分：一部分是表中的元素集合，另一部分是为实现正确操作而需记录的信息，即有关表的整体情况的信息，这部分信息主要包括元素存储区的容量和当前表中已有的元素个数**两项。

顺序表的两种基本实现方式：

  • 一体式结构：存储表信息的单元与元素存储区以连续的方式安排在一块存储区里，两部分数据的整体形成一个完整的顺序表对象。一体式结构整体性强，易于管理。但由于数据元素存储区域是表对象的一部分，顺序表创建后，元素存储区就固定了。
  • 分离式结构：表对象里只保存与整个表有关的信息（即容量和元素个数），实际数据元素存放在另一个独立的元素存储区里，通过链接与基本表对象关联。

元素存储区替换

一体式结构由于顺序表信息区与数据区连续存储在一起，所以若想更换数据区，只能整体搬迁，即整个顺序表对象（指存储顺序表的结构信息的区域）改变了。

分离式结构若想更换数据区，只需要将表信息区中的数据区链接地址更新即可，而该顺序表对象不变。

元素存储区扩充

采用分离式结构的顺序表，若将数据区更换为存储空间更大的区域，则可以在不改变表对象的前提下对其数据存储区进行了扩充，所有使用这个表的地方不必修改。只要程序的运行环境（计算机系统）还有空间存储，这种表结构就不会因为满了而导致操作无法进行。人们把采用这种技术实现的顺序表称为动态顺序表，因为其容量可以在使用中动态变化。

扩充的两种策略：

  • 每次扩充增加固定数目的存储位置，如每次扩充增加10个元素位置，这种策略可称为线性增长。特点：节省时间，但是扩充操作频繁，操作次数多。
  • 每次扩充容量加倍，如每次扩充增加一倍存储空间。特点：减少了扩充操作的执行次数，但可能会浪费空间资源，以空间换时间，推荐的方式。

增加（删除）元素

  1. 尾部加入元素（删除表尾元素），时间复杂度为O(1)；
  2. 非保序的加入（删除）元素（不常见），时间复杂度为O(1);
  3. 保序的元素加入（删除），时间复杂度为O(n)；

Python中的顺序表

python中的list和tuple两种类型采用了顺序表的实现技术，具有前面讨论的顺序表的所有性质。

tuple是不可变类型，即不变的顺序表，因此不支持改变其内部状态的任何操作，而其他方面，则与list的性质类似。

在python的官方实现中，list就是一种采用分离式技术实现的动态顺序表。这就是为什么用list.append(x)（或list.insert(len(list),x)，即尾部插入）比在指定位置插入元素效率高的原因。

在python的官方实现中，list实现采用如下的策略：在建立空表（或很小的表）时，系统分配一块能容纳8个元素的存储区；在执行插入操作（insert或append）时，如果元素存储区满就换一块4倍大的存储区。但如果此时表已经很大（目前的阈值为50000），则改变策略，采用加一倍的方法。引入这种改变的策略的方式，是为了避免出现空闲的存储位置。

2、链表

为什么需要链表

顺序表的构建需要预先知道数据大小来申请连续的存储空间，而在进行扩充时又需要进行数据的搬迁，所以使用起来并不是很灵活。

链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。

链表的定义

链表（Linked list）时一种常见的基础数据结构，是一种线性表，但是不像顺序表一样连续存储数据，而是在每一个节点（数据存储单元）里存放下一个节点的位置信息（即地址）。

单向链表

单向链表也叫单链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。

  • 表元素域elem用来存放具体的数据。
  • 链接域next用来存放下一个节点的位置（python中的标识）
  • 变量p指向链表的头节点（首节点）的位置，从p出发能找到表中的任意节点。

节点的实现

1
2
3
4
5
6
7
class SingNode(object):
    '''单链表的节点'''
    def __init__(self, item):
        # _item 存放数据元素
        self.item = item
        # _next 是下一个节点的标识
        self.next = None

单链表的操作：

  • is_empty() 链表是否为空
  • length() 链表长度
  • travel() 遍历整个链表
  • add(item) 链表头部添加元素
  • append(item)链表尾部添加元素
  • insert(pos, item) 指定位置添加元素
  • remove(item) 删除节点
  • search(item) 查找节点是否存在
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
class SingNode(object):
    '''单链表的节点'''
    def __init__(self, item):
        # item 存放数据元素
        self.item = item
        # next 是下一个节点的标识
        self.next = None

class SingleLinkList(object):
    '''单链表'''
    def __init__(self, node = None):
        self.__head = node

    def is_empty(self):
        '''链表是否为空'''
        return self.__head == None

    def length(self):
        '''链表长度'''
        # cur 游标，用来移动遍历节点
        cur = self.__head
        # count 记录数量
        count = 0
        while cur != None:
            count += 1
            cur = cur.next
        return count
    def travel(self):
        '''遍历整个链表'''
        cur = self.__head
        while cur != None:
            print(cur.item, end=' ')
            cur = cur.next
        print()
        print('-'*30)

    def add(self, item):
        '''链表头部添加元素'''
        node = SingNode(item)
        node.next = self.__head
        self.__head = node

    def append(self, item):
        '''链表尾部添加元素，尾插法'''
        node = SingNode(item)
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next != None:
                cur = cur.next
            cur.next = node


    def insert(self, pos, item):
        '''指定位置添加元素
        :params pos: 从0开始
        '''

        if pos <= 0:
            self.add(item)
        elif pos > self.length()-1:
            self.append(item)
        else:
            node = SingNode(item)
            pre = self.__head
            count = 0
            while count < (pos-1):
                pre = pre.next
                count += 1
            node.next = pre.next
            pre.next = node

    def remove(self, item):
        '''删除节点'''
        cur = self.__head
        pre = None
        while cur != None:
            if cur.item == item:
                # 先判断此节点是否是头节点
                if cur == self.__head:
                    self.__head = cur.next
                else:
                    pre.next = cur.next
                break
            else:
                pre = cur
                cur = cur.next
    def search(self, item):
        '''查找节点是否存在'''
        cur = self.__head
        while cur != None:
            if cur.item == item:
                return True
            else:
                cur = cur.next
        return False

if __name__ == '__main__':

    sll = SingleLinkList()
    sll.append(1)
    sll.append(2)
    sll.append(3)
    sll.append(4)
    sll.append(5)

    sll.travel()
    sll.insert(1, 100)
    sll.travel()
    print(sll.search(100))
    sll.remove(5)
    sll.travel()

链表与顺序表的对比

链表失去了顺序表随机读取的优点，同时链表由于增加了节点的指针域，空间开销比较大，但对存储空间的使用要相对灵活。

操作 链表 顺序表
访问元素 O(n) O(1)
在头部插入/删除 O(1) O(n)
在尾部插入/删除 O(n) O(1)
在中间插入/删除 O(n) O(n)

注意虽然表面看起来都是O(n)，但链表和顺序表在插入和删除时进行的是完全不同的操作。链表的主要耗时操作是遍历查找，删除和插入操作本身的复杂度是O(1)。顺序表查找很快，主要耗时的操作是拷贝覆盖。因为除了目标元素在尾部的特殊情况，顺序表在进行插入和删除时需要对操作点之后的所有元素进行前后疑为操作，只能通过拷贝和覆盖的操作进行。

单向循环链表

单链表的一个变形，链表中的最后一个节点的next域不在时None，而是指向链表的头节点。

操作：

  • is_empty() 链表是否为空
  • length() 链表长度
  • travel() 遍历整个链表
  • add(item) 链表头部添加元素
  • append(item)链表尾部添加元素
  • insert(pos, item) 指定位置添加元素
  • remove(item) 删除节点
  • search(item) 查找节点是否存在
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
class SingNode(object):
    '''单向循环链表的节点'''
    def __init__(self, item):
        # item 存放数据元素
        self.item = item
        # next 是下一个节点的标识
        self.next = None

class SingleCycleLinkList(object):
    '''单向循环链表'''
    def __init__(self, node = None):
        self.__head = node
        if node:
            node.next = node

    def is_empty(self):
        '''链表是否为空'''
        return self.__head == None

    def length(self):
        '''链表长度'''
        if self.is_empty():
            return 0
        # cur 游标，用来移动遍历节点
        cur = self.__head
        # count 记录数量
        count = 1
        while cur.next != self.__head:
            count += 1
            cur = cur.next
        return count
    def travel(self):
        '''遍历整个链表'''
        if self.is_empty():
            return None
        cur = self.__head
        while cur.next != self.__head:
            print(cur.item, end=' ')
            cur = cur.next
        # 退出循环，cur指向尾节点，但尾节点元素未打印
        print(cur.item)
        print('-'*30)

    def add(self, item):
        '''链表头部添加元素'''
        node = SingNode(item)
        if self.is_empty():
            self.__head = node
            node.next = self.__head
        else:
            cur = self.__head
            while cur.next != self.__head:
                cur = cur.next
            # 退出循环之后的cur指向尾节点
            node.next = self.__head
            self.__head = node
            cur.next = self.__head

    def append(self, item):
        '''链表尾部添加元素，尾插法'''
        node = SingNode(item)
        if self.is_empty():
            self.__head = node
            node.next = self.__head
        else:
            cur = self.__head
            while cur.next != self.__head:
                cur = cur.next

            cur.next = node
            node.next = self.__head


    def insert(self, pos, item):
        '''指定位置添加元素
        :params pos: 从0开始
        '''

        if pos <= 0:
            self.add(item)
        elif pos > self.length()-1:
            self.append(item)
        else:
            node = SingNode(item)
            pre = self.__head
            count = 0
            while count < (pos-1):
                pre = pre.next
                count += 1
            node.next = pre.next
            pre.next = node

    def remove(self, item):
        '''删除节点'''
        if self.is_empty():
            return None

        cur = self.__head
        pre = None
        while cur.next != self.__head:
            if cur.item == item:
                # 先判断此节点是否是头节点
                if cur == self.__head:
                    # 头节点
                    # 寻找尾节点
                    rear = self.__head
                    while rear.next != self.__head:
                        rear = rear.next
                    self.__head = cur.next
                    rear.next = self.__head
                else:
                    # 中间节点
                    pre.next = cur.next
                return None
            else:
                pre = cur
                cur = cur.next
        # 退出循环，cur指向尾节点
        if cur.item == item:
            if cur == self.__head:
                # 链表只有一个节点
                self.__head = None
            else:
                pre.next = cur.next
    def search(self, item):
        '''查找节点是否存在'''
        if self.is_empty():
            return False

        cur = self.__head
        while cur.next != self.__head:
            if cur.item == item:
                return True
            else:
                cur = cur.next
        # 退出循环，cur指向尾节点，但未进行判断
        if cur.item == item:
            return True
        return False

if __name__ == '__main__':

    sll = SingleCycleLinkList()
    sll.append(1)
    sll.append(2)
    sll.append(3)
    sll.append(4)
    sll.append(5)

    sll.travel()
    sll.insert(1, 100)
    sll.travel()
    print(sll.search(100))
    sll.remove(5)
    sll.travel()
    sll.remove(1)
    sll.travel()
# 输出结果：
1 2 3 4 5
------------------------------
1 100 2 3 4 5
------------------------------
True
1 100 2 3 4
------------------------------
100 2 3 4
------------------------------

双向链表

一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接：一个指向前一个节点，此节点为第一个节点时指向空值；而另一个指向下一个节点，此节点为最后一个节点时，指向空值。

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
# coding:utf-8

class Node(object):
    """节点"""
    def __init__(self, item):
        self.item = item
        self.next = None
        self.prev = None

class DoubleLinkList(object):
    """双链表"""
    def __init__(self, node=None):
        self.__head = node

    def is_empty(self):
        '''链表是否为空'''
        return self.__head is None

    def length(self):
        '''链表长度'''
        # cur 游标，用来移动遍历节点
        cur = self.__head
        # count 记录数量
        count = 0
        while cur != None:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        '''遍历整个链表'''
        cur = self.__head
        while cur != None:
            print(cur.item, end=' ')
            cur = cur.next
        print()
        print('-' * 30)

    def add(self, item):
        '''链表头部添加元素'''
        node = Node(item)
        if self.is_empty():
            self.__head = node
        else:
            node.next = self.__head
            self.__head = node
            node.next.prev = node

    def append(self, item):
        '''链表尾部添加元素，尾插法'''
        node = Node(item)
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next != None:
                cur = cur.next

            cur.next = node
            node.prev = cur

    def insert(self, pos, item):
        '''指定位置添加元素
        :params pos: 从0开始
        '''

        if pos <= 0:
            self.add(item)
        elif pos > self.length() - 1:
            self.append(item)
        else:
            node = Node(item)
            cur = self.__head
            count = 0
            while count < pos:
                cur = cur.next
                count += 1
            # 当退出循环时，cur指向pos
            node.next = cur
            node.prev = cur.prev
            cur.prev.next = node
            cur.prev = node

    def remove(self, item):
        '''删除节点'''
        cur = self.__head
        while cur != None:
            if cur.item == item:
                # 先判断此节点是否是头节点
                if cur == self.__head:
                    self.__head = cur.next
                    if cur.next != None:
                        # 判断链表是否只有一个链表
                        cur.next.prev = None
                    else:
                        pass
                else:
                    cur.prev.next = cur.next
                    if cur.next != None:
                        cur.next.prev = cur.prev
                break
            else:
                cur = cur.next

    def search(self, item):
        '''查找节点是否存在'''
        cur = self.__head
        while cur != None:
            if cur.item == item:
                return True
            else:
                cur = cur.next
        return False

if __name__ == '__main__':
    dll = DoubleLinkList()
    dll.append(1)
    dll.append(2)
    dll.append(3)
    dll.append(4)
    dll.append(5)

    dll.travel()
    dll.insert(1, 100)
    dll.travel()
    print(dll.search(100))
    dll.remove(5)
    dll.travel()

3、栈

栈（stack），有些地方称为堆栈，是一种容器，可存入数据元素、访问元素、删除元素，它的特点在于只能允许在容器的一端（称为栈顶端指标，英语：top）进行加入数据（英语：push）和输出数据（英语：pop）的运算。没有了位置概念，保证任何时候可以访问、删除的元素都是此前最后存入的那个元素，确定了一种默认的访问顺序。

由于栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO，Last in First Out）的原理运作。

栈结构实现

栈可以用顺序表实现，也可以用链表实现。

栈的操作

  • Stack() 创建一个新的空栈
  • push(item) 添加一个新的元素item到栈顶
  • pop() 弹出栈顶元素
  • peek() 返回栈顶元素
  • is_empty() 判断是否为空
  • size() 返回栈的元素个数
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
# coding:utf-8

class Stack(object):
    """栈"""
    def __init__(self):
        self.__list = []

    def push(self, item):
        '''添加一个新的元素item到栈顶'''
        self.__list.append(item)
    def pop(self):
        '''弹出栈顶元素'''
        if self.is_empty():
            return None
        else:
            return self.__list.pop()

    def peek(self):
        '''返回栈顶元素'''
        if self.is_empty():
            return None
        else:
            return self.__list[-1]
    def is_empty(self):
        '''判断是否为空'''
        return self.__list == []
    def size(self):
        '''返回栈的元素个数'''
        return len(self.__list)

if __name__ == '__main__':
    stack = Stack()

    stack.push(1)
    stack.push(2)
    stack.push(3)
    stack.push(4)

    print(stack.pop())
    print(stack.pop())
    print(stack.pop())
    print(stack.pop())
    print(stack.pop())
    print(stack.pop())

# 输出：
4
3
2
1
None
None

4、队列

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出（First in First Out）的线性表，简称FIFO。允许插入的一端为队尾，允许删除的一端为队头。队列不允许在中间部位进行操作。假设队列是 q = (a1, a2, ……, an)，那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，总是在队列最后。这也比较符合我们日常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。

队列结构实现

同栈一样，队列也可以用顺序表或者链表实现。

队列的操作

  • Queue() 创建一个空的队列
  • enqueue(item) 往队列中添加一个item元素
  • dequeue()从队列头部删除一个元素
  • is_empty() 判断一个队列是否为空
  • size() 返回队列的大小

实现

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
# coding:utf-8

class Queue(object):
    """队列"""
    def __init__(self):
        self.__items = []
    def enqueue(self, item):
        '''往队列中添加一个item元素'''
        self.__items.append(item)
    def dequeue(self):
        '''从队列头部删除一个元素'''
        if self.is_empty():
            return None
        else:
            return self.__items.pop(0)

    def is_empty(self):
        '''判断一个队列是否为空'''
        return self.__items == []

    def size(self):
        '''返回队列的大小'''
        return len(self.__items)

if __name__ == '__main__':
    queue = Queue()
    queue.enqueue(1)
    queue.enqueue(2)
    queue.enqueue(3)
    queue.enqueue(4)

    print(queue.dequeue())
    print(queue.dequeue())
    print(queue.dequeue())
    print(queue.dequeue())
    print(queue.dequeue())
    print(queue.dequeue())

# 输出
1
2
3
4
None
None

5、双端队列

双端队列（deque， 全名double-ended queue），是一种具有队列和栈的性质的数据结构

双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。

操作：

  • Deque 创建一个空的双端队列
  • add_front(item) 从队头加入一个item元素
  • add_rear(item) 从队尾加入一个item元素
  • remove_front() 从队头删除一个item元素
  • remove_rear() 从队尾删除一个item元素
  • is_empty() 判断双端队列是否为空
  • size() 返回队列的大小

实现

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
# coding:utf-8

class Deque(object):
    """双端队列"""
    def __init__(self):
        self.__items = []

    def add_front(self, item):
        '''从队头加入一个item元素'''
        self.__items.insert(0, item)
    def add_rear(self, item):
        '''从队尾加入一个item元素'''
        self.__items.append(item)
    def remove_front(self):
        '''从队头删除一个item元素'''
        if self.is_empty():
            return None
        else:
            return self.__items.pop(0)
    def remove_rear(self):
        '''从队尾删除一个item元素'''
        if self.is_empty():
            return None
        else:
            return self.__items.pop()
    def is_empty(self):
        '''判断双端队列是否为空'''
        return self.__items == []
    def size(self):
        '''返回队列的大小'''
        return len(self.__items)

if __name__ == '__main__':
    deque = Deque()

三、排序与搜索

排序算法（英语：Sorting Algorithm)是一种将一串数据依照特定顺序进行排序的一种算法。

常见排序算法效率比较

  • 冒泡排序

  • 平均情况 O(n^2)

  • 最好情况 O(n)

  • 最坏情况： O(n^2)

  • 辅助空间： O(1)

  • 稳定性：稳定

  • 选择排序：

  • 平均情况 O(n^2)

  • 最好情况 O(n^2)

  • 最坏情况： O(n^2)

  • 辅助空间： O(1)

  • 稳定性：不稳定

  • 插入排序：

  • 平均情况 O(n^2)

  • 最好情况 O(n)

  • 最坏情况： O(n^2)

  • 辅助空间： O(1)

  • 稳定性：稳定

  • 希尔排序

  • 平均情况 O(nlogn)～O(n^2)

  • 最好情况 O(n^{1.3})

  • 最坏情况： O(n^2)

  • 辅助空间： O(1)

  • 稳定性：不稳定

  • 堆排序

  • 平均情况 O(nlogn)

  • 最好情况 O(nlogn)

  • 最坏情况：O(nlogn)

  • 辅助空间： O(1)

  • 稳定性：不稳定

  • 归并排序

  • 平均情况 O(nlogn)

  • 最好情况 O(nlogn)

  • 最坏情况：O(nlogn)

  • 辅助空间： O(n)

  • 稳定性：稳定

  • 快速排序：

  • 平均情况 O(nlogn)

  • 最好情况 O(nlogn)

  • 最坏情况：O(n^2)

  • 辅助空间： O(log~n)～O(n)

  • 稳定性：不稳定

1. 排序算法的稳定性

稳定性：稳定排序算法会让原本有相等键值的记录维持相对次序。也就是如果一个排序算法是稳定的，当有两个相等键值的记录R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。

当相等的元素是无法分辨的，比如像是整数，稳定性并不是一个问题。然而，假设一下的数对将要以它们的第一个数字进行排序。

1
(4, 1)  (3, 1)  (3, 7)  (5, 6)

在这个情况中，可能会产生两种不同的结果，一个是让相等键值的记录维持相对的顺序，而另一个则没有：

1
2
(3, 1)  (3, 7)  (4, 1)  (5, 6) （维持次序）
(3, 7)  (3, 1)  (4, 1)  (5, 6) （次序被改变）

不稳定排序算法可能在相等的键值中改变记录的相对次序，但是稳定排序算法不会如此。不稳定排序算法可以被特别地实现为稳定。做这件事的一个方式是人工扩充键值的比较，如此在其他方面相同键值的两个对象间之比较，（比如上面的比较中加入第二个标准：第二个键值的大小）就会被决定使用在原先数据次序中的条目，当作一个同分决赛。然而，要记住这种次序通常牵扯到额外的空间负担。

2. 冒泡排序

冒泡排序（英语：Bubble Sort）是一种简单的排序算法。它重复的遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序算法的运作如下：

  • 比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个
  • 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  • 针对所有的元素重复以上的步骤，除了最后一个。
  • 持续每次对越来越少的元素重复上面的步骤，知道没有任何一对数字需要比较。

冒泡排序的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# coding:utf-8
def bubble_sort(alist):
    """冒泡排序"""
    for j in range(len(alist)-1, 0, -1):
        # j 表示每次遍历需要比较的次数，是逐渐缩小的
        for i in range(j):
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]
        print("第{}次排序的结果：".format(len(alist)-j), alist)
    return alist

if __name__ == '__main__':
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    sort_alist = bubble_sort(alist)

输出结果：
第1次排序的结果： [26, 54, 17, 77, 31, 44, 55, 20, 93]
第2次排序的结果： [26, 17, 54, 31, 44, 55, 20, 77, 93]
第3次排序的结果： [17, 26, 31, 44, 54, 20, 55, 77, 93]
第4次排序的结果： [17, 26, 31, 44, 20, 54, 55, 77, 93]
第5次排序的结果： [17, 26, 31, 20, 44, 54, 55, 77, 93]
第6次排序的结果： [17, 26, 20, 31, 44, 54, 55, 77, 93]
第7次排序的结果： [17, 20, 26, 31, 44, 54, 55, 77, 93]
第8次排序的结果： [17, 20, 26, 31, 44, 54, 55, 77, 93]

时间复杂度

  • 最优时间复杂度： O(n) （表示遍历一次发现没有任何可以交换的元素，排序结束）
  • 最坏时间复杂度： O(n^{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
# coding:utf-8

def bubble_sort(alist):
    """冒泡排序"""
    for j in range(len(alist)-1, 0, -1):
        # j 表示每次遍历需要比较的次数，是逐渐缩小的
        for i in range(j):
            if alist[i][1] > alist[i+1][1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]
        print("第{}次排序的结果：".format(len(alist)-j), alist)
    return alist

if __name__ == '__main__':
    alist = [93, 54, 26, 93, 17, 77, 31, 44, 55, 20]
    new_alist = [i for i in enumerate(alist)]
    sort_alist = bubble_sort(new_alist)

# 输出结果：
第1次排序的结果： [(1, 54), (2, 26), (0, 93), (4, 17), (5, 77), (6, 31), (7, 44), (8, 55), (9, 20), (3, 93)]
第2次排序的结果： [(2, 26), (1, 54), (4, 17), (5, 77), (6, 31), (7, 44), (8, 55), (9, 20), (0, 93), (3, 93)]
第3次排序的结果： [(2, 26), (4, 17), (1, 54), (6, 31), (7, 44), (8, 55), (9, 20), (5, 77), (0, 93), (3, 93)]
第4次排序的结果： [(4, 17), (2, 26), (6, 31), (7, 44), (1, 54), (9, 20), (8, 55), (5, 77), (0, 93), (3, 93)]
第5次排序的结果： [(4, 17), (2, 26), (6, 31), (7, 44), (9, 20), (1, 54), (8, 55), (5, 77), (0, 93), (3, 93)]
第6次排序的结果： [(4, 17), (2, 26), (6, 31), (9, 20), (7, 44), (1, 54), (8, 55), (5, 77), (0, 93), (3, 93)]
第7次排序的结果： [(4, 17), (2, 26), (9, 20), (6, 31), (7, 44), (1, 54), (8, 55), (5, 77), (0, 93), (3, 93)]
第8次排序的结果： [(4, 17), (9, 20), (2, 26), (6, 31), (7, 44), (1, 54), (8, 55), (5, 77), (0, 93), (3, 93)]
第9次排序的结果： [(4, 17), (9, 20), (2, 26), (6, 31), (7, 44), (1, 54), (8, 55), (5, 77), (0, 93), (3, 93)]

3. 选择排序

选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理如下：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于最终正确的位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

选择排序的实现：

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
# coding:utf-8

def select_sort(alist):
    n = len(alist)
    # 需要进行n-1次选择操作
    for i in range(n-1):
        # 记录最小值的位置
        min_index = i
        # 从i+1位置到末尾选择出最小值
        for j in range(i+1, n):
            if alist[j] < alist[min_index]:
                min_index = j

        alist[i], alist[min_index] = alist[min_index], alist[i]

        print("第{}次排序的结果：".format(i+1), alist)
    return alist


if __name__ == '__main__':
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    sort_alist = select_sort(alist)

# 输出结果
第1次排序的结果： [17, 26, 93, 54, 77, 31, 44, 55, 20]
第2次排序的结果： [17, 20, 93, 54, 77, 31, 44, 55, 26]
第3次排序的结果： [17, 20, 26, 54, 77, 31, 44, 55, 93]
第4次排序的结果： [17, 20, 26, 31, 77, 54, 44, 55, 93]
第5次排序的结果： [17, 20, 26, 31, 44, 54, 77, 55, 93]
第6次排序的结果： [17, 20, 26, 31, 44, 54, 77, 55, 93]
第7次排序的结果： [17, 20, 26, 31, 44, 54, 55, 77, 93]
第8次排序的结果： [17, 20, 26, 31, 44, 54, 55, 77, 93]

时间复杂度

  • 最优时间复杂度： O(n^{2})
  • 最坏时间复杂度： O(n^{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
# coding:utf-8

def select_sort(alist):
    n = len(alist)
    # 需要进行n-1次选择操作
    for i in range(n-1):
        # 记录最小值的位置
        min_index = i
        # 从i+1位置到末尾选择出最小值
        for j in range(i+1, n):
            if alist[j][1] < alist[min_index][1]:
                min_index = j
        alist[i], alist[min_index] = alist[min_index], alist[i]
        print("第{}次排序的结果：".format(i+1), alist)
    return alist

if __name__ == '__main__':
    alist = [93, 54, 26, 93, 17, 77, 31, 44, 55, 20]
    new_alist = [i for i in enumerate(alist)]
    sort_alist = select_sort(new_alist)

# 输出结果：
第1次排序的结果： [(4, 17), (1, 54), (2, 26), (3, 93), (0, 93), (5, 77), (6, 31), (7, 44), (8, 55), (9, 20)]
第2次排序的结果： [(4, 17), (9, 20), (2, 26), (3, 93), (0, 93), (5, 77), (6, 31), (7, 44), (8, 55), (1, 54)]
第3次排序的结果： [(4, 17), (9, 20), (2, 26), (3, 93), (0, 93), (5, 77), (6, 31), (7, 44), (8, 55), (1, 54)]
第4次排序的结果： [(4, 17), (9, 20), (2, 26), (6, 31), (0, 93), (5, 77), (3, 93), (7, 44), (8, 55), (1, 54)]
第5次排序的结果： [(4, 17), (9, 20), (2, 26), (6, 31), (7, 44), (5, 77), (3, 93), (0, 93), (8, 55), (1, 54)]
第6次排序的结果： [(4, 17), (9, 20), (2, 26), (6, 31), (7, 44), (1, 54), (3, 93), (0, 93), (8, 55), (5, 77)]
第7次排序的结果： [(4, 17), (9, 20), (2, 26), (6, 31), (7, 44), (1, 54), (8, 55), (0, 93), (3, 93), (5, 77)]
第8次排序的结果： [(4, 17), (9, 20), (2, 26), (6, 31), (7, 44), (1, 54), (8, 55), (5, 77), (3, 93), (0, 93)]
第9次排序的结果： [(4, 17), (9, 20), (2, 26), (6, 31), (7, 44), (1, 54), (8, 55), (5, 77), (3, 93), (0, 93)]

4. 插入排序

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素向后挪位，为最新元素提供插入空间。

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
# coding:utf-8
def insert_sort(alist):
    # 从第二个位置，即下标为1的元素开始向前插入
    for i in range(1, len(alist)):
        # 从第i个元素开始向前比较，如果小于前一个元素，交换位置
        for j in range(i, 0, -1):
            if alist[j] < alist[j-1]:
                alist[j], alist[j-1] = alist[j-1], alist[j]
            else:
                break
        print("第{}次排序的结果：".format(i), alist)


if __name__ == '__main__':
    alist = [93, 54, 26, 93, 17, 77, 31, 44, 55, 20]
    new_alist = [i for i in enumerate(alist)]
    sort_alist = insert_sort(new_alist)

# 输出结果：
第1次排序的结果： [54, 93, 26, 93, 17, 77, 31, 44, 55, 20]
第2次排序的结果： [26, 54, 93, 93, 17, 77, 31, 44, 55, 20]
第3次排序的结果： [26, 54, 93, 93, 17, 77, 31, 44, 55, 20]
第4次排序的结果： [17, 26, 54, 93, 93, 77, 31, 44, 55, 20]
第5次排序的结果： [17, 26, 54, 77, 93, 93, 31, 44, 55, 20]
第6次排序的结果： [17, 26, 31, 54, 77, 93, 93, 44, 55, 20]
第7次排序的结果： [17, 26, 31, 44, 54, 77, 93, 93, 55, 20]
第8次排序的结果： [17, 26, 31, 44, 54, 55, 77, 93, 93, 20]
第9次排序的结果： [17, 20, 26, 31, 44, 54, 55, 77, 93, 93]

时间复杂度：

  • 最优时间复杂度： O(n) （升序排列，序列已经处于升序状态）
  • 最坏时间复杂度： O(n^{2})
  • 稳定性：稳定

5. 希尔排序

希尔排序（Shell Sort）是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL. Shell于1959年提出而得名。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键字越来越多，当增量减少至1时，整个文件恰被分成一组，算法遍终止。

希尔排序过程

希尔排序的基本思想：将数组列在一个表中并对列分别进行插入排序，重复这个过程，不过每次用更长的列（步长更长了，列数更少了）来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序。

例如，假设有这样一组数 [13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样它们就应该看起来是这样（竖着的元素是步长组成）：

1
2
3
4
13  14  94 33 82
25  59  94 65 23 
45  27  73 25 39
10

时间复杂度：

  • 最优时间复杂度：根据步长序列的不同而不同
  • 最坏时间复杂度： O(n^{2})
  • 稳定性：不稳定

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def shell_sort(alist):
    # 希尔排序
    n = len(alist)

    gap = n // 2

    while gap > 0:
        # 按步长进行插入排序
        for i in range(gap, n):
            j = i
            # 插入排序
            while j >= gap and alist[j]>alist[j-gap]:
                alist[j-gap], alist[j] = alist[j], alist[j-gap]
                j -= gap

        # 得到新的步长
        gap = gap // 2
    return alist

if __name__ == '__main__':
    alist = [13,  14,  94, 33, 82,  25,  59, 94, 65, 23, 45, 27, 73, 25, 39, 10]
    sort_alist = shell_sort(alist)
    print(sort_alist)

6. 快速排序

时间复杂度：

  • 最优时间复杂度： O(nlogn)
  • 最坏时间复杂度： O(n^{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
# coding:utf-8
def quick_sort(alist, first, last):
    """快速排序"""
    if first >= last:
        return
    n = len(alist)
    mid_value = alist[first]
    low, hight = first, last
    while low < hight:
        # hight 左移
        while low < hight and alist[hight] >= mid_value:
            hight -= 1
        alist[low] = alist[hight]

        while low < hight and alist[low] < mid_value:
            low += 1
        alist[hight] = alist[low]
        
    # 当循环退出时，low == hight
    alist[low] = mid_value
    # 对low左边的列表执行快速排序
    quick_sort(alist, first, low-1)
    # 对low右边的列表执行快速排序
    quick_sort(alist, low+1, last)

if __name__ == '__main__':
    alist = [13,  14,  94, 33, 82,  25,  59, 94, 65, 23, 45, 27, 73, 25, 39, 10]
    quick_sort(alist, 0, len(alist)-1)
    print(alist)

7. 归并排序

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
# coding:utf-8

def merge_sort(alist):
    """归并排序"""
    n = len(alist)
    if n <= 1:
        return alist
    mid = n // 2
    # left 表示采用归并排序后形成的有序的新的列表
    left_li = merge_sort(alist[:mid])
    # right 表示采用归并排序后形成的有序的新的列表
    right_li = merge_sort(alist[mid:])
    # 将两个有序的子序列合并成一个整体
    # merge(left, right)
    left_pointer, right_pointer = 0, 0
    result = []
    while left_pointer < len(left_li) and right_pointer < len(right_li):
        if left_li[left_pointer]  < right_li[right_pointer]:
            result.append(left_li[left_pointer])
            left_pointer += 1
        else:
            result.append(right_li[right_pointer])
            right_pointer += 1

    result.extend(left_li[left_pointer:])
    result.extend(right_li[right_pointer:])
    return result

if __name__ == '__main__':
    alist = [13,  14,  94, 33, 82,  25,  59, 94, 65, 23, 45, 27, 73, 25, 39, 10]
    sort_result = merge_sort(alist)
    print(sort_result)

8. 搜索算法（二分查找）

递归查找：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# coding:utf-8
def binary_search(alist, aim_item):
    """二分查找"""
    n = len(alist)
    if n > 0:
        mid = n // 2
        if alist[mid] == aim_item:
            return True
        elif aim_item < alist[mid]:
            return binary_search(alist[:mid], aim_item)
        else:
            return binary_search(alist[mid+1:], aim_item)
    return False

if __name__ == '__main__':
    sort_alist = [10, 13, 14, 23, 25, 25, 27, 33, 39, 45, 59, 65, 73, 82, 94, 94]
    print(sort_alist)
    print('='*100)
    find_result = binary_search(sort_alist, 10)
    print(find_result)
    print('=' * 100)
    find_result = binary_search(sort_alist, 100)
    print(find_result)

非递归查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def binary_search_2(alist, aim_item):
    """二分查找，非递归"""
    n = len(alist)
    first = 0
    last = n-1
    while first <= last:
        mid = (first+last) // 2
        if alist[mid] == aim_item:
            return True
        elif aim_item < alist[mid]:
            last = mid - 1
        else:
            first = mid + 1
    return False
if __name__ == '__main__':
    sort_alist = [10, 13, 14, 23, 25, 25, 27, 33, 39, 45, 59, 65, 73, 82, 94, 94]
    print(sort_alist)
    print('='*100)
    find_result = binary_search_2(sort_alist, 10)
    print(find_result)
    print('=' * 100)
    find_result = binary_search_2(sort_alist, 100)
    print(find_result)

四、树

1. 树的概念

树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n (n\geq1 )个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一颗倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

  • 每个节点具有零或多个字节点；
  • 没有父节点的节点称为根节点；
  • 每一个非根节点有且只有一个父节点；
  • 除了根节点外，每个字节点可以分为多个不相交的子树；

树的术语：

  • 节点的度：一个节点含有的子树的个数称为该节点的度；
  • 树的度：一棵树中，最大的节点的度称为树的度；
  • 叶节点或终端节点：度为零的节点；
  • 父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
  • 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
  • 兄弟节点：具有相同父节点的节点互称为兄弟节点‘
  • 节点的层次：从根开始起，根为第1层，根的子节点为第2层，以此类推；
  • 树的高度或深度：根中节点的最大层次；
  • 堂兄弟节点：父节点在同一层的节点互为堂兄弟；
  • 节点的祖先：从根到该节点所经分支上的所有节点；
  • 子孙：以某节点为根的子树中任一节点都称为该节点的子孙；
  • 森林：由m（ m\geq 0 ）颗互不相交的树的集合称为森林。

树的种类：

  • 无序树：树中任意节点的子节点没有顺序关系，这种树称为无序树，也称为自由树；

  • 有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；

  • 二叉树：每个节点最多含有两个子树的树称为二叉树；

  • 完全二叉树：对于一棵二叉树，假设其深度为d( d>1 )。除了第d层外，其他各层的节点数目均已达到最大值，且第d层所有节点从左到右连续地紧密排列，这样的二叉树被称为完全二叉树，其中满二叉树的定义是所有叶节点都在最底层的完全二叉树；

  • 平衡二叉树（AVL树）：当且仅当任何节点的两颗子树的高度差不大于1的二叉树；

  • 排序二叉树（二叉查询树）（英语：Binary Search Tree），也叫二叉搜索树、有序二叉树）

  • 霍夫曼树（用于信息编码）：带权路径最短的二叉树称为二叉树或最优二叉树；

  • B树：一种对读写操作进行优化的子平衡的二叉查找树，能够保持数据有序，拥有多余两个子树。

树的存储与表示

顺序存储：将数据结构存储在固定的数组中，然在遍历速度上有一定的优势，但因所占空间比较大，是非主流二叉树，二叉树通常以链式存储。

链式存储的：可以存储。缺陷：指针域指针个数不定。

由于对节点的个数无法掌握，常见树的存储表示都转换为二叉树进行处理，子节点个数最多为2。

常见的一些树的应用场景

  1. xml、html等，那么编写这些东西的解析器的时候，不可避免用到树。
  2. 路由协议就是使用了树的算法
  3. mysql数据库索引
  4. 文件系统的目录结构
  5. 所以很多经典的AI算法其实都是树搜索，此外机器学习中的decision tree也是树结构。

2. 二叉树

二叉树的基本概念

二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree）和“右子树”（right subtree）。

二叉树的性质（特性）

**性质1:**在二叉树的第 i 层上至多有 2^{i-1} 个节点（ i>0 ）；

性质2:深度为 k 的二叉树至多有 2^k-1 个节点（ k>0 ）；

性质3:对于任意一棵二叉树，如果其叶节点数为 n_{0} ，而深度为2的节点总数为 n_2 ，则 n_0=n_2+1 ；

性质4:具有 n 个节点的完全二叉树的深度必为 log_{2}(n+1)

性质5:对完全二叉树，若从上至下、从左至右编号，则编号为 i 的节点，其左孩子编号必为 2i ，其右孩子编号必为 2i+1 ；其双亲的编号必为 \frac{i}{2} （ i=1 时为根，除外）。

（1）完全二叉树——若设二叉树的高度为 h ，除第 h 层外，其他各层( 1～h-1 ）的节点数都达到最大个数，第 h 层有叶子节点，并且叶子节点都是从左到右依次排布，这就是完全二叉树。

（2）满二叉树——除了叶子节点外每一个节点都有左右子叶且叶子节点都处在最底层的二叉树。

二叉树的节点表示以及数的创建

通过使用Node类中定义三个属性，分别为elem本身的值，还有lchild左孩子和rchild右孩子

3. 二叉树遍历

深度优先遍历：

  • 先序遍历：根 左 右
  • 中序遍历：左 根 右
  • 后序遍历：左 右 根
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
class Node(object):
    """节点类"""
    def __init__(self, item = -1, lchild = None, rchild = None):
        self.elem = item
        self.lchild = lchild
        self.rchild = rchild

class Tree(object):
    """二叉树"""
    def __init__(self):
        self.root = None

    def add(self, item):
        node = Node(item)
        if self.root is None:
            self.root = node
            return
        queue = [self.root]
        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.rchild is None:
                cur_node.rchild = node
                return
            else:
                queue.append(cur_node.rchild)

    def breadth_travel(self):
        """广度有限遍历"""
        if self.root is None:
            return
        queue = [self.root]
        while queue != []:
            cur_node = queue.pop(0)
            print(cur_node.elem, end='-->')
            if cur_node.lchild is not None:
                queue.append(cur_node.lchild)
            if cur_node.rchild is not None:
                queue.append(cur_node.rchild)

    # 深度优先遍历
    def preorder(self, node):
        """先序遍历"""
        if node is None:
            return
        print(node.elem, end='-->')
        self.preorder(node.lchild)
        self.preorder(node.rchild)

    def inorder(self, node):
        """中序遍历"""
        if node is None:
            return
        self.inorder(node.lchild)
        print(node.elem, end='-->')
        self.inorder(node.rchild)

    def postorder(self, node):
        """后序遍历"""
        if node is None:
            return
        self.postorder(node.lchild)
        self.postorder(node.rchild)
        print(node.elem, end='-->')

if __name__ == '__main__':
    tree = Tree()
    # print(tree.root)
    tree.add(0)
    tree.add(1)
    tree.add(2)
    tree.add(3)
    tree.add(4)
    tree.add(5)
    tree.add(6)
    tree.add(7)
    tree.add(8)
    tree.add(9)

    # print(tree.root.elem)
    print('-' * 100)
    tree.breadth_travel()
    print()
    print('-'*100)
    print('先序遍历：')
    tree.preorder(tree.root)
    print()
    print('-' * 100)
    print('中序遍历：')
    tree.inorder(tree.root)
    print()
    print('-' * 100)
    print('后序遍历：')
    tree.postorder(tree.root)

## 输出结果
----------------------------------------------------------------------------------------------------
0-->1-->2-->3-->4-->5-->6-->7-->8-->9-->
----------------------------------------------------------------------------------------------------
先序遍历：
0-->1-->3-->7-->8-->4-->9-->2-->5-->6-->
----------------------------------------------------------------------------------------------------
中序遍历：
7-->3-->8-->1-->9-->4-->0-->5-->2-->6-->
----------------------------------------------------------------------------------------------------
后序遍历：
7-->8-->3-->9-->4-->1-->5-->6-->2-->0-->
CATALOG
  1. 1. 算法笔记(python)(非原创)
    1. 1.0.1. 作者：春华秋实
  2. 1.1. 一、算法引入
    1. 1.1.1. 1、时间复杂度与大O表示法
    2. 1.1.2. 2、时间复杂度的几条基本计算规则
    3. 1.1.3. 3、常见时间复杂度之间的关系：
    4. 1.1.4. 4、python内置类型性能分析
    5. 1.1.5. 5、数据结构
  3. 1.2. 二、抽象数据类型（Abstract Data Type)
    1. 1.2.1. 1、顺序表
    2. 1.2.2. 2、链表
    3. 1.2.3. 3、栈
    4. 1.2.4. 4、队列
    5. 1.2.5. 5、双端队列
  4. 1.3. 三、排序与搜索
    1. 1.3.1. 1. 排序算法的稳定性
    2. 1.3.2. 2. 冒泡排序
    3. 1.3.3. 3. 选择排序
    4. 1.3.4. 4. 插入排序
    5. 1.3.5. 5. 希尔排序
    6. 1.3.6. 6. 快速排序
    7. 1.3.7. 7. 归并排序
    8. 1.3.8. 8. 搜索算法（二分查找）
  5. 1.4. 四、树
    1. 1.4.1. 1. 树的概念
    2. 1.4.2. 2. 二叉树
    3. 1.4.3. 3. 二叉树遍历
Total : 9
2025
OBS 网课 Docker Hexo Linux Nginx PM2 Node.js Python 算法 Website
生存 技术