广安 网站建设,杭州建设信用信息网,gooood谷德设计网官网,乐清市网论坛数据结构视频地址#xff1a;https://www.bilibili.com/video/BV1uA411N7c5
数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。简单来说#xff0c;数据结构就是设计数据以何种方式组织并存储在计算机中。
比如:列表、集合与字…数据结构视频地址https://www.bilibili.com/video/BV1uA411N7c5
数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。简单来说数据结构就是设计数据以何种方式组织并存储在计算机中。
比如:列表、集合与字典等都是一种数据结构。 N.Wirth: “程序 数据结构 算法” 数据结构按照其逻辑结构可以分为①线性结构②树结构③图结构。
线性结构数据结构中的元素存在 一对一 的相互关系树结构数据结构中的元素存在 一对多 的相互关系图结构数据结构中的元素存在 多对多 的相互关系
1. 列表/数组
列表其他语言成为数组是一种基本数据类型。
关于列表的问题
列表中的元素是如何存储的列表的基本操作按下标索引查找、插入元素、删除元素…这些操作的时间复杂度是多少 查找O(1)O(1)O(1)插入O(n)O(n)O(n)删除O(n)O(n)O(n)appendO(1)O(1)O(1)
扩展Python的列表是如何实现的
数组与列表有两点不同
数组元素类型相同数组长度固定
2. 栈stack
栈(Stack)是一个数据集合可以理解为只能在一端进行插入或删除操作的列表。
栈的特点先进后出后进先出LIFOLast-In, First-Out栈的概念栈顶、栈底栈的基本操作 进栈压栈push出栈pop取栈顶gettop
2.1 栈的实现
使用一般的列表结构(list)即可实现栈。
进栈: ls.append出栈: ls.pop取栈顶: ls[-1]
2.2 栈的基本实现代码
class Stack:def __init__(self):self.stack []def push(self, elem):self.stack.append(elem)def pop(self):if self.stack:return self.stack.pop()else:raise Empty Valuedef gettop(self):if self.stack:return self.stack[-1]else:return Noneif __name__ __main__:stack Stack()stack.push(1)stack.push(2)stack.push(3)print(stack.pop())print(stack.gettop())2.3 栈的应用 —— 括号匹配问题
括号匹配问题给一个字符串其中包含小括号、中括号和大括号求该字符串中的括号是否匹配。
例如
()()[]{} 匹配
([{()}]) 匹配
[]( 不匹配
[(]) 不匹配思路有左括号先放到栈中看下一个如果是右括号那么看和栈顶是否匹配如果匹配出栈。看完所有元素后如果栈是空栈那么说明是合法的如果不为空那么是非法的。
特殊情况如果直接来了一个右括号直接非法 代码
class Stack():def __init__(self):self.stack []def push(self, elem):self.stack.append(elem)def pop(self):if self.stack:return self.stack.pop()else:raise Empty Valuedef gettop(self):if self.stack:return self.stack[-1]else:raise Empty Valuedef is_empty(self):return len(self.stack) 0def brace_match(s):match_dict {): (,]: [,}: {}stack Stack()for char in s:if char in ([{:stack.push(char)elif char in )]}:if stack.is_empty():return Falseelif stack.gettop() match_dict[char]:stack.pop()else: # 不匹配return Falseelse:raise Illegal Value# 看一下栈里是否有元素if stack.is_empty():return Trueelse:return Falseif __name__ __main__:test_1 ()()[]{}test_2 ([{()}])test_3 [](test_4 [(])print(brace_match(test_1))print(brace_match(test_2))print(brace_match(test_3))print(brace_match(test_4))TrueTrueFalseFalse3. 队列(Queue)
队列Queue是一个数据集合仅允许在列表的一端进行插入另一端进行删除。 进行插入的一端称为队尾rear插入动作称为进队或入队进行删除的一端称为对头front删除动作称为出队队列的性质先进先出FIFOFirst-In, First-Out
3.1 队列的实现
队列是否能用列表简单实现为什么 列表不好实现出队3次以后再入队就没法入队了。但如果把这个队列的头和尾连起来这个问题就解决了
3.2 队列的实现方式 —— 环形队列 Q队满的时候为什么有一个位置是空的 A为了判断这个队是空队还是满队
空队列front rear满队列front rear 1
Qrear进队到11时怎么变为0 A使用% - rear rear % len(queue) - rear % 12
Q那么front呢 A也是一样的也是front % len(queue) 环形队列当队尾指针front MaxSize - 1时再前进一个位置就自动到0。
队首指针前进1front (front 1) % MaxSize队尾指针前进1rear (rear 1) % MaxSize队空条件rear front队满条件(rear 1) % MaxSize front MaxSize为队列的长度 3.3 队列的代码实现
class Queue:def __init__(self, size100):# 队列的长度需要固定self.size size # 队列的长度self.queue [0 for i in range(size)]self.rear 0 # 队尾进队self.front 0 # 队首出队# 入队def push(self, elem):if not self.is_filled():self.rear (self.rear 1) % self.sizeself.queue[self.rear] elem # 进队else:raise Filled Queue Error# 出队def pop(self):if not self.is_empty():self.front (self.front 1) % self.size# 这里不删除旧的元素了因为环形的有值后会覆盖它return self.queue[self.front]else:raise No Value Error# 判断队空def is_empty(self):if self.rear self.front:return Trueelse:return False# 判断队满def is_filled(self):if (self.rear 1) % self.size self.front:return Trueelse:return False# 获取队尾def getrear(self):return self.queue[self.rear]# 获取队首def getfront(self):return self.queue[(self.front 1) % 12]if __name__ __main__:q Queue(5)for i in range(4):q.push(i)print(q.is_filled())print(q.pop())print(q.is_empty())print(q.getfront())print(q.getrear())3.4 双向队列
双向队列的两端都支持进队和出队操作其基本操作如下
队首进队队首出队队尾进队队尾出队 3.5 Python队列内置模块
使用方法from collections import deque具体操作如下
创建队列queue deque()进队append()出队popleft()双向队列队首进队appendleft()双向队列队尾出队pop() 注意这里并不是import queue模块因为queue模块一般用在多线程、多进程中用来保持线程安全的。如果我们想要解题那么我们就使用from collections import deque deque: 全称dequeuede表示双向即双向队列 deque是从左到右队首和堆尾 一般情况下单向队列用的比较多 from collections import dequeq deque()# 单向队列
q.append(1) # 队尾进队
print(q.popleft()) # 队首出队
# print(q.popleft()) # IndexError: pop from an empty deque# 双向队列
q.appendleft(2) # 队首进队
print(q.pop())值得注意的是deque()在创建的时候是可以传入值的如下
from collections import deque# 不传入值
q1 deque()
q1.append(1)
q1.append((1, 2, 3))
q1.append([1, 2, 3])
print(q1) # deque([1, (1, 2, 3), [1, 2, 3]])
q1.popleft()
q1.popleft()
print(q1) # deque([[1, 2, 3]])# 传入值
q2 deque([1, 2, 3])
print(q2) # deque([1, 2, 3])
q2.append(4)
print(q2) # deque([1, 2, 3, 4])
q2.append([5, 6, 7]) # deque([1, 2, 3, 4, [5, 6, 7]])
print(q2)# 传入值和最大值
q3 deque([1, 2, 3], maxlen5)
print(q3) # deque([1, 2, 3], maxlen5)
q3.append(4)
q3.append(5)
print(q3) # deque([1, 2, 3, 4, 5], maxlen5)
q3.append(6)
print(q3) # deque([2, 3, 4, 5, 6], maxlen5) - 自动将1pop掉了3.6 使用deque实现Linux的tail命令
Linux的tail命令即在terminal中输出文本文件的后五行。
from collections import dequedef tail(n):with open(test.txt, r) as f:q deque(f, n)return qif __name__ __main__:# print(tail(5)) # deque([gdfsfdgh567u65g\n, dsfgfdgh456t24t\n, sdgfstg453rt234t2\n, gdfs344534y45\n, qqqfdu6574], maxlen5)for line in tail(5):print(line, end)gdfsfdgh567u65gdsfgfdgh456t24tsdgfstg453rt234t2gdfs344534y45qqqfdu65743.7 栈和队列的应用 —— 迷宫问题
给一个二维列表表示迷宫0表示通道1表示围墙。给出算法求一条走出迷宫的路径。 maze: 英[meɪz] 美[meɪz] n. 迷宫; 纷繁复杂的规则; 复杂难懂的细节; 迷宫图; vt. 使困惑; 使混乱; 迷失; 3.7.1 方法1栈 —— 深度优先搜索
回溯法思路从一个节点开始任意找下一个能走的点当找不到能走的点时退回上一个点寻找是否有其他方向的点。使用栈存储当前路径。
def maze_path(maze, x1, y1, x2, y2):# 创建栈stack []# 将起点放到栈中stack.append((x1, y1))# 定义四种寻找方式directions [lambda x, y: (x 1, y), # 上lambda x, y: (x - 1, y), # 下lambda x, y: (x, y - 1), # 左lambda x, y: (x, y 1), # 右]# 当栈不为空说明能继续找while len(stack) 0:# 设定当前节点curNode stack[-1]# 判断当前节点是否为终点if curNode[0] x2 and curNode[1] y2:print(Find Solution!)for path in stack:print(path, end-)return Trueelse: # 如果不是终点按照四个方向依次寻找for direction in directions:# 得到下一个节点nextNode direction(curNode[0], curNode[1])# 判断下一个节点是否为0if maze[nextNode[0]][nextNode[1]] 0: # 说明是下一个节点# 压栈stack.append(nextNode)# 进行标记以防止回退maze[nextNode[0]][nextNode[1]] 2# 已经找到下一个节点停止该节点的搜索breakelse: # 如果不是继续搜索下一个方向passelse: # 如果四个方向都没有找到下一个节点stack.pop()else: # 栈为空print(No Solution!)return Falseif __name__ __main__:maze [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1], # 1[1, 0, 0, 1, 0, 0, 0, 1, 0, 1], # 2[1, 0, 0, 1, 0, 0, 0, 1, 0, 1], # 3[1, 0, 0, 0, 0, 1, 1, 0, 0, 1], # 4[1, 0, 1, 1, 1, 0, 0, 0, 0, 1], # 5[1, 0, 0, 0, 1, 0, 0, 0, 0, 1], # 6[1, 0, 1, 0, 0, 0, 1, 0, 0, 1], # 7[1, 0, 1, 1, 1, 0, 1, 1, 0, 1], # 8[1, 1, 0, 0, 0, 0, 0, 0, 0, 1], # 9[1, 1, 1, 1, 1, 1, 1, 1, 1, 1], # 10]maze_path(maze, 1, 1, 8, 8)
Find Solution!
(1, 1)-(2, 1)-(3, 1)-(4, 1)-(5, 1)-(5, 2)-(5, 3)-(6, 3)-(6, 4)-(6, 5)-(7, 5)-(8, 5)-(8, 6)-(8, 7)-(8, 8)-3.7.2 方法2队列 —— 广度优先搜索
思路从一个节点开始寻找所有接下来能继续走的点继续不断寻找直到找到出口。 多种可能同时进行 使用队列存储当前正在考虑的节点。
from collections import dequedef print_path(path):curNode path[-1] # path的最后一个元素就是终点real_path [] # 存放真正的路径# 找到其他节点while curNode[2] ! -1:real_path.append((curNode[0], curNode[1]))curNode path[curNode[2]]else:real_path.append((curNode[0], curNode[1])) # 起点real_path.reverse()for node in real_path:print(node, end-)def maze_path_queue(maze, x1, y1, x2, y2):# 创建队列queue deque()# 存放起点queue.append((x1, y1, -1)) # x坐标y坐标哪个位置让它来的path [] # 存放出队的节点# 定义四种寻找方式directions [lambda x, y: (x 1, y), # 上lambda x, y: (x - 1, y), # 下lambda x, y: (x, y - 1), # 左lambda x, y: (x, y 1), # 右]while len(queue) 0:curNode queue.popleft() # 队首出栈path.append(curNode)# 判断curNode是否为终点if curNode[0] x2 and curNode[1] y2:print(Found Solution: )print_path(path)return True# 搜索四个方向for direction in directions:nextNode direction(curNode[0], curNode[1])# 判断nextNode是否能走通if maze[nextNode[0]][nextNode[1]] 0:# 能走进队并记录哪个节点带它来的queue.append((nextNode[0], nextNode[1], len(path) - 1))# 标记为已走过maze[nextNode[0]][nextNode[1]] 2else:print(No Solution)return Falseif __name__ __main__:maze [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1], # 1[1, 0, 0, 1, 0, 0, 0, 1, 0, 1], # 2[1, 0, 0, 1, 0, 0, 0, 1, 0, 1], # 3[1, 0, 0, 0, 0, 1, 1, 0, 0, 1], # 4[1, 0, 1, 1, 1, 0, 0, 0, 0, 1], # 5[1, 0, 0, 0, 1, 0, 0, 0, 0, 1], # 6[1, 0, 1, 0, 0, 0, 1, 0, 0, 1], # 7[1, 0, 1, 1, 1, 0, 1, 1, 0, 1], # 8[1, 1, 0, 0, 0, 0, 0, 0, 0, 1], # 9[1, 1, 1, 1, 1, 1, 1, 1, 1, 1], # 10]maze_path_queue(maze, 1, 1, 8, 8)
Found Solution:
(1, 1)-(2, 1)-(3, 1)-(4, 1)-(5, 1)-(5, 2)-(5, 3)-(6, 3)-(6, 4)-(6, 5)-(7, 5)-(8, 5)-(8, 6)-(8, 7)-(8, 8)-4. 链表Linked List
链表是由一系列节点组成的元素集合。每个节点包含两部分数据域item和指向下一个节点的指针next。通过节点之间的相互连接最终串联成一个链表。 class Node():def __init__(self, item):self.item itemself.next None定义链表
class Node:def __init__(self, item):self.item itemself.next Noneif __name__ __main__:# 创建节点a Node(1)b Node(2)c Node(3)# 将节点连起来a.next bb.next c# 通过a这个节点找到b和cprint(a.next.item) # 2print(a.next.next.item) # 34.1 链表的创建与遍历
上面创建链表的方式是手动的这样太慢了。创建链表的方式有头插法和尾插法。
头插法在head前面插入插入完毕后head指向新的头尾插法在tail后面插入插入完毕后tail指向新的尾
class Node():def __init__(self, item):self.item itemself.next Nonedef create_linkedlist_head(ls):# 新建头节点head Node(ls[0])for elem in ls[1:]:node Node(elem)node.next headhead nodereturn headdef create_linkedlist_tail(ls):head Node(ls[0])# 此时头节点和尾节点是同一指向tail headfor elem in ls[1:]:# 为不同元素创建节点node Node(elem)tail.next nodetail nodereturn headdef print_linklist(lk):while lk:print(lk.item, end, )lk lk.nextif __name__ __main__:lk_head create_linkedlist_head([1, 2, 3])print_linklist(lk_head) # 3, 2, 1,print()lk_tail create_linkedlist_tail([1, 2, 3, 4, 5])print_linklist(lk_tail) # 1, 2, 3, 4, 5,4.2 链表节点的插入
数组插入需要挪动再插入这样的时间复杂度比较高O(n)O(n)O(n)而对于一个链表而言先把需要插入的地方的链子解开插入后连起来就行了。 p.next curNode.next
curNode.next p4.3 链表节点的删除 p curNode.nextcurNode.next curNode.next.next # 写成curNode.next p.next也行
del p # 其实删不删都可以5. 双链表
双链表的每个节点有两个指针一个指向后一个节点另一个指向前一个节点。 class Node():def __init__(self, itemNone):self.item itemself.next Noneself.prior None5.1 双链表节点的插入 p.next curNode.next
curNode.next.prior p
p.prior curNode
curNode.next p5.2 双链表节点的删除 p curNode.next
curNode.next p.next
p.next.prior curNode
del p6. 链表 —— 复杂度分析
顺序表列表/数组与链表对比
Item顺序表链表按元素值查找O(n)O(n)O(n)O(n)O(n)O(n)按下标查找O(1)O(1)O(1)O(n)O(n)O(n)在某个元素后插入O(n)O(n)O(n)O(1)O(1)O(1)删除某个元素O(n)O(n)O(n)O(1)O(1)O(1)
链表在插入和删除的操作上明显快与顺序表链表的内存可以更灵活地分配 试利用链表重新实现栈和队列 链表这种链式存储的数据结构对树和图的结构有很大的启发性
7. 哈希表
哈希表是一个通过哈希函数来计算数存储位置的数据结构通常支持如下操作
insert(key, value): 插入键值对(key, value)get(key): 如果存在键为key的键值对则返回其value否则返回空值delete(key): 删除键为key的键值对 哈希表其实就是一个dict 7.1 直接寻址表
当关键字的全域 UUU 比较小时直接寻址是一种简单而有效的方法。 UUU是一个集合里面包含了所有可能出现的关键词 KKK是一个集合里面包含了所有实际出现的关键词 TTT是一个列表它和UUU一一对应 直接寻址技术的缺点
当域UUU很大时需要消耗大量内存很不实际如果域UUU很大而实际出现的key很少则大量空间被浪费无法处理关键字不是数字的情况 Q那我们应该怎么解决这些问题呢 A在直接寻址表上加一个哈希函数就形成了哈希表 7.2 哈希
直接寻址表key为k的元素放到k位置上
改进的直接寻址表哈希Hashing
构建大小为mmm的寻址表TTTkey为k的元素放到h(k)h(k)h(k)位置上h(k)h(k)h(k)是一个函数其将域UUU映射到表T[0,1,...,m−1]T[0, 1, ..., m-1]T[0,1,...,m−1]
7.3 哈希表
哈希表Hash Table又称为散列表是一种线性表的存储结构。哈希表由一个直接寻址表和一个哈希函数组成。哈希函数h(k)h(k)h(k)将元素关键字kkk作为自变量返回元素的存储下标。 假设有一个长度为7的哈希表哈希函数$h(k) k % 7 。元素集合。元素集合。元素集合{14, 22, 3, 5}$的存储方式如下图 元素集合{14,22,3,5}\{14, 22, 3, 5\}{14,22,3,5}是指key没有value h(k)k%7∈[0,6]h(k) k \% 7 \in [0, 6]h(k)k%7∈[0,6] Q: 如果有一个key0那么上面的表中key0已经有key了怎么办 A这么情况称为哈希冲突
7.4 哈希冲突
由于哈希表的大小是有限的而要存储的值的数量是无限的因此对于任何哈希函数而言都会出现两个不同元素映射到同一个位置上的情况这种情况叫做哈希冲突。
比如 h(k)k%7h(k) k \% 7h(k)k%7, h(0)h(7)h(14)...h(0) h(7) h(14) ...h(0)h(7)h(14)...
7.4.1 解决哈希冲突1 —— 开放寻址法
开放寻址法如果哈希函数返回的位置已经有值则可以向后探查新的位置来存储这个值。
线性探查如果位置 iii 被占用则探查 i1,i2,...i 1, i 2, ...i1,i2,...二次探查如果位置 iii 被占用则探查 i12,i−12,i21,i−22,...i 1^2, i - 1^2, i 2^1, i - 2^2, ...i12,i−12,i21,i−22,...二度哈希(Double Hash)有 nnn 个哈希函数当使用第1个哈希函数h1h_1h1发生冲突时则尝试使用h2,h3,...h_2, h_3, ...h2,h3,...
7.4.2 解决哈希冲突2 —— 拉链法
拉链法哈希表每个位置都连接一个链表当冲突发生时冲突的元素将被加到该位置链表的最后。 之前是每个位置存放一个元素现在不是元素而是链表 7.5 常见的哈希函数
除法哈希法 h(k)k%mh(k) k \% mh(k)k%m- lambda k: k % m 乘法哈希法 h(k)floor(m×(A×key%1))h(k) \rm{floor}(m\times (A \times \rm{key} \% 1))h(k)floor(m×(A×key%1))- lambda k: floor(m*(A*key%1))%1: 取小数部分 全域哈希法 ha,b(k)((a×keyb)%p)%mh_{a, b}(k) ((a\times \rm{key} b) \% p) \% mha,b(k)((a×keyb)%p)%m- lambda a, b, k: ((a * key b) % p) % ma,b1,2,...,p−1a, b 1, 2, ..., p-1a,b1,2,...,p−1
7.6哈希表的应用 —— 集合与字典
字典与集合都是通过哈希表来实现的。
a {name: Alex, age: 18, gender: Male}
使用哈希表存储字典通过哈希函数将字典的键映射为下标。假设 h(‘name’) 3, h(‘age’) 1, h(‘gender’) 4, 则哈希表存储为 [None, 18, None, ‘Alex’, ‘Man’]
如果发生哈希冲突则通过拉链法或开放寻址法解决。
7.7 哈希表的应用 —— MD5算法
MD5(Message-Digest Algorithm 5)曾经是密码学中常用的哈希函数可以把任意长度的数据映射为128位的哈希值其曾经包含如下特征
同样的消息其MD5值必定相同可以快速计算出给定消息的MD5值除非暴力的枚举所有可能的消息否则不可能从哈希值反推出消息本身两条消息之间即使只有微小的差别其对应的MD5值也应该是完全不同、完全不相关区的不能在有意义的时间内人工构造两个不同的消息使其具有相同的MD5值。 Message-Digest: 消息摘要 哈希只有加密没有解密 MD5值相同的两个文件但二者也有可能是不同的因为有哈希冲突的存在而且128位的哈希值是有限的虽然有限但是人工制造两个哈希值相同的不同文件基本上是不可能的 现在MD5已经被破解了不再安全了但仍然在大规模使用 7.7.1 应用举例 —— 文件的哈希值
算出文件的哈希值若两个文件的哈希值相同则可以认为这两个文件是相同的因此
用户可以利用它来验证下载的文件是否完整云存储服务商可以利用它来判断用户要上传的文件是否已经存在于服务器上从而实现秒传的功能同时也可以避免存储过多相同的文件副本
7.8 哈希表的应用 —— SHA-2算法
历史上MD5和SHA-1曾经是使用最为广泛的 Cryptographic Hash Function但是随着密码学的发展这两个哈希函数的安全性相继受到了各种挑战。因此现在安全性较重要的场合推荐使用SHA-2等新的、更安全的哈希函数。
SHA-2包含了一系列的哈希函数SHA-224SHA-256SHA-384SHA-512SHA-512/224SHA-512/256其对应的哈希长度分别为224,256,384或512位。SHA-2具有和MD5类似的性质参见MD5算法的特征。 SHA: Secure Hash Algorithm SHA-2目前还没有被破解因此更加安全 7.8.1 应用举例 —— SHA-2算法
在比特币Bitcoin系统中所有参与者需要共同解决如下问题对于一个给定的字符串U给定的目标哈希值H需要计算出一个字符串V使得UV的哈希值与H的差小于一个给定值D。此时只能通过暴力枚举V来猜测。
首先计算出结果的人可以获得一定奖金而某人首先计算成功的概率与其拥有的计算量成正比所以其获得奖金的期望值与其拥有的计算量成正比。
8. 树与二叉树
树是一种数据结构比如目录结构。树是一种可以递归定义的数据结构是由nnn个节点组成的集合
如果n0n0n0那这是一颗空树如果n0n 0n0那存在1个节点作为树的根节点其他节点可以分为mmm个集合每个集合本身又是一棵树。 8.1 一些概念
根节点A叶子节点没有孩子节点的节点到头了没有分叉了比如 B,C,P,Q,K,L,M,N树的深度高度最深的节点的度指定节点对应的分叉数E的度2树的度哪个节点分的叉最多那树的就是几 - max(节点的度)6孩子节点/父节点相对的概念子树EIJPQ是一颗以E为根节点的树
8.2 用树创建一个文件夹系统
# 树是由一堆节点构成所以节点是树的核心
class Node:def __init__(self, name, node_typedir):# 链式存储的方式self.name nameself.type node_type # dir or fileself.children []self.parent None # 指向父节点# 让Node可以被打印def __repr__(self):return self.nameclass FileSystemTree:def __init__(self):self.root Node(/) # 根节点: 这里仿照的是Linux系统的rootself.now self.root # 在哪个文件夹中def mkdir(self, name):# name必须以/结尾if name[-1] ! /:name /# 创建Nodenode Node(name)# 和现在的文件夹相连self.now.children.append(node)node.parent self.now# 展现当前目录下的所有目录def ls(self):print(self.now.children)# return self.now.children# change directory(只支持相对路径)def cd(self, name):if name in [.., ../]: # 返回上一级目录self.now self.now.parentreturn True# name必须以/结尾if name[-1] ! /:name /for child in self.now.children:if child.name name: # 如果有这个目录self.now child # 切换目录return Trueelse:raise ValueError(invalid directory)if __name__ __main__:n Node(hello)n2 Node(world)n.children.append(n2)n2.parent ntree FileSystemTree()tree.mkdir(var/)tree.mkdir(bin/)tree.mkdir(usr/)tree.ls() # [var/, bin/, usr/]tree.cd(bin/)tree.mkdir(python/)tree.ls() # [python/]tree.cd(../)tree.ls() # [var/, bin/, usr/]8.3 二叉树
二叉树的链式存储将二叉树的节点定义为一个对象节点之间通过类似链表的链接方式来连接。 8.3.1 节点定义
class BiTreeNode:def __init__(self, data):self.data dataself.lchild Noneself.rchild None二叉树的度是2 class BiTreeNode:def __init__(self, data):self.data dataself.lchild None # 左孩子节点self.rchild None # 右孩子节点if __name__ __main__:a BiTreeNode(A)b BiTreeNode(B)c BiTreeNode(C)d BiTreeNode(D)e BiTreeNode(E)f BiTreeNode(F)g BiTreeNode(G)e.lchild ae.rchild ga.rchild cc.lchild bc.rchild dg.lchild froot eprint(root.lchild.rchild.data) # C8.3.2 二叉树的遍历 二叉树的遍历方式
前序遍历EACBDGF —— 自己 - 左 - 右中序遍历ABCDEGF —— 左 - 自己 - 右后序遍历BDCAFGE —— 左 - 右 - 自己层次遍历EAGCFBD —— 每一层从左到右 前序、中序、后序都是指遍历自己的位置 给出三者的任意两者都可以推出这棵树 中序遍历后一定是升序的有序 from collections import dequeclass BiTreeNode:def __init__(self, data):self.data dataself.lchild None # 左孩子节点self.rchild None # 右孩子节点def pre_order(root):# 前序遍历: 自己 - 左 - 右if root: # 如果root不为空print(root.data, end ) # 自己pre_order(root.lchild) # 左pre_order(root.rchild) # 右def in_order(root):# 中序遍历: 左 - 自己 - 右if root:in_order(root.lchild)print(root.data, end )in_order(root.rchild)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)if __name__ __main__:a BiTreeNode(A)b BiTreeNode(B)c BiTreeNode(C)d BiTreeNode(D)e BiTreeNode(E)f BiTreeNode(F)g BiTreeNode(G)e.lchild ae.rchild ga.rchild cc.lchild bc.rchild dg.lchild froot eprint(root.lchild.rchild.data) # Cpre_order(root) # E A C B D G Fprint()in_order(root) # A B C D E F G print()post_order(root) # B D C A F G E print()level_order(root) # E A G C F B D8.4 二叉搜索树Binary Search Tree, BST 二叉搜索树是一颗二叉树且满足以下性质设 x 是二叉树的一个节点如果 y 是 x 左子树的任意一个节点那么 y.key ≤ x.key如果 y 是 x 右子树的一个节点那么 y.key ≥ x.key。 简单理解任意一个节点的左侧的值都比该节点小右边都比该节点大 二叉搜索树的操作
查询O(logn)O(\log^n)O(logn)插入O(logn)O(\log^n)O(logn)删除
import randomclass BiTreeNode:def __init__(self, data):self.data dataself.lchild Noneself.rchild Noneself.parent Noneclass BinarySearchTree:def __init__(self, lsNone):self.root None # 根节点if ls:for val in ls:self.insert_no_rec(val) # 非递归的方法更快# self.root self.insert(self.root, val) # 递归的方法def insert(self, node, val):node: 递归时遍历的所有节点val: 插入的值if node is None: # 如果node为空(写成 if not node也可以)node BiTreeNode(val) # node为空则需要创建一个节点elif val node.data: # 说明插入的值比遍历的节点小 - 左边node.lchild self.insert(node.lchild, val)node.lchild.parent nodeelif val node.data:node.rchild self.insert(node.rchild, val)node.rchild.parent nodeelse: # 相等的情况passreturn nodedef insert_no_rec(self, val):p self.rootif not p: # p是空的(空树的情况下)self.root BiTreeNode(val)returnwhile True:if val p.data:if p.lchild: # 左子树存在p p.lchildelse: # 左子树不存在p.lchild BiTreeNode(val)p.lchild.parent preturnelif val p.data:if p.rchild:p p.rchildelse:p.rchild BiTreeNode(val)p.rchild.parent preturnelse:returndef pre_order(self, root):if root:print(root.data, end )self.pre_order(root.lchild)self.pre_order(root.rchild)def in_order(self, root):if root:self.in_order(root.lchild)print(root.data, end )self.in_order(root.rchild)def post_order(self, root):if root:self.post_order(root.lchild)self.post_order(root.rchild)print(root.data, end )def query(self, node, val):递归版本需要nodeif not node: # 如果node为空递归的终止条件return Noneelif node.data val:return self.query(node.lchild, val)elif node.data val:return self.query(node.rchild, val)else:return nodedef query_no_rec(self, val):p self.rootwhile p:if p.data val:p p.lchildelif p.data val:p p.rchildelse:return pelse:return Noneif __name__ __main__:tree BinarySearchTree([4, 6, 7, 9, 2, 1, 3, 5, 8])tree.pre_order(tree.root) # 4 2 1 3 6 5 7 9 8print()tree.in_order(tree.root) # 1 2 3 4 5 6 7 8 9print()tree.post_order(tree.root) # 1 3 2 5 8 9 7 6 4print()ls list(range(500))random.shuffle(ls)tree BinarySearchTree(ls)tree.in_order(tree.root) # 0 1 2 3 4 5 ... 99 (排好序了)print()ls list(range(0, 500, 2))random.shuffle(ls)tree BinarySearchTree(ls)print(tree.query(tree.root, 4).data) # 4print(tree.query_no_rec(3)) # None8.4.1 二叉搜索树 —— 删除操作
如果要删除的节点是叶子节点直接删除 如果要删除的节点只有一个孩子将此节点的父亲与孩子连接然后删除该节点。 如果要删除的节点是根节点且这个根只有一个孩子节点那么直接更新根就行。 如果要删除的节点有两个孩子将其右子树的最小节点该节点最多有一个右孩子删除并替换当前节点。 在右子树中往左走到头就是最小节点 这部分的代码如下
min_node node.rchildwhile min_node.lchild: # 如果min_node有左孩子min_node min_node.lchild # 让左孩子替换min_node下面是整体的代码
import randomclass BiTreeNode:def __init__(self, data):self.data dataself.lchild Noneself.rchild Noneself.parent Noneclass BinarySearchTree:def __init__(self, lsNone):self.root None # 根节点if ls:for val in ls:self.insert_no_rec(val) # 非递归的方法更快# self.root self.insert(self.root, val) # 递归的方法def insert(self, node, val):node: 递归时遍历的所有节点val: 插入的值if node is None: # 如果node为空(写成 if not node也可以)node BiTreeNode(val) # node为空则需要创建一个节点elif val node.data: # 说明插入的值比遍历的节点小 - 左边node.lchild self.insert(node.lchild, val)node.lchild.parent nodeelif val node.data:node.rchild self.insert(node.rchild, val)node.rchild.parent nodeelse: # 相等的情况passreturn nodedef insert_no_rec(self, val):p self.rootif not p: # p是空的(空树的情况下)self.root BiTreeNode(val)returnwhile True:if val p.data:if p.lchild: # 左子树存在p p.lchildelse: # 左子树不存在p.lchild BiTreeNode(val)p.lchild.parent preturnelif val p.data:if p.rchild:p p.rchildelse:p.rchild BiTreeNode(val)p.rchild.parent preturnelse:returndef pre_order(self, root):if root:print(root.data, end )self.pre_order(root.lchild)self.pre_order(root.rchild)def in_order(self, root):if root:self.in_order(root.lchild)print(root.data, end )self.in_order(root.rchild)def post_order(self, root):if root:self.post_order(root.lchild)self.post_order(root.rchild)print(root.data, end )def query(self, node, val):递归版本需要nodeif not node: # 如果node为空递归的终止条件return Noneelif node.data val:return self.query(node.lchild, val)elif node.data val:return self.query(node.rchild, val)else:return nodedef query_no_rec(self, val):p self.rootwhile p:if p.data val:p p.lchildelif p.data val:p p.rchildelse:return pelse:return Nonedef __remove_node_1(self, node):# 情况1node是叶子结点没有孩子if not node.parent: # 如果节点的父节点为空那就是root节点self.root None # 删除根节点if node node.parent.lchild: # node是它父亲的左孩子node.parent.lchild None # 删除左孩子else: # 右孩子node.parent.rchild None # 删除右孩子def __remove_node_2_1(self, node):# 情况2-1node只有一个左孩子节点if not node.parent: # 根节点# 左孩子就是新的rootself.root node.lchildnode.lchild.parent Noneelif node node.parent.lchild: # 是左孩子node.parent.lchild node.lchildnode.lchild.parent node.parentelse: # 是右孩子node.parent.rchild node.lchild # node只有左孩子没有右孩子node.lchild.parent node.parentdef __remove_node_2_2(self, node):# 情况2-2node只有一个右孩子if not node.parent: # 是根节点self.root node.rchildelif node node.parent.lchild: # 是左孩子node.parent.lchild node.rchildnode.rchild.parent node.parentelse: # 是右孩子node.parent.rchild node.rchildnode.rchild.parent node.parentdef delete(self, val):if self.root: # 如果不是空树node self.query_no_rec(val) # 找到val对应的nodeif not node: # 如果val对应的node不存在raise ValueError(f数值{val}不存在!)if not node.lchild and not node.rchild: # node是叶子节点没有孩子self.__remove_node_1(node)elif not node.rchild: # 只有一个孩子只有左孩子- 2-1self.__remove_node_2_1(node)elif not node.lchild: # 只有一个右孩子 - 2-2self.__remove_node_2_2(node)else: # 两个孩子都有# 找右子树最小的节点min_node node.rchild# 一直找左孩子节点while min_node.lchild:min_node min_node.lchild# 直接替换即可node.data min_node.data# 删除min_node - 还需要判断if min_node.rchild: # 只有右孩子节点self.__remove_node_2_2(min_node)else: # 是叶子节点self.__remove_node_1(min_node)if __name__ __main__:tree BinarySearchTree([4, 6, 7, 9, 2, 1, 3, 5, 8])tree.pre_order(tree.root) # 4 2 1 3 6 5 7 9 8print()tree.in_order(tree.root) # 1 2 3 4 5 6 7 8 9print()tree.post_order(tree.root) # 1 3 2 5 8 9 7 6 4print()ls list(range(500))random.shuffle(ls)tree BinarySearchTree(ls)tree.in_order(tree.root) # 0 1 2 3 4 5 ... 99 (排好序了)print()ls list(range(0, 500, 2))random.shuffle(ls)tree BinarySearchTree(ls)print(tree.query(tree.root, 4).data) # 4print(tree.query_no_rec(3)) # Nonetree BinarySearchTree([1, 4, 2, 5, 3, 8, 6, 9, 7])tree.in_order(tree.root) # 1 2 3 4 5 6 7 8 9print()tree.delete(4)tree.delete(1)tree.delete(3)tree.delete(8)tree.in_order(tree.root) # 2 5 6 7 9二叉搜索树的效率
平均情况下二叉搜索树进行搜索的时间复杂度为 O(lgn)O(\lg^n)O(lgn)。 但是在最坏情况下二叉搜索树可能非常偏斜极端情况下退化到 O(n)O(n)O(n)。解决方案有
随机化插入AVL树
8.5 AVL树
AVL树AVL树是一棵自平衡的二叉搜索树。 AVL树具有以下性质
根的左右子树的高度差的绝对值不能超过1根的左右子树都是平衡二叉树 高度差针对每个节点的左右孩子数之差有孩子为1没孩子为0 balance factor平衡因子记录了左右子树的高度之差。对于10而言左0右1所以balance factor 0 - 1 -1 平衡二叉树简单理解为树的深度一致 8.6 AVL树 —— 插入
插入一个节点可能会破坏AVL树的平衡可以通过旋转操作来进行修正。
可视化VAL
插入一个节点后只有从插入节点到根节点的路径上的节点的平衡可能被改变。我们需要找出第一个破坏了平衡条件的节点称之为K。K的两棵子树的高度差为2。
不平衡的情况有4种。
8.6.1 左旋
不平衡是由于对K的右孩子的右子树插入导致的左旋。 8.6.2 右旋
不平衡是由于对K的左孩子的左子树插入导致的右旋。 8.6.3 右旋-左旋
不平衡是由于对K的右孩子的左子树插入导致的右旋-左旋。 8.6.4 左旋-右旋
不平衡是由于对K的左孩子的右子树插入导致的左旋-右旋。 左左右旋右右左旋左右左右右左右左
8.7 二叉搜索树扩展应用 —— B树
B树B-TreeB树是一棵自平衡的多路搜索树常用于数据库的索引。 比17和35小的走左边在范围内的走中间大的走右边。
文章转载自： http://www.morning.dighk.com.gov.cn.dighk.com http://www.morning.nktgj.cn.gov.cn.nktgj.cn http://www.morning.rtkgc.cn.gov.cn.rtkgc.cn http://www.morning.dqgbx.cn.gov.cn.dqgbx.cn http://www.morning.kbgzj.cn.gov.cn.kbgzj.cn http://www.morning.cspwj.cn.gov.cn.cspwj.cn http://www.morning.nqbpz.cn.gov.cn.nqbpz.cn http://www.morning.wbdm.cn.gov.cn.wbdm.cn http://www.morning.tbhf.cn.gov.cn.tbhf.cn http://www.morning.xylxm.cn.gov.cn.xylxm.cn http://www.morning.bdypl.cn.gov.cn.bdypl.cn http://www.morning.kfsfm.cn.gov.cn.kfsfm.cn http://www.morning.kbbmj.cn.gov.cn.kbbmj.cn http://www.morning.thzgd.cn.gov.cn.thzgd.cn http://www.morning.pjwml.cn.gov.cn.pjwml.cn http://www.morning.rttp.cn.gov.cn.rttp.cn http://www.morning.dybth.cn.gov.cn.dybth.cn http://www.morning.lcxzg.cn.gov.cn.lcxzg.cn http://www.morning.cflxx.cn.gov.cn.cflxx.cn http://www.morning.rbgqn.cn.gov.cn.rbgqn.cn http://www.morning.btypn.cn.gov.cn.btypn.cn http://www.morning.tqbyw.cn.gov.cn.tqbyw.cn http://www.morning.kdnbf.cn.gov.cn.kdnbf.cn http://www.morning.cnqdn.cn.gov.cn.cnqdn.cn http://www.morning.bysey.com.gov.cn.bysey.com http://www.morning.ylpwc.cn.gov.cn.ylpwc.cn http://www.morning.ljzqb.cn.gov.cn.ljzqb.cn http://www.morning.mfltz.cn.gov.cn.mfltz.cn http://www.morning.lkthj.cn.gov.cn.lkthj.cn http://www.morning.yrsg.cn.gov.cn.yrsg.cn http://www.morning.tzrmp.cn.gov.cn.tzrmp.cn http://www.morning.klcdt.cn.gov.cn.klcdt.cn http://www.morning.jmspy.cn.gov.cn.jmspy.cn http://www.morning.nsppc.cn.gov.cn.nsppc.cn http://www.morning.xqjz.cn.gov.cn.xqjz.cn http://www.morning.pqypt.cn.gov.cn.pqypt.cn http://www.morning.tqfnf.cn.gov.cn.tqfnf.cn http://www.morning.kjsft.cn.gov.cn.kjsft.cn http://www.morning.rlksq.cn.gov.cn.rlksq.cn http://www.morning.gidmag.com.gov.cn.gidmag.com http://www.morning.syqtt.cn.gov.cn.syqtt.cn http://www.morning.zfrs.cn.gov.cn.zfrs.cn http://www.morning.tnfyj.cn.gov.cn.tnfyj.cn http://www.morning.hmqmm.cn.gov.cn.hmqmm.cn http://www.morning.hkchp.cn.gov.cn.hkchp.cn http://www.morning.drgmr.cn.gov.cn.drgmr.cn http://www.morning.jwgmx.cn.gov.cn.jwgmx.cn http://www.morning.lpbrp.cn.gov.cn.lpbrp.cn http://www.morning.kwnnx.cn.gov.cn.kwnnx.cn http://www.morning.wdhlc.cn.gov.cn.wdhlc.cn http://www.morning.nba1on1.com.gov.cn.nba1on1.com http://www.morning.gcbhh.cn.gov.cn.gcbhh.cn http://www.morning.nlryq.cn.gov.cn.nlryq.cn http://www.morning.nxhjg.cn.gov.cn.nxhjg.cn http://www.morning.pzlcd.cn.gov.cn.pzlcd.cn http://www.morning.qlbmc.cn.gov.cn.qlbmc.cn http://www.morning.mrfjr.cn.gov.cn.mrfjr.cn http://www.morning.pqbkk.cn.gov.cn.pqbkk.cn http://www.morning.rkhhl.cn.gov.cn.rkhhl.cn http://www.morning.jpjpb.cn.gov.cn.jpjpb.cn http://www.morning.zrdhd.cn.gov.cn.zrdhd.cn http://www.morning.rqjxc.cn.gov.cn.rqjxc.cn http://www.morning.fnczn.cn.gov.cn.fnczn.cn http://www.morning.tmpsc.cn.gov.cn.tmpsc.cn http://www.morning.splcc.cn.gov.cn.splcc.cn http://www.morning.qyqmj.cn.gov.cn.qyqmj.cn http://www.morning.mrxqd.cn.gov.cn.mrxqd.cn http://www.morning.wtlyr.cn.gov.cn.wtlyr.cn http://www.morning.pnljy.cn.gov.cn.pnljy.cn http://www.morning.sbrjj.cn.gov.cn.sbrjj.cn http://www.morning.vehna.com.gov.cn.vehna.com http://www.morning.cjqqj.cn.gov.cn.cjqqj.cn http://www.morning.xqgh.cn.gov.cn.xqgh.cn http://www.morning.lrwsk.cn.gov.cn.lrwsk.cn http://www.morning.c7627.cn.gov.cn.c7627.cn http://www.morning.mnclk.cn.gov.cn.mnclk.cn http://www.morning.cwjsz.cn.gov.cn.cwjsz.cn http://www.morning.gbcnz.cn.gov.cn.gbcnz.cn http://www.morning.nwgkk.cn.gov.cn.nwgkk.cn http://www.morning.lpnb.cn.gov.cn.lpnb.cn
