python实现的二叉树算法和kmp算法实例
时间:2023-08-07 20:50:49
主要是:前序遍历、中序遍历、后序遍历、层级遍历、非递归前序遍历、非递归中序遍历、非递归后序遍历
#!/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
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Laravel中间件的使用详解
python 获取页面表格数据存放到csv中的方法
Python3使用TCP编写一个简易的文件下载器功能
![](https://img.aspxhome.com/file/2023/3/118303_0s.png)
Python实现的简单计算器功能详解
![](https://img.aspxhome.com/file/2023/1/64361_0s.jpg)
JavaScript深入理解作用域链与闭包详情
![](https://img.aspxhome.com/file/2023/8/135918_0s.webp)
python namedtuple函数的使用
asp网上购物车实例代码
Python多线程实现支付模拟请求过程解析
使用python实现一个简单ping pong服务器
![](https://img.aspxhome.com/file/2023/7/94027_0s.jpg)
详解Python对某地区二手房房价数据分析
![](https://img.aspxhome.com/file/2023/6/118766_0s.jpg)
微信小程序弹窗禁止页面滚动的实现代码
![](https://img.aspxhome.com/file/2023/2/56362_0s.gif)
纯CSS圆角框2-透明圆角化背景图片
![](https://img.aspxhome.com/file/UploadPic/200912/11/3-72s.png)
详解vue+vueRouter+webpack的简单实例
Javascript防止图片拉伸的自适应处理方法
![](https://img.aspxhome.com/file/2023/1/132561_0s.jpg)
一文详解Python定时任务触发
![](https://img.aspxhome.com/file/2023/7/99687_0s.png)
python求最大值,不使用内置函数的实现方法
jsp页面中获取servlet请求中的参数的办法详解
pandas 获取季度,月度,年度首尾日期的方法
详解python读写json文件
Python网络爬虫与信息提取(实例讲解)
![](https://img.aspxhome.com/file/2023/5/125155_0s.png)