0

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

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

因此，树的每一层都以这种方式推送到列表中

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

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

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

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

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

http://i.imgur.com/BKrqNZi.png

其中括号中的数字是节点，其他数字是叶子。

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

因此，在我们的示例中，我们的格式应该是这样的：

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

因为我们目前无法重写代码的整个逻辑，所以我们正在寻找一种巧妙的方法将我们奇怪的格式转换为那个格式。

欢迎任何想法。非常感谢您提前。

4

1 回答 1

5

您可以利用这样一个事实，即对于树的 rowr和 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]]
于 2014-06-20T20:30:51.967 回答