队列与树数据结构复习笔记

2.3 队列

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

队列是一种受限的线性结构
受限之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作

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

2.3.1 普通队列

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

案例：

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())

2.3.2 双端队列

双端队列（Deque，Double-Ended Queue）是一种具有队列和栈性质的数据结构，它允许我们在两端进行元素的添加（push）和移除（pop）操作。在Python中，双端队列可以通过collections模块中的deque类来实现。

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

案例：

from collections import deque


q = deque()

q.append(1)
q.append(2)
q.appendleft(3)
q.appendleft(4)

print(q.pop())
print(q.popleft())

当结合使用appendleft和popleft时，你实际上是在实现一个栈（Stack）的数据结构，因为栈是后进先出（LIFO）的，而这两个操作正好模拟了栈的“压栈”和“弹栈”行为。append和pop结合使用同理。

2.3.3 优先队列

优先队列（Priority Queue）是一种特殊的队列，其中的元素按照优先级进行排序。优先级最高的元素总是最先出队。Python 标准库中提供了 queue.PriorityQueue 和 heapq 模块来实现优先队列。

queue.PriorityQueue

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

案例：

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

heapq 模块是 Python 标准库中的一个模块，提供了基于堆的优先队列实现。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')

2.4 树

2.4.1 概念和术语

术语

在描述树的各个部分的时候有很多术语。

为了让介绍的内容更容易理解, 需要知道一些树的术语.
不过大部分术语都与真实世界的树相关, 或者和家庭关系相关(如父节点和子节点), 所以它们比较容易理解.

我们先来看一下树的结构

树的定义:

树（Tree）: n（n≥0）个结点构成的有限集合。
- 当n=0时，称为空树；
- 对于任一棵非空树（n> 0），它具备以下性质：
- 树中有一个称为“根（Root）”的特殊结点，用 root 表示；
- 其余结点可分为m(m>0)个互不相交的有限集T1，T2，… ，Tm，其中每个集合本身又是一棵树，称为原来树的“子树（SubTree）”
注意:
- 子树之间不可以相交
- 除了根结点外，每个结点有且仅有一个父结点；
- 一棵N个结点的树有N-1条边。

树的术语:

1.结点的度（Degree）：结点的子树个数.
2.树的度：树的所有结点中最大的度数. (树的度通常为结点的个数N-1)
3.叶子结点（Leaf）：度为0的结点. (也称为叶子结点)
4.父结点（Parent）：有子树的结点是其子树的根结点的父结点
5.子结点（Child）：若A结点是B结点的父结点，则称B结点是A结点的子结点；子结点也称孩子结点。
6.兄弟结点（Sibling）：具有同一父结点的各结点彼此是兄弟结点。
7.路径和路径长度：从结点n1到nk的路径为一个结点序列n1 , n2,… , nk, ni是 ni+1的父结点。路径所包含边的个数为路径的长度。
8.结点的层次（Level）：规定根结点在1层，其它任一结点的层数是其父结点的层数加1。
9.树的深度（Depth）：树中所有结点中的最大层次是这棵树的深度。

2.4.2 二叉树

2.4.2.1 概念

二叉树的定义

二叉树可以为空, 也就是没有结点.
若不为空，则它是由根结点和称为其左子树TL和右子树TR的两个不相交的二叉树组成。

二叉树有五种形态:

注意c和d是不同的二叉树, 因为二叉树是有左右之分的.

2.4.2.2 特性

二叉树有几个比较重要的特性, 在笔试题中比较常见:
- 一个二叉树第 i 层的最大结点数为：2^(i-1), i >= 1;
- 深度为k的二叉树有最大结点总数为： 2^k - 1, k >= 1;
- 对任何非空二叉树 T，若n0表示叶结点的个数、n2是度为2的非叶结点个数，那么两者满足关系n0 = n2 + 1。

2.4.2.3 特殊的二叉树

满二叉树(Full Binary Tree）

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

完全二叉树(Complete Binary Tree)

除二叉树最后一层外, 其他各层的节点数都达到最大个数.
且最后一层从左向右的叶结点连续存在, 只缺右侧若干节点.
满二叉树是特殊的完全二叉树.
下面不是完全二叉树, 因为D节点还没有右结点, 但是E节点就有了左右节点.

2.4.2.4 二叉树的存储

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

链表存储:

二叉树最常见的方式还是使用链表存储.
每个结点封装成一个Node, Node中包含存储的数据, 左结点的引用, 右结点的引用.

2.4.2.5 二叉树遍历

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

遍历规则：

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

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

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

2.4.3 二叉查找树

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

每个节点都有一个键值（key）。
对于每个节点，其左子树中的所有节点的键值都小于该节点的键值。
对于每个节点，其右子树中的所有节点的键值都大于该节点的键值。
左子树和右子树也分别是二叉查找树。
二叉查找树不允许出现键值相等的结点。

二叉查找树的主要操作包括插入、删除和遍历。代码实现如下：

2.4.3.1 创建二叉查找树节点

class TreeNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

key: 节点的键值。
left: 指向左子节点的指针。
right: 指向右子节点的指针。

2.4.3.2 创建二叉查找树类

class BinarySearchTree:
    def __init__(self):
        self.root = None

root: 指向二叉搜索树的根节点。初始时为 None。

2.4.3.3 插入节点

插入操作的步骤：

如果树为空：直接将新节点作为根节点。
如果树不为空：
- 从根节点开始，根据新节点的键值与当前节点的键值的比较结果，决定向左子树还是右子树移动。
- 如果新节点的键值小于当前节点的键值，如果当前节点没有左子树，则将新节点插入到当前节点的左子树，否则向左子树移动。
- 如果新节点的键值大于当前节点的键值，如果当前节点没有右子树，则将新节点插入到当前节点的右子树，否则向右子树移动。
- 重复上述步骤，直到找到一个空位置，将新节点插入到该位置。

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)

insert(key): 公开的插入方法。如果树为空，则创建一个新节点作为根节点；否则，调用 _insert 方法进行递归插入。
_insert(node, key): 递归插入方法。根据键值的大小，递归地在左子树或右子树中插入新节点。

2.4.3.4 查找节点

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)

2.4.3.5 删除节点

删除逻辑：

1.递归查找待删除节点

如果待删除节点的键值小于当前节点的键值，递归地在左子树中查找并删除。
如果待删除节点的键值大于当前节点的键值，递归地在右子树中查找并删除。

2.找到待删除节点

删除操作的步骤可以分为以下几种情况：

待删除节点是叶子节点（没有子节点）：直接删除该节点。
待删除节点只有一个子节点：用其子节点替换该节点。
待删除节点有两个子节点：
- 找到右子树中的最小节点（即后继节点）。
- 用后继节点的键值替换待删除节点的键值。
- 删除后继节点（后继节点要么是叶子节点，要么只有一个右子节点）。

假设我们有以下二叉搜索树：

        50
       /  \
     30    70
    /  \  /  \
  20  40 60  80

删除节点 20

找到键值为 20 的节点。
该节点是叶子节点，直接删除。

删除后的树：

删除节点 30

找到键值为 30 的节点。
该节点有一个右子节点 40，用 40 替换 30。

删除后的树：

删除节点 50

找到键值为 50 的节点。
该节点有两个子节点，找到右子树中的最小节点 60（即后继节点）。
用 60 替换 50。
删除右子树中的 60。

删除后的树：

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:
        # 找到要删除的节点
        # 情况 1: 节点是叶子节点
        if node.left is None and node.right is None:
            return None
        # 情况 2: 节点只有一个子节点
        elif node.left is None:
            return node.right
        elif node.right is None:
            return node.left
        # 情况 3: 节点有两个子节点
        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

2.4.3.6 中序遍历

先遍历左子树，然后访问当前节点，最后遍历右子树。

def inorder_traversal(self):
    result = []
    self._inorder_traversal(self.root, result)
    return result

def _inorder_traversal(self, node, result):
    if node:
        self._inorder_traversal(node.left, result)
        result.append(node.key)
        self._inorder_traversal(node.right, result)

2.4.3.7 前序遍历

先访问根节点、然后遍历左子树、最后遍历右子树。

def preorder_search(self):
    result = []
    if self.root is None:
        return None
    self._preorder_search(self.root, result)
    return result

def _preorder_search(self,node,result):
    if node is None:
        return None
    result.append(node.key)
    self._preorder_search(node.left,result)
    self._preorder_search(node.right,result)

标签：node,结点,复习,队列,self,键值,key,数据结构,节点
From： https://blog.csdn.net/b227737437/article/details/143334470

队列与树数据结构复习笔记

2.3 队列

2.3.1 普通队列

2.3.2 双端队列

2.3.3 优先队列

2.4 树

2.4.1 概念和术语

2.4.2 二叉树

2.4.2.1 概念

2.4.2.2 特性

2.4.2.3 特殊的二叉树

2.4.2.4 二叉树的存储

2.4.2.5 二叉树遍历

2.4.3 二叉查找树

2.4.3.1 创建二叉查找树节点

2.4.3.2 创建二叉查找树类

2.4.3.3 插入节点

2.4.3.4 查找节点

2.4.3.5 删除节点

2.4.3.6 中序遍历

2.4.3.7 前序遍历

相关文章

赞助商

阅读排行

队列与树 数据结构复习笔记

2.3 队列

2.3.1 普通队列

2.3.2 双端队列

2.3.3 优先队列

2.4 树

2.4.1 概念和术语

2.4.2 二叉树

2.4.2.1 概念

2.4.2.2 特性

2.4.2.3 特殊的二叉树

2.4.2.4 二叉树的存储

2.4.2.5 二叉树遍历

2.4.3 二叉查找树

2.4.3.1 创建二叉查找树节点

2.4.3.2 创建二叉查找树类

2.4.3.3 插入节点

2.4.3.4 查找节点

2.4.3.5 删除节点

2.4.3.6 中序遍历

2.4.3.7 前序遍历

相关文章

赞助商

阅读排行

队列与树数据结构复习笔记