主页
课程
在线编程
|
新建
Python3代码
海龟绘图代码
开源硬件代码
|
文件
下载至本地
编辑器
自动换行: 开
分享
查看分享页
| 文件名:
【H5】AVL树作业 (分享)
登录
注册
#uuid_share# 2ab430a7-276d-4893-85d0-38d92bc77a65 # # SESSDSA20课程上机作业 # 【H5】AVL树作业 # # 说明:为方便批改作业,请同学们在完成作业时注意并遵守下面规则: # (1)直接在本文件中指定部位编写代码 # (2)如果作业中对相关类有明确命名/参数/返回值要求的,请严格按照要求执行 # (3)有些习题会对代码的编写进行特殊限制,请注意这些限制并遵守 # (4)作业代码部分在4月29日18:00之前提交到PyLn编程学习系统,班级码见Canvas系统 # ---- 用AVL树实现字典类型 ---- # 用AVL树来实现字典类型,使得其put/get/in/del操作均达到对数性能 # 采用如下的类定义,至少实现下列的方法 # key至少支持整数、浮点数、字符串 # 请调用hash(key)来作为AVL树的节点key # 【注意】涉及到输出的__str__, keys, values这些方法的输出次序是AVL树中序遍历次序 # 也就是按照hash(key)来排序的,这个跟Python 3.7中的dict输出次序不一样。 # 请在此编写你的代码 class TreeNode: """ 二叉树节点 请自行完成节点内部的实现,并实现给出的接口 """ def __init__(self, key, val=None): # 初始化方法 pass def getLeft(self): # 获取左子树 (不存在时返回None) pass def getRight(self): # 获取右子树 (不存在时返回None) pass class mydict: """ 以AVL树作为内部实现的字典 """ def getRoot(self): # 返回内部的AVL树根 pass def __init__(self): # 创建一个空字典 pass def __setitem__(self, key, value): # 将key:value保存到字典 # md[key]=value pass def __getitem__(self, key): # 从字典中根据key获取value # v = md[key] # key在字典中不存在的话,请raise KeyError pass def __delitem__(self, key): # 删除字典中的key # del md[key] # key在字典中不存在的话,请raise KeyError pass def __len__(self): # 获取字典的长度 # l = len(md) pass def __contains__(self, key): # 判断字典中是否存在key # k in md pass def clear(self): # 清除字典 pass def __str__(self): # 输出字符串形式,参照内置dict类型,输出按照AVL树中序遍历次序 # 格式类似:{'name': 'sessdsa', 'hello': 'world'} pass __repr__ = __str__ def keys(self): # 返回所有的key,类型是列表,按照AVL树中序遍历次序 pass def values(self): # 返回所有的value,类型是列表,按照AVL树中序遍历次序 pass # 代码结束 #mydict=dict # 检验 print("========= AVL树实现字典 =========") md = mydict() md['hello'] = 'world' md['name'] = 'sessdsa' print(md) # {'name': 'sessdsa', 'hello': 'world'} for f in range(1000): md[f**0.5] = f for i in range(1000, 2000): md[i] = i**2 print(len(md)) # 2002 print(md[2.0]) # 4 print(md[1000]) # 1000000 print(md['hello']) # world print(20.0 in md) # True print(99 in md) # False del md['hello'] print('hello' in md) # False for i in range(1000, 2000): del md[i] print(len(md)) # 1001 for f in range(1000): del md[f**0.5] print(len(md)) # 1 print(md.keys()) # ['name'] print(md.values()) # ['sessdsa'] for a in md.keys(): print(md[a]) # sessdsa md.clear() print(md) # {}
运行代码
清除输出
©2019 版权所有 北京大学409创新实验室