Python(数据结构2)

常见数据结构

队列

队列(Queue)，它是一种运算受限的线性表,先进先出(FIFO First In First Out)

Python标准库中的queue模块提供了多种队列实现，包括普通队列、双端队列、优先队列等。

1 普通队列

queue.Queue 是 Python 标准库 queue 模块中的一个类，适用于多线程环境。它实现了线程安全的 FIFO（先进先出）队列。

Queue:普通队列，从队尾入列，从列头出列
 put（）：入列
 get（）：出列

2 双端队列

deque是一个双端队列的实现，它提供了在两端快速添加和移除元素的能力。

deque:双端队列，既可以在队尾进行入队和出队操作，也可以在对头进行出队和入队
append：从队尾入队
appendleft：在队头入队
pop：从队尾出队
popleft：从队头出队
appendleft和popleft组合使用时，相当于栈操作

3 优先队列

queue.PriorityQueue

queue.PriorityQueue 是 Python 标准库 queue 模块中的一个类，适用于多线程环境。它实现了线程安全的优先队列。

向队列中添加元素，元素是一个元组 (priority, item)，其中 priority 是优先级，item 是实际的数据，prioriity越小优先级越高。

heapq

heapq 模块是 Python 标准库中的一个模块，提供了基于堆的优先队列实现。

heapq 模块不是线程安全的，适用于单线程环境。

heapq.heappush（heap，）：向堆中添加元素，元素是一个元组 (priority, item)

heapq.heappop(heap)：从堆中取出元素

树

二叉树

1 概念

• 二叉树可以为空, 也就是没有结点.

• 若不为空，则它是由根结点和称为其左子树TL和右子树TR的两个不相交的二叉树组成。

2 特性

二叉树有几个比较重要的特性, 在笔试题中比较常见:

• 一个二叉树第 i 层的最大结点数为：2^(i-1), i >= 1;

• 深度为k的二叉树有最大结点总数为： 2^k - 1, k >= 1;

• 对任何非空二叉树 T，若n0表示叶结点的个数、n2是度为2的非叶结点个数，那么两者满足关系n0 = n2 + 1。

3 特殊的二叉树

满二叉树(Full Binary Tree）

• 在二叉树中, 除了最下一层的叶结点外, 每层节点都有2个子结点, 就构成了满二叉树.

完全二叉树(Complete Binary Tree)

• 除二叉树最后一层外, 其他各层的节点数都达到最大个数.

• 且最后一层从左向右的叶结点连续存在, 只缺右侧若干节点.

• 满二叉树是特殊的完全二叉树.

4 二叉树的存储

二叉树的存储常见的方式是链表.

链表存储:

• 二叉树最常见的方式还是使用链表存储.

• 每个结点封装成一个Node, Node中包含存储的数据, 左结点的引用, 右结点的引用.

5 二叉树遍历

前序遍历（Pre-order Traversal）、中序遍历（In-order Traversal）和后序遍历（Post-order Traversal）是二叉树的三种基本遍历方式。

遍历规则：

前序遍历，按照以下顺序访问节点：根节点、左子树、右子树。

中序遍历，按照以下顺序访问节点：左子树、根节点、右子树。

后序遍历，按照以下顺序访问节点：左子树、右子树、根节点。

二叉查找树

二叉查找树（Binary Search Tree, BST）是一种特殊的二叉树，它具有以下性质：

1. 每个节点都有一个键值（key）。

2. 对于每个节点，其左子树中的所有节点的键值都小于该节点的键值。

3. 对于每个节点，其右子树中的所有节点的键值都大于该节点的键值。

4. 左子树和右子树也分别是二叉查找树。

5. 二叉查找树不允许出现键值相等的结点。

代码实现：

1.创建二叉查找树节点；2.创建二叉查找树类；3 插入节点；4 查找节点；5.删除节点；6 中序遍历。

TreeNode 类定义了一个节点，它有三个属性：

• key：存储节点的值。

• left：指向节点的左子节点，默认为 None。

• right：指向节点的右子节点，默认为 None。

BST 类定义了一个二叉搜索树，它有一个属性：

• root：指向树的根节点，默认为 None。

insert 方法用于插入一个新的节点到树中。如果树为空（即根节点 None），则创建一个新的节点作为根。如果树非空，则调用 _insert 方法来递归地插入节点。_insert 方法检查插入的键值与当前节点的键值，并相应地向左子树或右子树进行插入。

inorder_search 方法执行中序遍历，返回树中的所有键值。它首先初始化一个空的结果列表，然后调用 _inorder_search 辅助方法填充这个列表。_inorder_search 方法按照左子树 -> 当前节点 -> 右子树的顺序遍历整个树，并将每个节点的键值追加到结果列表中。

remove 方法用于从树中移除具有特定键值的节点。它通过调用 _remove 辅助方法来实现。_remove 方法是一个递归方法，它处理四种情况：

1. 如果树为空，返回 None。

2. 如果键值小于当前节点的键值，则递归地移除左子树中的节点。

3. 如果键值大于当前节点的键值，则递归地移除右子树中的节点。

4. 如果键值等于当前节点的键值，那么根据当前节点的情况来处理：

   • 如果当前节点没有子节点，则返回 None。

   • 如果当前节点只有一个子节点，则返回那个子节点。

   • 如果当前节点有两个子节点，则找到右子树中的最小值节点来替代当前节点，并递归地删除这个最小值节点。

_min_value_node 方法用于找到并返回从给定节点开始的子树中的最小值节点。它通过不断访问当前节点的左子节点直到到达最左边的叶子节点来实现。

Python包和模块

当使用Python编程时，包（Packages）和模块（Modules）是两个关键的概念，它们有助于组织、管理和复用代码。

模块（Modules）

一个.py 文件就是一个模块

• 把相关功能的函数等放在一起有利于管理，有利于多人合作开发

• 模块的分类

  1. 内置模块（在python3 程序内部，可以直接使用）

  2. 标准库模块(在python3 安装完后就可以使用的 )

  3. 第三方模块（需要下载安装后才能使用）

  4. 自定义模块(用户自己编写)

  5. 模块名如果要给别的程序导入，则模块名必须是 标识符

导入模块

import 模块名  [as 模块新名字1]

from 模块名 import 模块属性名 [as 属性新名]

from 模块名 import *

模块的内部属性

__file__  绑定模块的路径
__name__  绑定模块的名称
       如果是主模块（首先启动的模块）则绑定 '__main__'
       如果不是主模块则 绑定 xxx.py 中的 xxx 这个模块名

这样输入函数名可调用函数。

Python 常用的内建模块

1 random 模块

random.choice(seq)：从序列的元素中随机挑选一个元素，比如random.choice(range(10))，从0到9中随机挑选一个整数。

random.randrange (start, stop,step)：从指定范围内，按指定基数递增的集合中获取一个随机数，基数默认值为 1

输出一个范围在0到10的一个随机的偶数

random.random()：随机生成下一个实数，它在[0,1)范围内。

如图，random函数还可与其他函数组合使用，该图表示，在0到1间生成1个数，然后乘10，且保留两位小数，最后加上5.

random.shuffle(list)：将序列的所有元素随机排序,修改原list

uniform(x, y)：随机生成实数，它在[x,y]范围内.

 random.randint（a，b）：生产 a~b的随机整数

os 模块

os模块是Python标准库中的一部分，提供了一种与操作系统进行交互的方法。主要功能包括文件和目录的操作、路径处理、进程管理等。在使用os模块之前，我们需要先导入它：

os.getcwd():获取当前工作目录

os.chdir(path): 改变当前工作目录

os.listdir(path='.'): 返回指定目录下的所有文件和目录列表

os.mkdir(path): 创建目录

os.remove（path）: 删除目录

os.path 模块

os.path.split（path）：将文件路径和文件名切割，得到文件路径和文件名

os.path.exists（path）：判断目录或者文件是否存在

os.path.isdir（）：判断指定路径是否是目录

os.path.isfile（）：判断指定路径是否是文件