python 数据结构 2

三、队列

        线性表,先进先出（栈：后进先出）

        常用方法：put(参数) ：将参数放入队列；get()：获取队列的数据；qsize()：返回队列的大小

1、普通队列

        import queue 

        创建方法：queue.Queue()

import queue
q = queue.Queue()
q.put(1)
q.put(2)
print(q.get())  # 1
print(q.get())  # 2

2、双端队列

        from collections import deque

        创建方法：deque()

        常用方法：append(参数) ：将参数从队尾放入队列；appendleft(参数) ：将参数从对头放入队列；pop()：从队尾获取队列的数据；popleft()：从对头获取队列数据

from collections import deque
q = deque()
q.append(1)
q.append(2)
q.appendleft(-1)
q.appendleft(-2)
print(q)  # deque([-2, -1, 1, 2])
print(q.pop())  # 2
print(q.popleft())  # -2

3、优先队列  

        按照优先级进行排序，优先级最高的元素总是最先出队

3.1、queue.PriorityQueue

        import queue

        创建方法：queue.PriorityQueue()

import queue
q = queue.PriorityQueue()
q.put((1, '内容1'))
q.put((3, '内容2'))
q.put((2, '内容3'))
print(q)  # deque([-2, -1, 1, 2])
print(q.get())  # (1, '内容1')
#  参数为元组，元组第一个元素为优先级顺序，第二个为内容
print(q.get())  # (2, '内容3')
print(q.get())  # (3, '内容2')

3.2、heapq

        import heapq

import heapq
heap = []
heapq.heappush(heap, (1, '内容1'))
heapq.heappush(heap, (3, '内容2'))
heapq.heappush(heap, (2, '内容3'))
print(heapq.heappop(heap))  # (1, '内容1')
# 按照参数第二个（元组）的第一个参数进行定义优先级
print(heapq.heappop(heap))  # (2, '内容3')
print(heapq.heappop(heap))  # (3, '内容2')

四、树

        如同公司结构的关系，从上到下依次为一对多的关系；子树之间不可以相交，每个节点有且仅有一个父节点。

结点的度（Degree）：该节点直接连接的子节点个数.

树的度：所有节点度最大那个。(满树的度通常为结点的个数减去1（ N-1）)

叶子结点（Leaf）：度为0的结点，没有子节点。 

父结点（Parent）：有直接相连的节点，那么该节点就成为这些节点的父节点。

子结点（Child）：有直接相连的节点，那么这些节点就成为该节点的子节点。

兄弟结点（Sibling）：具有同一父结点的各结点彼此是兄弟结点。

路径和路径长度：从结点n1到nk的路径为一个结点序列n1 , n2,… , nk, ni是 ni+1的父结点。路径所包含边的个数为路径的长度。

结点的层次（Level）：规定根结点在1层，其它任一结点的层数就是该节点与根节点之间存在了多少个直接相连的父节点的个数加1。

树的深度（Depth）：节点层次数的最大值就是数的深度。

1、二叉树的定义

        子节点的度最高为2（全部都为2或存在0 称为完全二叉树（除最后一层外，其余都满度），完全二叉树的叶子节点都在同一层次，那么称为完全二叉树（最后一层的度都0，其他都满度））

二叉树                                        完全二叉树                        满二叉树

                               ​​​​​​​        

一个二叉树第 i 层的最大结点数为：, i >= 1

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

2、二叉树的遍历

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

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

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

3、二叉查找树

        每个节点都有一个键值（key），左子树中的所有节点的键值都小于该节点的键值，右子树中的所有节点的键值都大于该节点的键值。

生成二叉树：

        生成跟节点键、左子树、右子树

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

插入节点

是否存在根节点值，若在就判断大小，进入左右子树继续判断节点值是否进入深一层。

 def insert(self, key):
        # 判断是否为空树，空的树直接将新添加的键作为根节点
        if self.root is None:
            self.root = TreeNode(key)
        else:
            return 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)
        else:
            raise Exception('key is in BST')

删除节点

1、若无左右子树，直接删除该节点；2、存在一个子树，就用该节点替代被删除节点；3、两个子树都存在，就将右子树中的最小值移动来替代被删除节点。

    def remove(self, key):
        self.root = self._remove(self.root, key)

    def _remove(self, node, key):
        # 如果节点为空，那么返回空值，也就是空节点不需要删除
        if node is None:
            return None

        # 判断指定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值大小相等；判断下一层节点情况
        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
            # 两个字子树都存在；查找当前节点的右子树的最小值
            else:
                temp = self._minvalue(node.right) 
                node.key = temp.key  # 赋值被删除节点为最小值节点
                node.right = self._remove(node.right, temp.key) #删除最小值节点
                return node
        return node

    def _minvalue(self, node):
        while node.left is not None:  遍历右子树中的所有左子树节点，返回最小值
            node = node.left
        return node

前序遍历

根、左子树、右子树

    def inorder_search_left(self):
        result = []
        self._inorder_search_left(self.root, result)
        return result

    def _inorder_search_left(self, node, result):
        if node:
            result.append(node.key)  # 先返回根节点
            self._inorder_search_left(node.left, result) # 返回左子树
            self._inorder_search_left(node.right, result) # 返回右子树

中序遍历

左子树、根、右子树 （前序顺序变化）

self._inorder_search_left(node.left, result) # 先返回左子树

result.append(node.key)  # 返回根节点
self._inorder_search_left(node.right, result) # 返回右子树

后序遍历

左子树、右子树、根 （前序顺序变化）

self._inorder_search_left(node.left, result) # 先返回左子树
self._inorder_search_left(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:
            return 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)
        else:
            raise Exception('key is in BST')

    def remove(self, key):
        self.root = self._remove(self.root, key)

    def _remove(self, node, key):
        # 如果节点为空，那么返回空值
        if node is None:
            return None

        # 判断指定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值大小相等；判断下一层节点情况
        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._minvalue(node.right)
                node.key = temp.key
                node.right = self._remove(node.right, temp.key)
                return node
        return node

    def _minvalue(self, node):
        while node.left is not None:
            node = node.left
        return node

    # 中序遍历：左子树、根节点、右子树
    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 inorder_search_left(self):
        result = []
        self._inorder_search_left(self.root, result)
        return result

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

    # 后序遍历 左子树、右子树、跟
    def inorder_search_right(self):
        result = []
        self._inorder_search_right(self.root, result)
        return result

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

if __name__ == '__main__':
    bst = BST()
    bst.insert(5)
    bst.insert(8)
    bst.insert(9)
    bst.insert(2)
    bst.insert(4)
    bst.insert(3)
    bst.insert(7)
    print(bst.inorder_search())  # [2, 3, 4, 5, 7, 8, 9]
    print(bst.inorder_search_left())  # [5, 2, 4, 3, 8, 7, 9]
    print(bst.inorder_search_right())  # [3, 4, 2, 7, 9, 8, 5]