python实现的二叉树算法和kmp算法实例

主要是：前序遍历、中序遍历、后序遍历、层级遍历、非递归前序遍历、非递归中序遍历、非递归后序遍历

#!/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实现的二叉树算法和kmp算法实例。“日事日毕，日清日高”的OEC管理模式，其含义是全方位地对每个人、每一天所做的每件事进行控制和清理，做到“日清日毕，日清日高”，每天的工作每天完成，而且每天的工作质量都有一点儿（1%）的提高。（日事日毕，解决基础管理问题；日清日高，解决速度问题）。更多关于python实现的二叉树算法和kmp算法实例请关注haodaima.com其它相关文章！