我需要一种算法来遍历带有可选节点和替代节点的树，以计算所有可能的路径

Question

给定以下树，它是一种 Backus-Nauf 形式的符号，其中 |表示或（所以B是F或G）和[]表示可选（所以H是可选的）

Def: A B C
A: D E
B: F | G
C: [H] I
D: a b
E: c d
F: e f
G: g h
H: i j
I: k l

a: a
b: b
c: c
d: d
e: e
f: f
g: g
h: h
i: i
j: j
k: k
l: l

可以看作是

              Def
    A          B          C
 D     E    F  |  G   [H]    I
a b   c d  e f   g h  i j   k l

我需要遍历提取叶节点的树并转换为下面给出可能路径的树

所以可能的路径是

abcdefijkl

abcdefkl

abcdghijkl

abcdghkl

我有一个 repo 有一个失败的 C# 单元测试（设置树并调用基本的递归 walker），希望它能阐明我想要实现的目标。

我想不通的是如何在可选节点和替代节点处分支，同时保持正确的叶子以将后续叶子附加到。

Answer 1

非递归广度优先搜索可能看起来像这些线（伪代码）。通过调用 findAllLeafPaths(Def):

开始

var allPathsFound = {}
function findAllLeafPaths(startNode) {
    var tokenSequenceQueue = {
        createTokenSequenceFrom(startNode)
    }
    while (tokenSequenceQueue.isNotEmpty()) {
        var tokenSequence = tokenSequenceQueue.removeFirst()
        var allLeaves = true
        for (every token T in tokenSequence) {
            if isLeafNode(T)
                continue
            else if T's rule is "T: Y Z" {
                allLeaves = false
                tokenSequenceQueue.append(tokenSequence.replace(T, Y + Z))
            } else if T's rule is "T: [Y] Z" {
                allLeaves = false
                tokenSequenceQueue.append(tokenSequence.replace(T, Y + Z))
                tokenSequenceQueue.append(tokenSequence.replace(T, Z))
            } else if T's rule "T: Y | Z" {
                allLeaves = false
                tokenSequenceQueue.append(tokenSequence.replace(T, Y))
                tokenSequenceQueue.append(tokenSequence.replace(T, Z))
            }
        }
        if (allLeaves) {
            allPathsFound.add(tokenSequence)
        }
    }
}

这里还有一个递归深度优先的版本。我更喜欢第一个，因为递归使您的堆栈受到结果路径的最大可能长度的支配：

var allPathsFound = {}
function toLeafNodes(tokenSequence) {
    var allLeaves = true
    for every token T in tokenSequence {
        if isLeafNode(T)
            continue
        else if T's rule is "T: Y Z" {
            allLeaves = false
            toLeafNodes(tokenSequence.replace(T, Y + Z)
        } else if T's rule is "T: [Y] Z" {
            allLeaves = false
            toLeafNode(tokenSequence.replace(T, Y + Z)
            toLeafNode(tokenSequence.replace(T, Z)
        } else if T's rule "T: Y | Z" {
            allLeaves = false
            toLeafNode(tokenSequence.replace(T, Y)
            toLeafNode(tokenSequence.replace(T, Z)
        }
    }
    if (allLeaves) {
        allPathsFound.add(tokenSequence)
    }
}

[编辑] 非递归版本目前一次替换一个，并立即将结果序列放入队列。它可以进一步优化，一次完成所有可能的替换。

Answer 2

还有另一种方法可以根据您的定义构建树。考虑：

Def: A B C
A: D E
B: F | G
C: [H] I

开始于

A
 \
  B
   \
    C

然后把A换成D E:

D
 \
  E
   \
    B
     \
      C

对 B（替换为 F | G）和 C（替换为 [H] I）做同样的事情，你会得到：

      D
       \
        E     
    /       \
   F         G
  / \       / \
 I   H     I   H
      \         \
       I         I

现在，如果您对该树进行递归深度优先遍历，您将获得有效字符串：

D E F I
D E F H I
D E G I
D E G H I

并且在输出字符串时，您可以将 D 替换为 "a b"，等等。

我一步一步地展示了它，但你可以一次完成所有操作。

我需要一种算法来遍历带有可选节点和替代节点的树，以计算所有可能的路径

I need an algorithm to walk a tree with optional and alternative nodes to calculate all possible paths

algorithm

tree-traversal