队列 (Queue)
队列是一种运算受限的线性结构，遵循先进先出（FIFO）原则。
队列是一种受限的线性结构
受限之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作
普通队列
queue.Queue，适用于多线程环境。
双端队列
collections.deque，具有队列和栈性质的数据结构 ，允许在两端进行元素的添加和移除。deque是一个双端队列的实现，它提供了在两端快速添加和移除元素的能力。（结合使用appendleft和popleft时，你实际上是在实现一个栈（Stack）的数据结构 ，append和pop结合使用同理。 ）
优先队列 ：元素按照优先级排序。Python 标准库中提供了 queue.PriorityQueue 和 heapq 模块来实现优先队列。
heapq
heapq 模块是 Python 标准库中的一个模块，提供了基于堆的优先队列实现。heapq 模块不是线程安全的，适用于单线程环境。
代码实现 ：
#普通队列
import queue
q = queue.Queue()
q.put(1)
q.put(3)
q.put(2)
print(q.qsize())
print(q.get())
print(q.get())
print(q.get())
#双端队列
from collections import deque
q = deque()
q.append(1)
q.append(2)
q.appendleft(3)
q.appendleft(4)
print(q.pop())
print(q.popleft())
#优先队列
import queue
q = queue.PriorityQueue()
# 向队列中添加元素，元素是一个元组 (priority, item)，其中 priority 是优先级，item 是实际的数据
q.put((1,'item1'))
q.put((3,'item3'))
q.put((2,'item2'))
print(q.get())
print(q.get())
print(q.get())
#heapq模块
import heapq
# 创建一个列表作为堆
heap = []
# 向堆中添加元素，元素是一个元组 (priority, item)
heapq.heappush(heap, (3, 'Task 3'))
heapq.heappush(heap, (1, 'Task 1'))
heapq.heappush(heap, (2, 'Task 2'))
# 从堆中取出元素
print(heapq.heappop(heap)) # 输出: (1, 'Task 1')
print(heapq.heappop(heap)) # 输出: (2, 'Task 2')
print(heapq.heappop(heap)) # 输出: (3, 'Task 3')
树 (Tree)
树的定义:
树是由: n（n≥0）个节点组成的层次结构，每个节点有零个或多个子节点。
1.当n=0时，称为空树；
2.对于任一棵非空树（n> 0），它具备以下性质：
3.树中有一个称为“根（Root）”的特殊结点，用 root 表示；
4.其余结点可分为m(m>0)个互不相交的有限集T1，T2，... ，Tm，其中每个集合本身又是一棵
树，称为原来树的“子树（SubTree）”
注意:
1.子树之间不可以相交
2.除了根结点外，每个结点有且仅有一个父结点；
3.一棵N个结点的树有N-1条边。
树的术语 ：
节点的度：子树个数。
树的度：最大节点度数。
叶子节点：度为0的节点。
父节点：有子树的节点。
子节点：父节点的子树的根节点。
兄弟节点：具有同一父节点的节点。
路径和路径长度：从节点到另一节点的节点序列及其边数。
节点的层次：根节点为1层，其他节点为父节点层数加1。
树的深度：最大节点层次。
二叉树 (Binary Tree)
定义
二叉树是由节点和边组成的树，每个节点最多有两个子节点。
二叉树可以为空, 也就是没有结点.
若不为空，则它是由根结点和称为其左子树TL和右子树TR的两个不相交的二叉树组成。
二叉树有五种形态:
注意c和d是不同的二叉树, 因为二叉树是有左右之分的
特性 ：
第i层最大节点数：2^(i 1)。
深度为k的二叉树最大节点总数：2^k 1。
叶子节点数n0 = 度为2的非叶子节点数n2 + 1。
特殊二叉树
满二叉树：每层节点都有2个子节点。
完全二叉树：除最后一层外，其他各层节点数都达到最大个数，最后一层从左向右的叶子节点连续存在。
存储 ：通常使用链表存储，每个节点包含数据、左子节点引用和右子节点引用。
遍历 （按照顺序访问节点）：
前序遍历：根节点、左子树、右子树。
中序遍历：左子树、根节点、右子树。
后序遍历：左子树、右子树、根节点。
二叉查找树 (Binary Search Tree, BST)
二叉查找树是一种特殊的二叉树，具有以下性质：
每个节点都有一个键值。
左子树中的所有节点的键值都小于该节点的键值。
右子树中的所有节点的键值都大于该节点的键值。
左子树和右子树也是二叉查找树。
不允许出现键值相等的节点。
创建二叉查找树节点
class TreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
key: 节点的键值。
left:指向左子节点的指针。
right: 指向右子节点的指针
创建二叉查找树类
class BinarySearchTree:
def __init__(self):
self.root = None
root: 指向二叉搜索树的根节点。初始时为 None
插入节点
插入操作的步骤：
1. 树为空
直接将新节点作为根节点。
2. 树不为空
从根节点开始，根据新节点的键值与当前节点的键值的比较结果，决定向左子树还是右子树
移动。
如果新节点的键值小于当前节点的键值，如果当前节点没有左子树，则将新节点插入到当前
节点的左子树，否则向左子树移动。
如果新节点的键值大于当前节点的键值，如果当前节点没有右子树，则将新节点插入到当前
节点的右子树，否则向右子树移动。
重复上述步骤，直到找到一个空位置，将新节点插入到该位置
def insert(self, key):
if self.root is None:
self.root = TreeNode(key)
else:
self._insert(self.root, key)
def _insert(self, node, key):
if key < node.key:
if node.left is None:
node.left = TreeNode(key)
else:
self._insert(node.left, key)
elif key > node.key:
if node.right is None:
node.right = TreeNode(key)
else:
self._insert(node.right, key)
查找节点
def search(self, key):
return self._search(self.root, key)
def _search(self, node, key):
if node is None or node.key == key:
return node
if key < node.key:
return self._search(node.left, key)
return self._search(node.right, key)
删除节点
def delete(self, key):
self.root = self._delete(self.root, key)
def _delete(self, node, key):
if node is None:
return node
if key < node.key:
node.left = self._delete(node.left, key)
elif key > node.key:
node.right = self._delete(node.right, key)
else:
if node.left is None and node.right is None:
return None
elif node.left is None:
return node.right
elif node.right is None:
return node.left
temp = self._min_value_node(node.right)
node.key = temp.key
node.right = self._delete(node.right, temp.key)
return node
def _min_value_node(self, node):
current = node
while current.left is not None:
current = current.left
return current
中序遍历
先遍历左子树，然后访问当前节点，最后遍历右子树。
def inorder_traversal(self):
result = []
self._inorder_traversal(self.root, result)
return result
前序遍历
先访问根节点、然后遍历左子树、最后遍历右子树。
代码实现：
class TreeNode:
def __init__(self,key):
self.left = None
self.right = None
self.key = key
class LeftTree:
def __init__(self):
self.root = None
def left_search(self):
result = []
if self.root is None:
return result
self._left_search(self.root, result)
return result
def _left_search(self, node,result):
if node is None:
return None
result.append(node.key)
if node.left is not None:
self._left_search(node.left, result)
if __name__ == "__main__":
tree = LeftTree()
tree.root = TreeNode(1)
tree.root.left = TreeNode(2)
tree.root.right = TreeNode(3)
tree.root.left.left = TreeNode(4)
tree.root.left.right = TreeNode(5)
tree.root.right.left = TreeNode(6)
tree.root.right.right = TreeNode(7)
print(tree.left_search())
#输出：[1, 2, 4]
后序遍历
先访问左子树、然后遍历右子树、最后遍历根节点。
代码实现：
class TreeNode:
def __init__(self, key):
self.left = None
self.right = None
self.key = key
class BehindTree:
def __init__(self):
self.root = None
def behind_search(self):
result = []
if self.root is None:
return result
self._behind_search(self.root, result)
return result
def _behind_search(self, node, result):
if node is None:
return
self._behind_search(node.left, result)
self._behind_search(node.right, result)
result.append(node.key)
if __name__ == "__main__":
# 创建一个二叉树
tree = BehindTree()
tree.root = TreeNode(1)
tree.root.left = TreeNode(2)
tree.root.right = TreeNode(3)
tree.root.left.left = TreeNode(4)
tree.root.left.right = TreeNode(5)
tree.root.right.left = TreeNode(6)
tree.root.right.right = TreeNode(7)
print(tree.behind_search())
# 输出: [4, 5, 2, 6, 7, 3, 1]