数据结构——基础知识补充

1.队列

1.普通队列

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

2.双端队列

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

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

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

3.优先队列

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

queue.PriorityQueue

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

heapq

heapq 模块是 Python 标准库中的一个模块，提供了基于堆的优先队列实现。heapq 模块不是线程安全的，适用于单线程环境。

代码示例：

import queue
from collections import deque
import heapq


def pd_queue():
    """# 普通队列 队尾入队 对头出队
    # put()入队
    # get() 出队
    q = queue.Queue()
    q.put(55)
    q.put(44)
    q.put(33)
    print(q.qsize())
    print(q.get())
    print(q.get())
    print(q.get())"""

    # deque 双端队列 既可以在队尾进行入队和出队操作
    #               也可以在队头进行入队和出队操作
    # append()在队尾入队
    # appendleft()在队头入队
    # pop()在队尾出队
    # popleft()在队头出队

    # appendleft()和popleft()组合使用时 相当于栈的操作
    # append()和pop()同理
    dq = deque()
    dq.append(10)
    dq.append(20)
    dq.appendleft(30)
    dq.appendleft(40)
    print(dq.popleft())
    print(dq.popleft())
    print(dq.popleft())
    print(dq.popleft())

    print("----------------------------------------")
    pq = queue.PriorityQueue()


    pq.put((2,"item2"))
    pq.put((1,"item1"))
    pq.put((4,"item4"))
    pq.put((3,"item3"))
    print(pq.get())
    print(pq.get())
    print(pq.get())
    print(pq.get())

    print("----------------------------------------")
    # headq 优先队列 基于堆实现的 要预先定义一个数组作为heap堆对象 线程不安全
    # heappush() 向队中添加元素元组(优先级 元素值) 优先级的数值越小
    heap  = []
    heapq.heappush(heap, (1,"hq1"))
    heapq.heappush(heap, (3,"hq3"))
    heapq.heappush(heap, (2,"hq2"))
    heapq.heappush(heap, (4,"hq4"))
    print(heapq.heappop(heap))
    print(heapq.heappop(heap))
    print(heapq.heappop(heap))
    print(heapq.heappop(heap))
if __name__ == '__main__':
    pd_queue()

2.树

1.概念

1.术语

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

• 为了让介绍的内容更容易理解, 需要知道一些树的术语.

• 不过大部分术语都与真实世界的树相关, 或者和家庭关系相关(如父节点和子节点), 所以它们比较容易理解.

我们先来看一下树的结构

2.树的定义

• 树（Tree）: n（n≥0）个结点构成的有限集合。

  • 当n=0时，称为空树；

  • 对于任一棵非空树（n> 0），它具备以下性质：

  • 树中有一个称为“根（Root）”的特殊结点，用 root 表示；

  • 其余结点可分为m(m>0)个互不相交的有限集T1，T2，... ，Tm，其中每个集合本身又是一棵树，称为原来树的“子树（SubTree）”

  注意:

  • 子树之间不可以相交

  • 除了根结点外，每个结点有且仅有一个父结点；

  • 一棵N个结点的树有N-1条边。

3.树的术语:

• 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.二叉树

1.概念

二叉树的定义

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

二叉树有五种形态:

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

2.特性

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

• 一个二叉树第 i 层的最大结点数为：2^(i-1), i >= 1;
• 深度为k的二叉树有最大结点总数为： 2^k - 1, k >= 1;
• 对任何非空二叉树 T，若n0表示叶结点的个数、n2是度为2的非叶结点个数，那么两者满足关系n0 = n2 + 1。 

3.特殊的二叉树

1.满二叉树(Full Binary Tree）

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

2.完全二叉树(Complete Binary Tree)

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

4.二叉树的存储

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

链表存储:

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

5.二叉树遍历

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

遍历规则：

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

3.二叉查找树

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

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

二叉查找树的主要操作包括插入、删除和遍历。

1.创建二叉查找树

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

 参数说明：

• key: 节点的键值。

• left: 指向左子节点的指针。

• right: 指向右子节点的指针。

2.创建二叉查找树

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

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

3.插入节点

插入操作的步骤：

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)

• insert(key): 公开的插入方法。如果树为空，则创建一个新节点作为根节点；否则，调用 _insert 方法进行递归插入。

• _insert(node, key): 递归插入方法。根据键值的大小，递归地在左子树或右子树中插入新节点。

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)

5.删除节点 

删除逻辑：

1.递归查找待删除节点

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

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

2.找到待删除节点

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

1. 待删除节点是叶子节点（没有子节点）：直接删除该节点。

2. 待删除节点只有一个子节点：用其子节点替换该节点。

3. 待删除节点有两个子节点：

   • 找到右子树中的最小节点（即后继节点）。

   • 用后继节点的键值替换待删除节点的键值。

   • 删除后继节点（后继节点要么是叶子节点，要么只有一个右子节点）。

    def _remove(self, node, key):
        # 如果树为空则返回None
        if node is None:
            return None

        # 判断指定的key和当前节点的key的大小 如果指定的key小于当前节点的key 则递归遍历左子树
        # 如果指定的key大于当前节点的key 则递归遍历右子树
        if key < node.key:
            node.left = self._remove(node.left, key)
        elif key > node.key:
            node.right = self._remove(node.right, key)
        # 如果指定key等于当前节点key
        # 1.当前节点没有子节点 直接删除 返回None
        # 2.当前节点有一个子节点
        #   1.有右子节点 用右子节点替换当前节点
        #   2.有左子节点 用左子节点替换当前节点
        # 3.当前节点有两个节点
        #   查找当前节点的右节点的最小值 找到最小值 用这个最小值来替代当前节点
        else:
            # 如果当前节点 左右子树都为空 则返回None
            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
            # 如果当前节点右两个子树 则查询当前节点右子树的左子树找到最小值节点
            # 将最小值替换到当前节点 将最小值节点递归删除
            else:
                temp = self._min_value_node(node.right)
                node.key = temp.key
                # 以当前节点的右子树节点为根节点 删除最小值节点
                node.right = self._remove(node.right,temp.key)
        return node

    # 查找当前节点的最小值 最小值在当前节点的左子树中
    def _min_value_node(self,node):
        current = node
        while current.left is not None:
            current = current.left
        return node

6.遍历

遍历规则：

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

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

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

    # 中序遍历
    def inorder_search(self):
        result = []
        self._inorder_search(self.root,result)
        return result

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

    # 前序遍历
    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:
            result.append(node.key)
            self._preorder_search(node.left, result)
            self._preorder_search(node.right, result)

    # 后序遍历
    def afterorder_search(self):
        result = []
        self._afterorder_search(self.root, result)
        return result

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

整个代码实现：

# 定义二叉查找树节点
class TreeNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None


class BST:
    def __init__(self,):
        self.root = None

    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:
                # node.left表示当前节点的左子树节点
                self._insert(node.left,key)

        # 如果要插入的键值大于当前节点的键值
        # 则判断当前节点是否有右子树 没有则将新节点赋给当前节点的右子树
        # 有则继续向当前节点的右子树移动 递归插入
        else :
            if node.right is None:
                node.right = TreeNode(key)
            else:
                self._insert(node.right, key)

    # 中序遍历
    def inorder_search(self):
        result = []
        self._inorder_search(self.root,result)
        return result

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

    # 前序遍历
    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:
            result.append(node.key)
            self._preorder_search(node.left, result)
            self._preorder_search(node.right, result)

    # 后序遍历
    def afterorder_search(self):
        result = []
        self._afterorder_search(self.root, result)
        return result

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

    def remove_bst(self, key):

        self.root = self._remove(self.root, key)


    def _remove(self, node, key):
        # 如果树为空则返回None
        if node is None:
            return None

        # 判断指定的key和当前节点的key的大小 如果指定的key小于当前节点的key 则递归遍历左子树
        # 如果指定的key大于当前节点的key 则递归遍历右子树
        if key < node.key:
            node.left = self._remove(node.left, key)
        elif key > node.key:
            node.right = self._remove(node.right, key)
        # 如果指定key等于当前节点key
        # 1.当前节点没有子节点 直接删除 返回None
        # 2.当前节点有一个子节点
        #   1.有右子节点 用右子节点替换当前节点
        #   2.有左子节点 用左子节点替换当前节点
        # 3.当前节点有两个节点
        #   查找当前节点的右节点的最小值 找到最小值 用这个最小值来替代当前节点
        else:
            # 如果当前节点 左右子树都为空 则返回None
            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
            # 如果当前节点右两个子树 则查询当前节点右子树的左子树找到最小值节点
            # 将最小值替换到当前节点 将最小值节点递归删除
            else:
                temp = self._min_value_node(node.right)
                node.key = temp.key
                # 以当前节点的右子树节点为根节点 删除最小值节点
                node.right = self._remove(node.right,temp.key)
        return node

    # 查找当前节点的最小值 最小值在当前节点的左子树中
    def _min_value_node(self,node):
        current = node
        while current.left is not None:
            current = current.left
        return node




if __name__ == '__main__':
    bst = BST()
    bst.insert(3)
    bst.insert(1)
    bst.insert(2)
    bst.insert(5)
    bst.insert(4)
    # result = bst.inorder_search()
    # result = bst.preorder_search()
    result = bst.afterorder_search()
    print(result)