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