主要是:前序遍历、中序遍历、后序遍历、层级遍历、非递归前序遍历、非递归中序遍历、非递归后序遍历
复制代码 代码如下:
#!/usr/bin/env python
#-*- coding:utf8 -*-
class TreeNode(object):
def __init__(self, data=None, left=None, right=None):
self.data = data
self.left = left
self.right = right
class Tree(object):
def __init__(self, root=None):
self.root = None
def makeTree(self, data, left, right):
self.root = TreeNode(data, left, right)
def is_empty(self):
"""是否为空 """
if self.root is None:
return True
return False
def preOrder(self, r):
"""前序遍历 """
if not r.is_empty():
print r.root.data
if r.root.left is not None:
r.preOrder(r.root.left)
if r.root.right is not None:
r.preOrder(r.root.right)
def inOrder(self, r):
"""中序遍历 """
if not r.is_empty():
if r.root.left is not None:
r.preOrder(r.root.left)
print r.root.data
if r.root.right is not None:
r.preOrder(r.root.right)
def postOrder(self, r):
"""后续遍历 """
if not r.is_empty():
if r.root.left is not None:
r.preOrder(r.root.left)
print r.root.data
if r.root.right is not None:
r.preOrder(r.root.right)
def levelOrder(self, r):
"""层级遍历 """
if not r.is_empty():
s = [r]
while len(s) > 0:
temp = s.pop(0) # 先弹出最先append到的点
if temp and temp.root is not None:
print temp.root.data
if temp.root.left is not None:
s.append(temp.root.left)
if self.root.right is not None:
s.append(temp.root.right)
def preOrder1(self, r):
"""非递归 前序遍历 """
stack = []
current = r
while len(stack) > 0 or (current and not current.is_empty()):
while current and not current.is_empty():
print current.root.data
stack.append(current)
current = current.root.left
if len(stack) > 0:
current = stack.pop()
current = current.root.right
def inOrder1(self, r):
"""非递归 中序遍历 """
stack = []
current = r
while len(stack) > 0 or (current and not current.is_empty()):
while current and not current.is_empty():
stack.append(current)
current = current.root.left
if len(stack) > 0:
current = stack.pop()
print current.root.data
current = current.root.right
def postOrder1(self, r):
"""非递归 后续遍历 """
stack = []
current = r
pre = None
while len(stack) > 0 or (current and not current.is_empty()):
if current and not current.is_empty():
stack.append(current)
current = current.root.left
elif stack[-1].root.right != pre:
current = stack[-1].root.right
pre = None
else:
pre = stack.pop()
print pre.root.data
def leaves_count(self, r):
"""求叶子节点个数 """
if r.is_empty():
return 0
elif (not r.root.left) and (not r.root.right):
return 1
else:
return r.root.left.leaves_count(r.root.left) + r.root.right.leaves_count(r.root.right)
if __name__ == '__main__':
"""二叉树"""
ra, rb, rc, rd, re, rf = Tree(), Tree(), Tree(), Tree(), Tree(), Tree()
ra.makeTree("a", None, None)
rb.makeTree("b", None, None)
rc.makeTree("c", None, None)
rd.makeTree("d", None, None)
re.makeTree("e", None, None)
rf.makeTree("f", None, None)
r1, r2, r3, r4, r = Tree(), Tree(), Tree(), Tree(), Tree()
r1.makeTree("-", rc, rd)
r2.makeTree("*", rb, r1)
r3.makeTree("+", ra, r2)
r4.makeTree("/", re, rf)
r.makeTree("-", r3, r4)
r.preOrder(r)
r.inOrder(r)
r.postOrder(r)
r.levelOrder(r)
print r.leaves_count(r)
大学的时候学过kmp算法,最近在看的时候发现竟然忘了,所以去重新看了看书,然后用python写下了这个算法:
复制代码 代码如下:
def kmp(text, pattern):
"""kmp算法 """
pattern = list(pattern)
next = [-1] * len(pattern)
#next 函数
i, j = 1, -1
for i in range(1, len(pattern)):
j = next[i - 1]
while True:
if pattern[i - 1] == pattern[j] or j == -1:
next[i] = j + 1
break
else:
j = next[j]
#循环比较
i, j = 0, 0
while i < len(text) and j < len(pattern):
if text[i] == pattern[j] or j == -1:
i += 1
j += 1
else:
j = next[j]
#返回结果 如果匹配,返回匹配的位置,否则返回-1
if j == len(pattern):
print i – j
else:
print -1
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
P70系列延期,华为新旗舰将在下月发布
3月20日消息,近期博主@数码闲聊站 透露,原定三月份发布的华为新旗舰P70系列延期发布,预计4月份上市。
而博主@定焦数码 爆料,华为的P70系列在定位上已经超过了Mate60,成为了重要的旗舰系列之一。它肩负着重返影像领域顶尖的使命。那么这次P70会带来哪些令人惊艳的创新呢?
根据目前爆料的消息来看,华为P70系列将推出三个版本,其中P70和P70 Pro采用了三角形的摄像头模组设计,而P70 Art则采用了与上一代P60 Art相似的不规则形状设计。这样的外观是否好看见仁见智,但辨识度绝对拉满。
更新日志
- 《原神》「星路拾忆」网页活动壁纸展示
- 群星.2024-祝你幸福!电影原声带【阿里巴巴】【FLAC分轨】
- 于台烟.2004-执着【乾坤唱片】【WAV+CUE】
- 黄品源.2004-感谢·情人(引进版)【滚石】【WAV+CUE】
- 《最终幻想16》评测:游、戏两难全的系列转折
- 《纸嫁衣》五部打包¥104,《鬼泣5》仅需¥44
- 《崩坏:星穹铁道》造物大赛卷出新高度
- 《王菲 菲常传奇 2CD》[WAV+CUE][950MB]
- 《王菲 空灵独味唱腔 非常传奇 紫水晶2CD》[WAV+CUE][860MB]
- 《车载专业测试王1号 极品音质》[WAV/分轨][980MB]
- 炉石传说的国服回归送什么奖励 炉石传说9.25回归最新消息介绍
- 云顶之弈最强阵容汇总2024 云顶之弈最强阵容搭配最新版本
- S14lol全球总决赛在哪观看 lol全球总决赛观赛直播地址汇总
- 黄思婷2011-感谢天[豪记唱片][WAV+CUE]
- 孙淑媚2013-太阳[台湾首版][WAV+CUE]