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

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

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

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

所以可能的路径是

abcdefijkl

abcdefkl

abcdghijkl

abcdghkl

我有一个 repo一个失败的 C# 单元测试(设置树并调用一个基本的 recusive 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)
    }
}

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