将树节点转换为边端点的坐标

Question

我有一个（重组）二叉树 t = ((4,), (3, 5), (2, 4, 6), (1, 3, 5, 7))，其中晶格级别索引为 (0,1,2,3)。即 4 的索引为 0，而 3、5 的索引为 1，依此类推。我需要一组边端点的坐标（连接树节点）。自然地，4连接到3和5； 3 连接到 2 和 4； 5 连接到 4 和 6。

对我可以采取的方法有什么想法吗？

输出是元素（以任何顺序）（这些是成对的）

[(0,4),(1,3)], [(0,4),(1,5)], 
[(1,3),(2,2)], [(1,3),(2,4)], [(1,5),(2,4)], [(1,5),(2,6)], 
[(2,2),(3,1)], [(2,2),(3,3)], [(2,4),(3,3)], [(2,4),(3,5)], [(2,6),(3,5)], [(2,6),(3,7)]

树会长大。任何可迭代的基本数据（列表、集合、元组、字典等）都可以。

我认为将树转换为矩阵的下对角线会使事情变得更容易，但现在认为可能有直接的方法。

这是重组树的进展示例：

如果需要澄清，请告诉我。

Answer 1

如果所有相邻节点都被认为是成对的：

t = ((4,), (3, 5), (2, 4, 6), (1, 3, 5, 7))

from itertools import tee
a, b = tee(t)
next(b)
for ind, (t1, t2) in enumerate(zip(a, b)):
    print([[(ind, i), (ind + 1, j)] for i in t1 for j in t2])

您必须对输出进行分组，但这应该更接近您的需要：

def pairs(t):
    a, b = tee(t)
    next(b)
    for ind, (t1, t2) in enumerate(zip(a, b)):
        it = iter(t2)
        nxt = next(it)
        for ele in t1:
            n = next(it)
            yield [(ind, ele), (ind + 1, nxt)]
            yield [(ind, ele), (ind + 1, n)]
            nxt = n


from pprint import pprint as pp
pp(list(pairs(t)),compact=1)

输出：

[[(0, 4), (1, 3)], [(0, 4), (1, 5)], [(1, 3), (2, 2)], [(1, 3), (2, 4)],
 [(1, 5), (2, 4)], [(1, 5), (2, 6)], [(2, 2), (3, 1)], [(2, 2), (3, 3)],
 [(2, 4), (3, 3)], [(2, 4), (3, 5)], [(2, 6), (3, 5)], [(2, 6), (3, 7)]]

将树节点转换为边端点的坐标

Convert tree nodes to coordinates of endpoints of edges

python

algorithm

tree

data-structures

python-3.x