Python将列表转换为树表示格式

Question

我和我的朋友正在做一个简单的Python项目。实际上，我们正在用自己的方式实现前缀并行和算法。

我们正在创建和处理一个格式非常奇怪的二叉树。我们希望将此格式转换为Tree printing库/软件(如ete2)所接受的格式。

因此，树的每一层都以这种方式被压入列表

[ [level0], [level1], ... [level i-1], [root] ]

在我们的格式中，每个内部列表(树的级别)都有偶数个节点或叶子。

例如，假设我们有这样的输入:[1, 2, 3, 4, 5]。这将产生以下输出列表:[[1, 2, 3, 4], [3, 7], [10, 5], [15]]

上面输出示例的问题是，有时叶子不在最后一层，但它们包含在上层列表中。这使得很难处理列表的列表，区分节点和叶子，并将它们安排在正确的位置。

我们希望将其可视化如下:

https://i.stack.imgur.com/vWztP.png

其中括号内的数字为节点，其余为叶子。

为了生成这个输出树，我们想使用一个tree绘图库。大多数人期望这种格式:[root, [left], [right]]

所以，在我们的例子中，我们的格式应该是这样的:

[15, [10, [3, [1], [2]], [7, [3], [4]] ], [5] ]

因为我们现在不能重写我们代码的整个逻辑，所以我们正在寻找一种聪明的方法把我们奇怪的格式转换成那个格式。

欢迎任何想法。非常感谢。

Answer 1

您可以利用以下事实:对于树的r, col c行中的元素，如果这些元素存在(否则该节点是叶子)，则左子元素和右子元素分别位于下一行的c*2和c*2+1位置。把它放到一个算法中:

def normalize(tree, row=0, col=0):
    try:
        node = tree[row][col]
        left  = normalize(tree, row+1, col*2)
        right = normalize(tree, row+1, col*2+1)
        return [node, left, right] if left or right else [node]
    except:
        return None # child index does not exist

的例子:

>>> tree = [[1, 2, 3, 4], [3, 7], [10, 5], [15]]
>>> print normalize(tree[::-1]) # reverse the list!
[15, [10, [3, [1], [2]], [7, [3], [4]]], [5]]