ホームページ > バックエンド開発 > Python チュートリアル > バイナリ ツリー アルゴリズムの Python 実装例

バイナリ ツリー アルゴリズムの Python 実装例

不言
リリース: 2019-02-25 10:42:15
転載
3533 人が閲覧しました

この記事では、Python でバイナリ ツリーを実装するためのアルゴリズムの例をいくつか紹介します。一定の参考値があります。必要な友人は参照してください。お役に立てば幸いです。

ノード定義

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

class Node(object):

    def __init__(self, left_child, right_child, value):

        self._left_child = left_child

        self._right_child = right_child

        self._value = value

 

    @property

    def left_child(self):

        return self._left_child

 

    @property

    def right_child(self):

        return self._right_child

 

    @left_child.setter

    def left_child(self, value):

        self._left_child = value

 

    @right_child.setter

    def right_child(self, value):

        self._right_child = value

 

    @property

    def value(self):

        return self._value

 

    @value.setter

    def value(self, value):

        self._value = value

ログイン後にコピー

バイナリ ツリー定義

1

2

3

4

5

6

7

class Tree(object):

    def __init__(self, value):

        self._root = Node(None, None, value=value)

 

    @property

    def root(self):

        return self._root

ログイン後にコピー

プリオーダー トラバーサル

再帰的メソッド

1

2

3

4

5

6

7

8

9

10

11

12

13

'''

先序遍历,递归方式

'''

def preoder(root):

    if not isinstance(root, Node):

        return None

    preorder_res = []

    if root:

        preorder_res.append(root.value)

        preorder_res += preoder(root.left_child)

        preorder_res += preoder(root.right_child)

 

    return preorder_res

ログイン後にコピー

Non-再帰的メソッド

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

'''

先序遍历,非递归方式

'''

def pre_order_not_recursion(root):

    if not isinstance(root, Node):

        return None

 

    stack = [root]

    result = []

    while stack:

        node = stack.pop(-1)

        if node:

            result.append(node.value)

            stack.append(node.right_child)

            stack.append(node.left_child)

    return result

ログイン後にコピー

順序トラバーサル

再帰的メソッド

1

2

3

4

5

6

7

8

9

10

11

12

'''

中序遍历,递归方式

'''

def middle_order(root):

    if not isinstance(root, Node):

        return None

    middle_res = []

    if root:

        middle_res += middle_order(root.left_child)

        middle_res.append(root.value)

        middle_res += middle_order(root.right_child)

    return middle_res

ログイン後にコピー

非再帰的メソッド

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

'''

中序遍历,非递归方式

'''

def middle_order_bot_recursion(root):

    if not isinstance(root, Node):

        return None

 

    result = []

    stack = [root.right_child, root.value, root.left_child]

    while stack:

        temp = stack.pop(-1)

        if temp:

            if isinstance(temp, Node):

                stack.append(temp.right_child)

                stack.append(temp.value)

                stack.append(temp.left_child)

            else:

                result.append(temp)

    return result

ログイン後にコピー

後順トラバーサル

再帰的メソッド

1

2

3

4

5

6

7

8

9

10

11

12

'''

后序遍历,递归方式

'''

def post_order(root):

    if not isinstance(root, Node):

        return None

    post_res = []

    if root:

        post_res += post_order(root.left_child)

        post_res += post_order(root.right_child)

        post_res.append(root.value)

    return post_res

ログイン後にコピー

非再帰メソッド

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

'''

后序遍历,非递归方式

'''

def post_order_not_recursion(root):

    if not isinstance(root, Node):

        return None

 

    stack = [root.value, root.right_child, root.left_child]

    result = []

 

    while stack:

        temp_node = stack.pop(-1)

        if temp_node:

            if isinstance(temp_node, Node):

                stack.append(temp_node.value)

                stack.append(temp_node.right_child)

                stack.append(temp_node.left_child)

            else:

                result.append(temp_node)

 

    return result

ログイン後にコピー

階層トラバーサル

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

'''

分层遍历,使用队列实现

'''

def layer_order(root):

    if not isinstance(root, Node):

        return None

 

    queue = [root.value, root.left_child, root.right_child]

    result = []

    while queue:

        temp = queue.pop(0)

        if temp:

            if isinstance(temp, Node):

                queue.append(temp.value)

                queue.append(temp.left_child)

                queue.append(temp.right_child)

            else:

                result.append(temp)

 

    return result

ログイン後にコピー

二分木のノード数を計算する

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

'''

计算二叉树结点个数,递归方式

NodeCount(root) = NodeCount(root.left_child) + NodeCount(root.right_child)

'''

def node_count(root):

    if root and not isinstance(root, Node):

        return None

 

    if root:

        return node_count(root.left_child) + node_count(root.right_child) + 1

    else:

        return 0

 

 

'''

计算二叉树结点个数,非递归方式

借用分层遍历计算

'''

def node_count_not_recursion(root):

    if root and not isinstance(root, Node):

        return None

 

    return len(layer_order(root))

ログイン後にコピー

二分木の深さを計算する

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

'''

计算二叉树深度,递归方式

tree_deep(root) = 1 + max(tree_deep(root.left_child), tree_deep(root.right_child))

'''

def tree_deep(root):

    if root and not isinstance(root, Node):

        return None

 

    if root:

        return 1 + max(tree_deep(root.left_child), tree_deep(root.right_child))

    else:

        return 0

 

'''

计算二叉树深度,非递归方法

同理参考分层遍历的思想

'''

def tree_deep_not_recursion(root):

    if root and not isinstance(root, Node):

        return None

    result = 0

    queue = [(root, 1)]

    while queue:

        temp_node, temp_layer = queue.pop(0)

        if temp_node:

            queue.append((temp_node.left_child, temp_layer+1))

            queue.append((temp_node.right_child, temp_layer+1))

            result = temp_layer + 1

 

    return result-1

ログイン後にコピー

二分木のノード数を計算する k-レベルノードの数

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

'''

计算二叉树第k层节点个数,递归方式

kth_node_count(root, k) = kth_node_count(root.left_count, k-1) + kth_node_count(root.right_count, k-1)

'''

def kth_node_count(root, k):

    if root and not isinstance(root, Node):

        return None

 

    if not root or k <= 0:

        return 0

    if k == 1:

        return 1

    return kth_node_count(root.left_child, k-1) + kth_node_count(root.right_child, k-1)

 

&#39;&#39;&#39;

计算二叉树第K层节点个数,非递归方式

&#39;&#39;&#39;

def kth_node_count_not_recursion(root, k):

    if root and not isinstance(root, Node):

        return None

 

    if not root or k <= 0:

        return 0

 

    if k == 1:

        return 1

 

    queue = [(root, 1)]

    result = 0

    while queue:

        temp_node, temp_layer = queue.pop(0)

        if temp_node:

            if temp_layer == k:

                result += 1

            elif temp_layer > k:

                return result

            else:

                queue.append((temp_node.left_child, temp_layer+1))

                queue.append((temp_node.right_child, temp_layer+1))

    return result

ログイン後にコピー

二分木の葉ノード数を計算する

1

2

3

4

5

6

7

8

9

10

11

12

13

14

'''

计算二叉树叶子节点个数,递归方式

关键点是叶子节点的判断标准,左右孩子皆为None

'''

def leaf_count(root):

    if root and not isinstance(root, Node):

        return None

 

    if not root:

        return 0

    if not root.left_child and not root.right_child:

        return 1

 

    return leaf_count(root.left_child) + leaf_count(root.right_child)

ログイン後にコピー

2つの二分木が正しいかどうかを判断します同じ

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

'''

判断两个二叉树是不是相同,递归方式

isSame(root1, root2) = (root1.value == root2.value)

                    and isSame(root1.left, root2.left) 

                    and isSame(root1.right, root2.right)

'''

def is_same_tree(root1, root2):

    if not root1 and not root2:

        return True

 

    if root1 and root2:

        return (root1.value == root2.value) and \

               is_same_tree(root1.left_child, root2.left_child) and \

               is_same_tree(root1.right_child, root2.right_child)

    else:

        return False

ログイン後にコピー

二分探索木BSTかどうかの判定

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

'''

判断是否为二分查找树BST,递归方式

二分查找树的定义搞清楚,二分查找树的中序遍历结果为递增序列

'''

def is_bst_tree(root):

    if root and not isinstance(root, Node):

        return None

 

    def is_asc(order):

        for i in range(len(order)-1):

            if order[i] > order[i+1]:

                return False

        return True

 

    return is_asc(middle_order_bot_recursion(root))

ログイン後にコピー

テスト方法

1

2

3

4

5

6

7

8

9

10

11

12

13

14

if __name__ == "__main__":

    tree = Tree(1)

    tree1 = Tree(1)

    node6 = Node(None, None, 7)

    node5 = Node(None, None, 6)

    node4 = Node(None, None, 5)

    node3 = Node(None, None, 4)

    node2 = Node(node5, node6, 3)

    node1 = Node(node3, node4, 2)

    tree.root.left_child = node1

    tree.root.right_child = node2

    tree1.root.left_child = node2

    tree1.root.right_child = node2

    print(is_bst_tree(tree.root))

ログイン後にコピー

以上がバイナリ ツリー アルゴリズムの Python 実装例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

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