如何在 python 中实现状态 space 树（二叉树）？

Question

给定 (M, F) - 随着某个过程的每一步，元组变成 (M + F, F) 或 (M, M + F)。所以，从 (1, 1) 开始，有以下可能：

我在绘制树时遵循的算法是 -

If not root, 
left_ child = (parent0 + parent1, parent1)

and right_child = (parent0, parent0 + parent1)

其中 parent0 指的是父元组的第一个元素，parent1 指的是第二个元素。

我完全不确定我将如何创建一棵树，该树将遵循上述算法在给定 M 和 F 的任何起始值的 n 个步骤后创建树。

当我决定在线搜索时，我得到了一些类似的东西：

class Tree(object):
    def __init__(self):
        self.left = None
        self.right = None
        self.data = None

root = Tree()
root.data = "root"
root.left = Tree()
root.left.data = "left"
root.right = Tree()
root.right.data = "right"

或

class Tree:
    def __init__(self, cargo, left=None, right=None):
        self.cargo = cargo
        self.left  = left
        self.right = right

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

tree = Tree(1, Tree(2), Tree(3))

我想不出一种方法来使用上面的代码来构建我想要的状态 space 树。也就是说，当给定输入为 (M, F) 且 n 是过程中的步骤数（即树中的级别数）时，我如何实现一棵自动创建具有计算值的子树的树。

Answer 1

您只需要一个包含两个值而不是一个值的树，以及一些自动生成子树的属性：

class SpaceTree:
    def __init__(self, M=1, F=1):
        self.M= M
        self.F= F
        self._left= None
        self._right= None

    @property
    def left(self):
        if self._left is None:
            self._left= SpaceTree(self.M+self.F, self.F)
        return self._left

    @property
    def right(self):
        if self._right is None:
            self._right= SpaceTree(self.M, self.F+self.M)
        return self._right

    def __repr__(self):
        return 'SpaceTree({}, {})'.format(self.M, self.F)

现在你可以创建一棵树并遍历它到你想要的为止：

>>> SpaceTree()
SpaceTree(1, 1)
>>> SpaceTree().left
SpaceTree(2, 1)
>>> SpaceTree().left.right
SpaceTree(2, 3)

如何在 python 中实现状态 space 树（二叉树）？

How do I implement a state space tree (which is a binary tree) in python?

python

algorithm

data-structures

tree

state-space