首页 / 算法 / day12 数据结构+算法
day12 数据结构+算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了day12 数据结构+算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4844字，纯文字阅读大概需要7分钟。
内容图文
day12 数据结构+算法
二叉树
class Node():
def __init__(self,item):
self.item = item
self.left = None
self.right = None
class Tree():
def __init__(self):
self.root = None
def addNode(self,item):
node = Node(item)
if self.root == None:#如果树中没有节点,把第一个的节点给root
self.root = node
return
cur = self.root #不改变root节点.赋值
while 1 :
q = [cur] # 将节点加到列表中,然后在pop出来,左右为空,添加节点,不为空,添加到列表中继续判断
# 要赋值,否则每次都要pop,pop太多值了,一次.
# if q.pop(0).left == None :#如果左节点没有
# q.pop(0).left = node #给左节点赋值
# return #退出函数
# else:....
n = pop(0)
if n.left == None :#如果左节点没有
n.left = node #给左节点赋值
return #退出函数
else:
q.append(n.left)#如果左节点有,加到列表中判断
if n.right == None :
n.right = node
return
else:
q.append(n.right)
广度排序
前序 (根左右)
写出一个来,然后套到别的树
有序的深度排序
中序
class SortTree():
def __init__(self):
self.root = None
def midTravel(self,root):
if root = None
return
# 左根右
self.midTravel(root.left) # 递归, 循环直到return
print(root.item)
self.midTravel(root.right)
def insertNode(self,item):
node = Node(item)
cur = self.root
# 数为空
if self.root == None:
self.root = node
return
# 树为非空
while True:
if cur.left > node.item :
cur.left = node
break
else:
cur = cur.left
if cur.right > node.item :
cur.right = node
break
else:
cur = cur.right
单链表写出之后,双链表也可以,循环列表
排序二叉树
写出来,写树的高度,什么都可以了.
深度排序:
中序有用, 也没有排序, 自动排序
排序算法
二分查找
- 有序列表对于我们的实现搜索是很有用的。在顺序查找中，当我们与第一个元素进行比较时，如果第一个元素不是我们要查找的，则最多还有 n-1 个元素需要进行比较。 二分查找则是从中间元素开始，而不是按顺序查找列表。 如果该元素是我们正在寻找的元素，我们就完成了查找。 如果它不是，我们可以使用列表的有序性质来消除剩余元素的一半。如果我们正在查找的元素大于中间元素，就可以消除中间元素以及比中间元素小的一半元素。如果该元素在列表中，肯定在大的那半部分。然后我们可以用大的半部分重复该过程，继续从中间元素开始，将其与我们正在寻找的内容进行比较。
low = 0
high = len() -1
mid = (low+high)//2
while low <= high:
? if items[mid]>item : low = ...
? if < : high = ...
? else : find = T
return find
# 基于有序 减半 速度def search(alist,item):
find = False
low = 0
high = len(alist)-1
while low <= high:
mid = (low+high) // 2 #中心位置的元素下标（切割点）
if alist[mid] < item:
low = mid + 1
elif alist[mid] > item:
high = mid - 1
else:#alist[mid] == item
find = True
break
return find
alist = [1,2]
print(search(alist,22)) 冒泡排序
- 1.将原始列表中的最大值找出且放置在列表最右侧(将元素两两比较，将数值大的数逐步向后移动)
- 2.重复执行步骤1
#将原始列表中的最大值找出且放置在列表最右侧(将元素两两比较，将数值大的数逐步向后移动)
def sort(alist):
for i in range(len(alist)-1):
if alist[i] > alist[i+1]:
alist[i],alist[i+1] = alist[i+1],alist[i]
return alist
def sort(alist):
for j in range(len(alist)-1):
#交换
for i in range(len(alist)-1-j):
if alist[i] > alist[i+1]:
alist[i],alist[i+1] = alist[i+1],alist[i]
return alistalist = [3,6,1,4,8,2]
print(sort(alist))
----->[1, 2, 3, 4, 6, 8]
选择排序
将最大值一次找出, 放在列表最右
#将列表中的最大值的下标找到
def sort(alist):
max_index = 0 #最大值的下标
for i in range(1,len(alist)):
if alist[max_index] < alist[i]:
max_index = i
print(max_index)#将列表中的最大值一次找出，放置在列表最右侧
def sort(alist):
max_index = 0 #最大值的下标
for i in range(1,len(alist)):
if alist[max_index] < alist[i]:
max_index = i
alist[max_index],alist[len(alist)-1] = alist[len(alist)-1],alist[max_index]
return alistdef sort(alist):
for j in range(len(alist),1,-1):
max_index = 0 #最大值的下标
for i in range(1,j): #len(alist) == > j
if alist[max_index] < alist[i]:
max_index = i
alist[max_index],alist[j-1] = alist[j-1],alist[max_index]
return alistalist = [3,6,1,4,8,2]
sort(alist)
---->[1, 2, 3, 4, 6, 8]
相比来说,交换的次数少了, 在第一循环内部, 第二循环外部
排序二叉树
class SortTree():
def __init__(self):
self.root = None
def midTravel(self,root):
if root == None:
return
#左根右
self.midTravel(root.left)
print(root.item)
self.midTravel(root.right)
def insertNode(self,item):
node = Node(item)
cur = self.root
#树为空
if self.root == None:
self.root = node
return
#树为非空
while True:
if cur.item > node.item:
if cur.left == None:
cur.left = node
break
else:
cur = cur.left
else:
if cur.right == None:
cur.right = node
break
else:
cur = cur.right
t = SortTree()
t.insertNode(3)
t.insertNode(8)
t.insertNode(3)
t.insertNode(1)
t.insertNode(1)
t.midTravel(t.root)---->
1
1
3
3
8
快排
def sort(alist,start,end):
low = start
high = end
#结束递归的条件
if low > high:
return
mid = alist[low]
while low < high:
while low < high:
if alist[high] > mid:
high -= 1
else:
alist[low] = alist[high]
break
while low < high:
if alist[low] < mid:
low += 1
else:
alist[high] = alist[low]
break
# if low == high:
alist[low] = mid
sort(alist,low+1,end) #将基准右侧的子列表进行递归操作
sort(alist,start,high-1)
return alist内容总结
以上是互联网集市为您收集整理的day12 数据结构+算法全部内容，希望文章能够帮你解决day12 数据结构+算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】