ホームページ > バックエンド開発 > Python チュートリアル > Pythonで実装された二分木アルゴリズムとkmpアルゴリズムの例

Pythonで実装された二分木アルゴリズムとkmpアルゴリズムの例

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB
リリース: 2016-06-16 08:44:23
オリジナル
1442 人が閲覧しました

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

复制代码 代码如下:

#!/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 , なし)
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 function
i, j = 1, -1
for i in range (1, len(pattern)):
j = next[i - 1]
while True:
if pattern[i - 1] == pattern[j] または j == -1:
next[i] = j + 1
Break
else:
j = next[j]
#ループ比較
i, j = 0, 0
while i < ; len(テキスト) および j
if text[i] == pattern[j] または j == -1:
i += 1
j += 1
else:
j = next[j ]
#Return result 一致した場合は一致した位置を返し、そうでない場合は -1
を返す if j == len(pattern):
print i – j
else:
print -1

関連ラベル:
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
最新の問題
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート