数据结构基础

what’s the 数据结构

数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。 简单来说，数据结构就是设计数据以何种方式组织并存储在计算机中。比如：列表、集合与字典等都是一种数据结构。

通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

数据结构按照其逻辑结构可分为线性结构、树结构、图结构：

• 线性结构：数据结构中的元素存在一对一的相互关系
• 树结构：数据结构中的元素存在一对多的相互关系
• 图结构：数据结构中的元素存在多对多的相互关系

栈(Stack)

栈是一个数据集合，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。可以将栈理解为只能在一端进行插入或删除操作的列表。

栈的特点：后进先出、先进后出（类似于往箱子里放东西，要拿的时候只能拿最上面的，而最上面的是最后进的）

栈操作：进栈 push、出栈 pop、取栈顶 gettop

在 Python 中，不用自定义栈，直接用列表就行。进栈函数：append；出栈函数：pop；查看栈顶函数：li[-1]；

栈的应用

括号匹配问题：给一个字符串，其中包含小括号、中括号、大括号，求该字符串中的括号是否匹配。

基本思路：按顺序遍历字符串是左括号则进栈，来的是右括号则将栈顶左括号 pop，若来的右括号与栈顶左括号不匹配或空栈情况下来了右括号则返回错误信息

def brace_match(s):
    stack = []
    d = {'(':')', '[':']', '{':'}'}
    for ch in s:
        if ch in {'(', '[', '{'}:
            stack.append(ch)
        elif len(stack) == 0:
            print('多了右括号%s' % ch)
            return False
        elif d[stack[-1]] == ch:
            stack.pop()
        else:
            print('括号%s处不匹配' % ch)
            return False
    if len(stack) == 0:
        return True
    else:
        print("剩余左括号未匹配")
        return False
 
 
print(brace_match('[]{{}[]{()})}'))

用两个栈实现队列

class QueueStack(object):
    def __init__(self):
        self.l1 = []
        self.l2 = []
 
    def push(self,a):
        self.l1.append(a)
 
    def pop(self):
        if not self.l2:
            for i in range(len(self.l1)):
                a = self.l1.pop()
                self.l2.append(a)
        if self.l2:
            return self.l2.pop()
        else:
            return False

队列

队列(Queue)是一个数据集合，仅允许在列表的一端进行插入，另一端进行删除。

• 进行插入的一端称为队尾(rear)，插入动作称为进队或入队；
• 进行删除的一端称为队头(front)，删除动作称为出队。

和栈一样，队列是一种操作受限制的线性表。

队列的性质：先进先出（可以将队列理解为排队买东西）

特殊情况——双向队列：队列的两端都允许进行进队和出队操作。

如何用列表实现队列：

1. 初步设想：列表+两个下标指针
2. 创建一个列表和两个变量，front 变量指向队首，rear 变量指向队尾。初始时，front 和 rear 都为0。
3. 进队操作：元素写到 li[rear] 的位置，rear 自增1。
4. 出队操作：返回 li[front] 的元素，front 自减1。

以上就是队列实现的基本思路，但是队列出队之后，前面的空间被浪费了，所以实际情况中队列的实现原理是一个环形队列

环形队列：当队尾指针 front == Maxsize + 1 时，再前进一个位置就自动到0。

• 实现方式：求余数运算
• 队首指针前进1：front = (front + 1) % MaxSize
• 队尾指针前进1：rear = (rear + 1) % MaxSize
• 队空条件：rear == front
• 队满条件：(rear + 1) % MaxSize == front

在 Python 中，有一个内置模块可以帮我们快速建立起一个队列 deque 模块

• 使用方法：from collections import deque
• 创建队列：queue = deque(li)
• 进队：append()
• 出队：popleft()
• 双向队列队首进队：appendleft()
• 双向队列队尾进队：pop()

栈和队列的应用

求走出迷宫的路径

用栈解决迷宫问题

基本思路：在一个迷宫节点 (x,y) 上，可以进行四个方向的探查：maze[x-1][y]（表示上）， maze[x+1][y]（下）， maze[x][y-1]（左）， maze[x][y+1]（右）

思路：从一个节点开始，任意找下一个能走的点，当找不到能走的点时，退回上一个点寻找是否有其他方向的点

方法：创建一个空栈，首先将入口位置进栈。当栈不空时循环：获取栈顶元素，寻找下一个可走的相邻方块，如果找不到可走的相邻方块，说明当前位置是死胡同，进行回溯（就是讲当前位置出栈，看前面的点是否还有别的出路）

maze = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
    [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
 
dirs = [
    lambda x, y: (x - 1, y),  # 上
    lambda x, y: (x, y + 1),  # 右
    lambda x, y: (x + 1, y),  # 下
    lambda x, y: (x, y - 1),  # 左
]
 
 
def stack_solve_maze(x1, y1, x2, y2):
    """
    :param x1: 起点x坐标
    :param y1: 起点y坐标
    :param x2: 终点x坐标
    :param y2: 终点y坐标
    :return:
    """
    stack = []
    stack.append((x1,y1)) # 起点
    maze[x1][y1] = 2      # 2表示已经走过的点，我们要将已经走过的点进行标识，免得走重复的路
    while len(stack) > 0:        # 当栈不空循环
        cur_node = stack[-1]     # 栈顶，即目前所在位置
        if cur_node == (x2,y2):  # 到达终点
            for p in stack:
                print('==>',p,end='')  # 依次输出栈内坐标
            return True
        # 没到终点时，在任意位置都要试探上下左右是否走得通
        for dir in dirs:
            next_node = dir(*cur_node)
            if maze[next_node[0]][next_node[1]] == 0:   # 0是通道，说明找到一个能走的方向
                stack.append(next_node)
                maze[next_node[0]][next_node[1]] = 2    # 2表示已经走过的点
                break
        else: # 如果一个方向也找不到，说明到死胡同了
            stack.pop()
    else:
        print("无路可走")
        return False
 
 
stack_solve_maze(1,1,8,8)
# ==> (1, 1)==> (1, 2)==> (2, 2)==> (3, 2)==> (3, 1)==> (4, 1)==> (5, 1)==> (5, 2)==> (5, 3)==> (6, 3)==> (6, 4)==>(6, 5)==> (5, 5)==> (4, 5)==> (4, 6)==> (4, 7)==> (3, 7)==> (3, 8)==> (4, 8)==> (5, 8)==> (6, 8)==> (7, 8)==> (8, 8)

用队列解决迷宫问题

思路：从一个节点开始，寻找所有下面能继续走的点。继续寻找，直到找到出口。

方法：创建一个空队列，将起点位置进队。在队列不为空时循环：出队一次。如果当前位置为出口，则结束算法；否则找出当前方块的4个相邻方块中可走的方块，全部进队。

from collections import deque
 
maze = [
    [1,1,1,1,1,1,1,1,1,1],
    [1,0,0,1,0,0,0,1,0,1],
    [1,0,0,1,0,0,0,1,0,1],
    [1,0,0,0,0,1,1,0,0,1],
    [1,0,1,1,1,0,0,0,0,1],
    [1,0,0,0,1,0,0,0,0,1],
    [1,0,1,0,0,0,1,0,0,1],
    [1,0,1,1,1,0,1,1,0,1],
    [1,1,0,0,0,0,0,0,0,1],
    [1,1,1,1,1,1,1,1,1,1]
]
 
dirs = [
    lambda x,y:(x-1,y),  #上
    lambda x,y:(x,y+1),  #右
    lambda x,y:(x+1,y),  #下
    lambda x,y:(x,y-1),  #左
]
 
 
def deque_solve_maze(x1,y1,x2,y2):
    queue = deque()# 创建队列
    path = []      # 记录出队之后的节点
    queue.append((x1,y1,-1))
    maze[x1][y1] = 2  # 2表示应经走过的点
    while len(queue) > 0:
        cur_node = queue.popleft()
        path.append(cur_node)
        if cur_node[0] == x2 and cur_node[1] == y2:  # 到终点
            real_path = []
            x,y,i = path[-1]
            real_path.append((x,y))  # 将终点坐标append到real_path中
            while i >= 0:
                node = path[i]  # node是一个元祖（x坐标，y坐标，该点的leader）
                real_path.append(node[0:2])  # 只要坐标
                i = node[2]
            real_path.reverse() # 反转后顺序才为从起点到终点
            for p in real_path:
                print('==>',p,end='')
            return True
        for dir in dirs:
            next_node = dir(cur_node[0], cur_node[1])
            if maze[next_node[0]][next_node[1]] == 0:
                queue.append((next_node[0], next_node[1], len(path)-1))
                maze[next_node[0]][next_node[1]] = 2  # 标记为已经走过
    else:
        print("无路可走")
        return False

总结：

• 队列解决迷宫问题找到的出路肯定是最短路径，但是相对而言用队列会比较占用内存
• 队列对应的思想是广度优先，栈对应的是深度优先

链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。

每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到 O(1) 的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n) 的时间，而线性表和顺序表相应的时间复杂度分别是 O(logn) 和 O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。

链表有很多种不同的类型：单向链表，双向链表以及循环链表。链表可以在多种编程语言中实现。像 Lisp 和 Scheme 这样的语言的内建数据类型中就包含了链表的存取和操作。程序语言或面向对象语言，如 C、C++ 和 Java 依靠易变工具来生成链表。

链表中每一个元素都是一个对象，每个对象称为一个节点，包含有数据域 key 和指向下一个节点的指针 next。通过各个节点之间的相互连接，最终串联成一个链表。

# 结点的定义，单向
class Node(object):
    def __init__(self, item):
        self.item = item
        self.next = None

建立链表的方式有头插法和尾插法两种

• 头插法：在一个结点的前面插入元素，head 的指针由指向原来的结点变为指向新元素，新元素的指针指向原来的结点
• 尾插法：在一个元素后面插入一个元素，原来结点的指针指向新元素

建立列表实现代码如下：

# a = Node(1) # 头结点,是节点
# b = Node(2)
# c = Node(3)
# a.next = b
# b.next = c
# head = a
 
# 带空头结点的链表
# head = Node() # 头结点
# a = Node(1)
# b = Node(2)
# c = Node(3)
# head.next = a
# a.next = b
# b.next = c
# print(a.next.data)
 
 
class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None
 
class LinkList:
    def __init__(self, li, method='tail'):
        self.head = None
        self.tail = None
        if method == 'tail':
            self.create_linklist_tail(li)
        elif method == 'head':
            self.create_linklist_head(li)
        else:
            raise ValueError("Unsupport value %s" % method)
 
    def create_linklist_head(self, li):
        self.head = Node(0)
        for v in li:
            n = Node(v)
            n.next = self.head.next
            self.head.next = n
            self.head.data += 1
 
    def create_linklist_tail(self, li):
        self.head = Node(0)
        self.tail = self.head
        for v in li:
            p = Node(v)
            self.tail.next = p
            self.tail = p
            self.head.data += 1
 
    def traverse(self):
        p = self.head.next
        while p:
            yield p.data
            p = p.next
 
    def __len__(self):
        return self.head.data
 
 
ll = LinkList([1, 2, 3, 4, 5], method='tail')
print(len(ll))

链表结点的插入

链表插入结点的操作的重点是指针的变换，首先我们有两个结点 A 指向 B，这时要在 AB 中间插入 C，我们需要将 C 的指针指向 B，然后将 A 的指针指向 C，在删除 AB 之间的指针，就完成了 C 的插入，由 AB 变为了 ACB

# curNode为A结点
c.next = curNode.next
curNode.next = c

链表结点的删除

在链表中，要删除一个结点不能直接删掉就万事大吉，我们需要将指向该结点的结点的指针指向该结点指针指向的结点（A 指向 B 指向 C，B 为要删除的该结点，将 A 的指针指向 C），然后才能删除该节点B

# p为要删除的结点
curNode.next = curNode.next.next  # 即 p.next
del p

链表的特殊形态——双链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继（后面结点）和直接前驱（前面结点）。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

双向链表的节点定义

class Node(object):
    def __init__(self, item=None):
        self.item = item
        self.next = None
        self.prior = None

双向链表结点的插入

与链表相同，双向链表插入结点也需要将指针进行变换。同样是 AB 之间要插入 C，我们需要先将 C 的指针指向 B、B 的指针由指向 A 转变为指向 B，然后 C 的另一个指针指向 A，A 结点的指针由指向 B 转变为指向 B。

# p为新插入的元素
p.next = curNode.next
curNode.next.prior = p
p.prior = curNode
curNode.next = p

双向链表结点的删除

删除双向链表的结点前需要建立起该结点前后两个结点的指针关系，然后才能删除结点

# p 为要删除的结点
p = curNode.next
curNode.next = p.next
p.next.prior = curNode
del p

链表的复杂度分析

• 按元素值查找 O(n)，因为没有下标所以没法做二分
• 按下标查找 O(n)，因为没有下标
• 在某元素后插入 O(1)
• 删除某元素 O(1)

总结

• 链表在插入和删除的操作上明显快于顺序表
• 链表的内存可以更灵活的分配。试利用链表重新实现栈和队列
• 链表这种链式存储的数据结构对树和图的结构有很大的启发性

链表的题

检查给定的链表是否包含循环，包含循环返回1，不包含循环则返回0。同时说明所实现的时间和空间复杂度是多少。

# 快慢指针法：一个指针每次移动一个单位，一个指针每次移动两个单位，如果重合，说明有环
def find_loop(list):
    p1 = p2 = list
    while p2 and p2.next:
        p1 = p1.next
        p2 = p2.next.next
        if p1 == p2:
            return 1
    return 0
# 时间复杂度O(n), 空间复杂度O(1).

哈希表

哈希表的简单概述

哈希表一个通过哈希函数来计算数据存储位置的数据结构，通常支持如下操作 (高效的操作)：Python 中的字典是通过哈希表实现的

• insert(key, value)：插入键值对(key,value)
• get(key)：如果存在键为 key 的键值对则返回其 value，否则返回空值
• delete(key)：删除键为 key 的键值对

直接寻址表

当关键字的 key 的全域U(关键字可能出现的范围)比较小时，直接寻址是一种简单而有效的方法

• 存储：如上图将数组的下标作为 key，将数值存储在对应的下表位置，key 为 k 的元素放到 k 位置上
• 删除：当要删除某个元素时，将对应的下标的位置值置为空

直接寻址技术缺点：

• 当域U 很大时，需要消耗大量内存，很不实际
• 如果域U 很大而实际出现的 key 很少，则大量空间被浪费
• 无法处理关键字不是数字的情况，因为 key 可以是其他的数据类型

哈希与哈希表

改进直接寻址表:哈希

• 构建大小为 m 的寻址表 T
• key 为 k 的元素放到 h(k)位置上
• h(k) 是一个函数，其将域 U 映射到表T [0,1,...,m-1]

哈希表

• 哈希表（Hash Table，又称为散列表），是一种线性表的存储结构。哈希表由一个直接寻址表和一个哈希函数组成。
• 哈希函数 h(k) 将元素关键字 k 作为自变量，返回元素的存储下标。

简单的hash函数

• 除法哈希：h(k) = k mod m
• 乘法哈希：h(k) = floor(m(kA mod 1)) 0<A<1

存储机制

以除法哈希为例讨论下存储机制以及存在的问题

假设有一个长度为 7 的数组，哈希函数 h(k)=k mod 7，元素集合 {14,22,3,5} 的存储方式如下图。

解释:

• 存储: key 对数组长度取余，余数作为数组的下标，将值存储在此处
• 存在的问题 :比如：h(k)=k mod 7, h(0)=h(7)=h(14)=...

哈希冲突

由于哈希表的大小是有限的，而要存储的值的总数量是无限的，因此对于任何哈希函数，都会出现两个不同元素映射到同一个位置上的情况，这种情况叫做哈希冲突。

比如上图中的哈希表就存在这哈希冲突 h(k)=k%7, h(0)=h(7)=h(14)=...

解决哈希冲突方法

方法一：开放寻址法。如果哈希函数返回的位置已经有值，则可以向后探查新的位置来存储这个值。

• 线性探查：如果位置 i 被占用，则探查 i+1, i+2,……
• 二次探查：如果位置 i 被占用，则探查 i+12,i-12,i+22,i-22,……
• 二度哈希：有 n 个哈希函数，当使用第 1 个哈希函数 h1 发生冲突时，则尝试使用 h2,h3,……

方法二：拉链法。哈希表每个位置都连接一个链表，当冲突发生时，冲突的元素将被加到该位置链表的最后。

哈希表在 Python 中的应用

字典与集合都是通过哈希表来实现的。

Python 中的字典：a = {'name': 'Damon', 'age': 18, 'gender': 'Man'} 使用哈希表存储字典，通过哈希函数将字典的键映射为下标。假设h("name") = 3, h("age") = 1, h("gender") = 4，则哈希表存储为 [None, 18, None, "Damon", "Man"]

在字典键值对数量不多的情况下，几乎不会发生哈希冲突，此时查找一个元素的时间复杂度为 O(1)。

二叉树

树

在了解二叉树之前，首先我们得有树的概念。

树是一种数据结构又可称为树状图，如文档的目录、HTML 的文档树都是树结构，它是由 n（n>=1） 个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

• 每个节点有零个或多个子节点；
• 没有父节点的节点称为根节点；
• 每一个非根节点有且只有一个父节点；
• 除了根节点外，每个子节点可以分为多个不相交的子树；

有关树的一些相关术语：

• 节点的度：一个节点含有的子树的个数称为该节点的度；
• 叶节点或终端节点：度为0的节点称为叶节点；
• 非终端节点或分支节点：度不为0的节点；
• 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
• 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
• 兄弟节点：具有相同父节点的节点互称为兄弟节点；
• 树的度：一棵树中，最大的节点的度称为树的度；
• 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
• 树的高度或深度：树中节点的最大层次；
• 堂兄弟节点：双亲在同一层的节点互为堂兄弟；
• 节点的祖先：从根到该节点所经分支上的所有节点；
• 森林：由 m（m>=0） 棵互不相交的树的集合称为森林；

树的种类有：无序树、有序树、二叉树、霍夫曼树。其中最重要应用最多的就是二叉树，下面我们来学习有关二叉树的知识。

二叉树

二叉树的定义为度不超过 2 的树，即每个节点最多有两个叉（两个分支）。上面那个例图其实就是一颗二叉树。

二叉树是每个节点最多有两个子树的树结构。通常子树被称作 左子树（left subtree）和 右子树（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

二叉树的每个结点至多只有二棵子树(不存在度大于 2 的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第 i 层至多有 $2^{i−1}$ 个结点；深度为 k 的二叉树至多有 $2^{k}−1$个结点；对任何一棵二叉树T，如果其终端结点数为 $n_{0}$，度为 2 的结点数为 $n_{2}$，则 $n_{0}=n_{2}+1$。

二叉树的存储方式分为链式存储和顺序存储（类似列表）两种

二叉树父节点下标i和左孩子节点的编号下标的关系为2i+1，和右孩子节点的编号下标的关系为2i+2

二叉树有两个特殊的形态：满二叉树和完全二叉树

满二叉树：一个二叉树，如果除了叶子节点外每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。一棵深度为 k 的满二叉树有 $2^{k}−1$ 个节点

完全二叉树：除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点。具有 n 个节点的完全二叉树的深度为 log2n+1。深度为 k 的完全二叉树，至少有 $2^{k−1}$ 个节点，至多有 $2^{k}−1$ 个节点。

完全二叉树是效率很高的数据结构

二叉树的链式存储：将二叉树的节点定义为一个对象，节点之间通过类似链表的链接方式来连接。

二叉树结点的定义

class BiTreeNode:
    def __init__(self, data):
        self.data = data
        self.lchild = None
        self.rchild = None

二叉树的遍历分为四种：前序遍历、中序遍历、后序遍历和层级遍历

前序+中序 或者 后序+中序 可以唯一确定一颗子树（两个节点除外）

设树结构为：

• 前序遍历：先打印根，再递归其左子树，后递归其右子数 E ACBD GF
• 中序遍历：以根为中心，先打印左子树，然后打印根，然后打印右子树（注意，每个子树也有相应的根和子树）A BCD E GF
• 后序遍历：先递归左子树，再递归右子树，后打印根（注意，每个子树也有相应的根和子树 BDC A FG E
• 层次遍历：从根开始一层一层来，同一层的从左到右输出 E AG CF BD

四种遍历方法的代码实现：

# 结点的定义
class BiTreeNode:
    def __init__(self, data):
        self.data = data
        self.lchild = None
        self.rchild = None
# 二叉树结点
a = BiTreeNode('A')
b = BiTreeNode('B')
c = BiTreeNode('C')
d = BiTreeNode('D')
e = BiTreeNode('E')
f = BiTreeNode('F')
g = BiTreeNode('G')
# 结点之间的关系
e.lchild = a
e.rchild = g
a.rchild = c
c.lchild = b
c.rchild = d
g.rchild = f
 
root = e
 
# 前序遍历：先打印根，再递归左孩子，后递归右孩子
def pre_order(root):
    if root:
        print(root.data, end='')
        pre_order(root.lchild)
        pre_order(root.rchild)
 
# 中序遍历：以根为中心，左边打印左子树，右边打印右子树（注意，每个子树也有相应的根和子树）
# (ACBD) E (GF)-->(A(CBD)) E (GF)-->(A (B C D)) E (G F)
def in_order(root):
    if root:
        in_order(root.lchild)
        print(root.data, end='')
        in_order(root.rchild)
 
# 后序遍历：先递归左子树，再递归右子数，后打印根（注意，每个子树也有相应的根和子树）
# (ABCD)(GF)E-->((BCD)A)(GF)E-->(BDCA)(FG)E
def post_order(root):
    if root:
        post_order(root.lchild)
        post_order(root.rchild)
        print(root.data, end='')
 
# 层次遍历：一层一层来，同一层的从左到右输出
def level_order(root):
    queue = deque()
    queue.append(root)
    while len(queue) > 0:
        node = queue.popleft()
        print(node.data,end='')
        if node.lchild:
            queue.append(node.lchild)
        if node.rchild:
            queue.append(node.rchild)
 
pre_order(root)     # EACBDGF
print("")
in_order(root)      # ABCDEGF
print("")
post_order(root)    # BDCAFGE
print("")
level_order(root)   # EAGCFBD

二叉搜索树

二叉搜索树（Binary Search Tree），它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉搜索树。

二叉搜索树的中序遍历得到的是原来列表按升序排序的列表

由列表生成二叉搜索树、通过二叉搜索树查询值

# 结点定义
class BiTreeNode:
    def __init__(self, data):
        self.data = data
        self.lchild = None
        self.rchild = None


# 建立二叉搜索树（循环列表，插入值）
class BST:
    def __init__(self, li=None):
        self.root = None
        if li:
            self.root = self.insert(self.root, li[0]) # 列表的第一个元素是根
            for val in li[1:]:
                self.insert(self.root, val)
    # 生成二叉搜索树递归版本
    def insert(self, root, val):
        if root is None:
            root = BiTreeNode(val)
        elif val < root.data: # 插入的值小于root，要放到左子树中（递归查询插入的位置）
            root.lchild = self.insert(root.lchild, val)
        else:                 # 插入的值大于root，要放到右子树中（递归查询插入的位置）
            root.rchild = self.insert(root.rchild, val)
        return root
    # 生成二叉搜索树不递归的版本
    def insert_no_rec(self, val):
        p = self.root
        if not p:
            self.root = BiTreeNode(val)
            return
        while True:
            if val < p.data:
                if p.lchild:
                    p = p.lchild
                else:
                    p.lchild = BiTreeNode(val)
                    break
            else:
                if p.rchild:
                    p = p.rchild
                else:
                    p.rchild = BiTreeNode(val)
                    break
    # 查询递归版本
    def query(self, root, val):
        if not root:
            return False
        if root.data == val:
            return True
        elif root.data > val:
            return self.query(root.lchild, val)
        else:
            return self.query(root.rchild, val)
    # 查询非递归版本
    def query_no_rec(self, val):
        p = self.root
        while p:
            if p.data == val:
                return True
            elif p.data > val:
                p = p.lchild
            else:
                p = p.rchild
        return False
 
    # 中序遍历，得到的是升序的列表
    def in_order(self, root):
        if root:
            self.in_order(root.lchild)
            print(root.data, end=',')
            self.in_order(root.rchild)
 
 
tree = BST()
for i in [1,5,9,8,7,6,4,3,2]:
    tree.insert_no_rec(i)
tree.in_order(tree.root)
print(tree.query_no_rec(12))

删除操作

1. 如果要删除的节点是叶子节点：直接删除
2. 如果要删除的节点只有一个孩子：将此节点的父亲与孩子连接，然后删除该节点。
3. 如果要删除的节点有两个孩子：将其右子树的最小节点（该节点最多有一个右孩子）删除，并替换当前节点。

二叉搜索树效率：

• 平均情况下，二叉搜索树进行搜索的时间复杂度为 O(nlogn)。
• 最坏情况下，二叉搜索树可能非常偏斜。
• 解决方案：随机化插入，AVL树

二叉搜索树的应用——AVL树、B树、B+树

AVL 树

AVL 树：AVL 树是一棵自平衡的二叉搜索树。

AVL 树具有以下性质：根的左右子树的高度之差的绝对值不能超过 1，根的左右子树都是平衡二叉树

插入一个节点可能会破坏 AVL 树的平衡，可以通过 旋转 操作来进行修正。

插入一个节点后，只有从插入节点到根节点的路径上的节点的平衡可能被改变。我们需要找出第一个破坏了平衡条件的节点，称之为K。K的两颗子树的高度差2。

不平衡的出现可能有4种情况

1. 不平衡是由于对K的右孩子的右子树插入导致的：左旋

   

2. 不平衡是由于对K的左孩子的左子树插入导致的：右旋

   

3. 不平衡是由于对K的右孩子的左子树插入导致的：右旋-左旋

   

4. 不平衡是由于对K的左孩子的右子树插入导致的：左旋-右旋

   

B树

B树是一棵自平衡的多路搜索树。常用于数据库的索引。

B+树

B+树是一种树数据结构，是一个 n 叉排序树，每个节点通常有多个孩子，一棵 B+ 树包含根节点、内部节点和叶子节点。根节点可能是一个叶子节点，也可能是一个包含两个个或两个以上孩子节点的节点。

B+树通常用于数据库和操作系统的文件系统中。NTFS, ReiserFS, NSS, XFS, JFS, ReFS 和 BFS 等文件系统都在使用B+树作为元数据索引。B+树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+树元素自底向上插入。

B+树是应文件系统所需而出的一种B树的变型树。B和B+树的区别在于，B+树的非叶子结点只包含导航信息，不包含实际的值，所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。

B+树的优点在于：

由于B+树在内部节点上不包含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。因此访问叶子节点上关联的数据也具有更好的缓存命中率。

B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。

但是B树也有优点，其优点在于，由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。

通常在B+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。