binary_tree_iterator.py

# -*- coding:utf-8 -*-

import numpy as np

# [問題]
#
# 以下の表はそのマスとその周囲8マスに含まれている爆弾の個数を表しています。フィールドに含まれている爆弾の位置を(x,y)としたとき、
# その積k(=x*y)が小さい順にアルファベットを並べるとある単語が完成します。
field_data = np.array([
    [[1, 'i'], [2, 'p'], [2, 'a'], [1, 'g'], [1, 'x'], [1, 'u']],
    [[1, 'c'], [2, 't'], [2, 'e'], [2, 'h'], [2, 'r'], [2, 'a']],
    [[1, 'g'], [2, 'q'], [1, 'i'], [2, 'r'], [3, 'n'], [3, 'z']],
    [[2, 'r'], [2, 'd'], [2, 'g'], [2, 'o'], [3, 'e'], [2, 'o']],
    [[2, 'v'], [2, 'n'], [2, 'o'], [1, 'w'], [3, 'y'], [2, 's']],
    [[2, 'b'], [2, 't'], [2, 'r'], [1, 'p'], [2, 'w'], [1, 'a']],
    [[2, 'g'], [2, 'u'], [2, 'i'], [1, 'x'], [3, 'q'], [2, 'u']],
    [[2, 'e'], [2, 't'], [2, 's'], [1, 'm'], [2, 'x'], [1, 'n']],
])

field_x_length = 6
field_y_length = 8
max_depth = 8

mines = np.zeros((field_x_length, field_y_length))


class BinaryTreeNode(object):
    def __init__(self, parent=None, value=None):
        self.p = parent
        self.v = value
        self.r = None
        self.l = None

    def __str__(self):
        return str(self.v)

class BinaryTreeNodeIterator(object):
    def __init__(self, _root):
        self.root = _root

    def __iter__(self):
        return self._next()

    def _next(self, node=None):
        node = node
        if node is None:
            node = self.root

        if node.r is None and node.l is None:
            yield self.get_value(node)

        if node.r is not None:
            for n in self._next(node.r):
                yield n

        if node.l is not None:
            for n in self._next(node.l):
                yield n

        raise StopIteration

    def get_value(self, node):
        _buf = ''
        n = node
        while n.p is not None:
            _buf = str(n) + _buf
            n = n.p
        return _buf

def createTree(depth):
    root = BinaryTreeNode()
    return addChild(depth, root)

def addChild(max_depth, node, depth=0):
    node.r = BinaryTreeNode(parent=node, value=1)
    node.l = BinaryTreeNode(parent=node, value=0)
    depth += 1
    if depth >= max_depth:
        return node
    addChild(max_depth, node.r, depth)
    addChild(max_depth, node.l, depth)
    return node

root = createTree(8)

itr = BinaryTreeNodeIterator(root)
for elm in itr:
    print elm