如何迭代这个树/图形数据结构？（关于）IT技术

Question

我需要迭代一棵树/图并按照一些规则生成特定的输出：

     _ d
   /  / \
  b  c  _e
 /     / |
a     f  g

预期输出应为（顺序无关）：

{'bde', 'bcde', 'abde', 'abcde', 'bdfe', 'bdfge', 'abdfe', ...}

规则如下：

1. 树的顶部 'bde' (最左侧的根节点子节点+根节点+最右侧的根节点子节点) 应始终存在。
2. 左-右顺序应保持不变，例如组合 'cb' 或 'gf' 不被允许。
3. 所有路径都按从左到右的方向进行。

我需要找到遵循这些规则的所有路径。不幸的是，我没有计算机科学背景，我的头快要爆炸了。任何提示都将有所帮助。

编辑：此结构非常接近于我的树：

class N():
    """Node"""
    def __init__(self, name, lefts, rights):
        self.name = name
        self.lefts = lefts
        self.rights = rights

tree = N('d', [N('b', [N('a', [], [])], []), N('c', [], [])], 
              [N('e', [N('f', [], []), N('g', [], [])], 
                      [])])

或许更易读：

N('d', lefts =[N('b', lefts=[N('a', [], [])], rights=[]), N('c', [], [])], 
       rights=[N('e', lefts=[N('f', [], []), N('g', [], [])], rights=[])])

- Biela Diela

---

展示你所尝试过的！ - ovgolovin

说实话，我不知道该如何开始。我想过使用双重循环，但是我感觉需要进行一些递归操作。我只是无法将所有东西组合在一起。 - Biela Diela

d和f/g之间，以及b和c之间没有直接路径。很难揭示你期望的输出背后的逻辑（为什么和何时从d跳到g然后到f再回到e）。 - marmeladze

树的初始格式是什么？ - Nat Knight

你说这是一棵二叉树，但是d似乎有3个孩子？这个例子是错误的还是它不是二叉的？ - happydave

Answer 1

所以这可以被视为两个问题的组合。我的代码假设已经像你的问题陈述中一样定义了 N 类和 tree 结构。第一个问题：给定一个类似于你的树结构，如何生成其节点的中序遍历？这是一个相当简单的问题，因此我将展示一个解决它的简单递归生成器：

def inorder(node):
    if not isinstance(node, list):
        node = [node]
    for n in node:
        for left in inorder(getattr(n, 'lefts', [])):
            yield left
        yield n.name
        for right in inorder(getattr(n, 'rights', [])):
            yield right

print list(inorder(tree))
# ['a', 'b', 'c', 'd', 'f', 'g', 'e']

第二步: 现在我们已经有了节点的“正确”排序，接下来我们需要找出所有可能的组合 a) 保持这个顺序，以及 b) 包含三个“锚点”元素 ('b', 'd', 'e')。我们可以借助总是方便的itertools库完成此任务。

基本步骤如下:

• 确定锚点元素，并围绕它们将列表分成四个部分
• 计算每个分区的所有元素组合 (即幂集)
• 取所有这样的组合的乘积

就像这样:

from itertools import chain, combinations
# powerset recipe taken from itertools documentation
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def traversals(tree):
    left, mid, right = tree.lefts[0].name, tree.name, tree.rights[0].name
    nodes = list(inorder(tree))
    l_i, m_i, r_i = [nodes.index(x) for x in (left, mid, right)]
    parts = nodes[:l_i], nodes[l_i+1:m_i], nodes[m_i+1:r_i], nodes[r_i+1:]
    psets = [powerset(x) for x in parts]
    for p1, p2, p3, p4 in product(*psets):
        yield ''.join(chain(p1, left, p2, mid, p3, right, p4))

print list(traversals(tree))
# ['bde', 'bdfe', 'bdge', 'bdfge', 'bcde', 'bcdfe', 
#  'bcdge', 'bcdfge', 'abde', 'abdfe', 'abdge', 'abdfge', 
#  'abcde', 'abcdfe', 'abcdge', 'abcdfge']

- tzaman

---

太棒了！现在我知道我距离自己能做到这一点有多远了。谢谢！ - Biela Diela