用元组在 python 中构建一棵树

Question

我得到以下元组 :(12, (6, (2,), (8,)), (15, (14,), (18,))) 我需要 return 以下形式的 Tree 实例：Tree(12, Tree(6, Tree(2), Tree(8)), Tree(15, Tree(14), Tree(18)))

我的 class 是：

class Tree():
    def __init__(self, entry, left=None, right=None):
        self.entry = entry
        self.left = left
        self.right = right
    def __repr__(self):
        if not self.left and not self.right:
            return "Tree({0})".format(repr(self.entry))
        return "Tree({0},{1},{2})".format(repr(self.entry),repr(self.left),repr(self.right))

我无法理解的问题是为什么不进入基本条件？以及如何修复该功能。

我做的功能是：

def build_tree(tree):
    if type(tree) != tuple:
        return Tree(tree)
    return Tree(tree[0], build_tree(tree[1]), build_tree(tree[2]))

激活为：

tree1 = (12, (6, (2,), (8,)), (15, (14,), (18,)))
t1=build_tree(tree1)
print(t1)

Answer 1

你想要isinstance

def build_tree(tree):
    if isinstance(tree, tuple):
        if len(tree) == 1:
            return Tree(tree[0])
        return Tree(tree[0], build_tree(tree[1]), build_tree(tree[2]))
    return Tree(tree)

print(build_tree((12, (6, 2, 8), (15, 14, 18))))

Answer 2

问题是 tree[1] 和 tree[2] 有时未设置 (2,) 或 (8,) 等条目。这将导致 IndexError。解决方法是用 (None, None) 值“填充”元组，然后 trim 减少到 3 个元素 -

def build_tree(a):
  if a:
    (entry, left, right) = (a + (None, None))[:3]
    return Tree(entry, build_tree(left), build_tree(right))
  else:
    return None

x = (12, (6, (2,), (8,)), (15, (14,), (18,)))
mytree = build_tree(x)
print(mytree)

Tree(12,Tree(6,Tree(2),Tree(8)),Tree(15,Tree(14),Tree(18)))

我要指出的是，使用薄 class 包装器的功能方法将使您更容易扩展树的功能。有关此技术的更多信息，请参阅 .

Answer 3

由于最里面的元组只有一个成员，避免使用超出范围的索引，只是 slice 将节点值后面的元组成员作为元组成员，然后映射那些你的功能。

因此，将 build_tree 函数中的最后一个 return 语句替换为：

return Tree(tree[0], *map(build_tree, tree[1:]))

用元组在 python 中构建一棵树

Building a tree in python with tuple

python

tree

recursion