主要是:前序遍历、中序遍历、后序遍历、层级遍历、非递归前序遍历、非递归中序遍历、非递归后序遍历
复制代码 代码如下:
#!/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
- 上一篇:Python操作sqlite3快速、安全插入数据(防注入)的实例
- 下一篇:Python BeautifulSoup中文乱码问题的2种解决方法
相关文章
相关视频
- 在Django框架中运行Python应用全攻略
- 在Python的Django框架中创建和使用模版
- python获取元素在数组中索引号的方法
- 浅谈python中截取字符函数strip,lstr...
- python实现的二叉树算法和kmp算法实例
- Python 简介
- Python 环境搭建
- Python 中文编码
- Python 基础语法
- Python 变量类型
网友评论
文明上网理性发言,请遵守 新闻评论服务协议
我要评论
立即提交
专题推荐
- 独孤九贱-php全栈开发教程
全栈 100W+
主讲:Peter-Zhu 轻松幽默、简短易学,非常适合PHP学习入门
- 玉女心经-web前端开发教程
入门 50W+
主讲:灭绝师太 由浅入深、明快简洁,非常适合前端学习入门
- 天龙八部-实战开发教程
实战 80W+
主讲:西门大官人 思路清晰、严谨规范,适合有一定web编程基础学习
作者信息
php教程
认证0级讲师
- 最近文章
发布技术文章
- 最新文章
- 热门排行
- python之禅怎么打出来
- python怎么学
- boosting和bootstrap区别
- python库是什么意思
- python卸载后怎么也安装不上
- python安装后怎么不见了
- python怎么卸载模块
- python能做什么?是什么?
- pickle库的使用详解
- Anaconda的新手使用大全
- python爬虫是什么?为什么把python叫做爬虫?
- Python微信库:itchat的用法详解
- 关于python3学习基础知识总结
- python爬虫是什么
- 使用Python可以做什么
- python如何实现可视化热力图
推荐视频教程
视频教程分类
- php视频教程
- html视频教程
- css视频教程
- JS视频教程