从父子结构算法创建完整的层次结构字符串，递归

Question

我正在解决以下任务。有一个给定元素的层次结构。我拥有最低级（基础）元素，并需要创建完整的层次结构字符串。我有一个函数，它返回一个元素的父级。这意味着我可以询问父级，然后是父级的父级等等。

例如：B是A的父级，[C1，C2]是B的父级，...

在这个例子中，结果应该是包含3个字符串的数组（第1、2、3行），每个字符串都包含基础元素A的完整层次结构。

以下是我的伪代码函数：

Function getAllParents (Element)

    ParentCount = getParentCount(Element)
    result = Element
    IF (ParentCount > 0) THEN
        FOR i = 0 to ParentCount
            ParentName = getParentName(Element, i)
            result =  result + "," + getAllParents(parent)
        NEXT
    END IF
    
    IF (ParentCount = 0) then       
        result =  result + &newLine
    END IF
    
    RETURN result

END Function

这是我的示例结果：

A,B,C1,D1,E1 
C2,D2,E2  
E3

如何达到预期结果？

A,B,C1,D1,E1
A,B,C2,D2,E2
A,B,C2,D2,E3

- Lukáš Tomšů

---

你的意思是什么？你有在某种方式下运行它吗？这只是 伪代码，不是吗？其次，你是如何运行它的？也就是说，你正在做什么（想象中）的调用？第三，设想你调用getAllParents(E1)。ParentCount为0。循环为空。所以你只需执行 result = result + &newLine，但这个“result”到底是什么，你添加了“newLine”之后呢？ - Will Ness

@WillNess 这是对我最初的特定语言的一般性问题链接。我添加了缺失的行来初始化结果：result = Element。我仅为基本元素调用此函数，总是有一个父元素。 - Lukáš Tomšů

变量 parent 在你的伪代码中似乎没有被声明。 - גלעד ברקן

Answer 1

我们必须在递归函数进入时建立当前的 line，并在函数退出时将返回的行作为 result 进行连接。这是伪代码：

Function getAllParents (line, Element)
    result = “”
    ParentCount = getParentCount(Element)
    IF (ParentCount > 0) THEN
        FOR i = 0 to ParentCount
            ParentName = getParentName(Element, i)
            result_i = getAllParents(copy(line)+”,”+ParentName, ParentName)
            result = result + result_i
        NEXT
    ELSE
        result = copy(line)+&newLine
    END IF
    
    RETURN result

END Function

每次达到终端节点时，newline 会添加到 line 中，就像在您的表格中一样。

我们称其为 getAllParents(“A”, “A”)。

为了更好地理解其工作原理，以下是您示例的函数调用流程:

(“A”, “A”)
- (“A,B”, “B”)
- - (“A,B,C1”, “C1”)
- - - (“A,B,C1,D1”, “D1”)
- - - - (“A,B,C1,D1,E1”, “E1”)
- - (“A,B,C2”, “C2”)
- - - (“A,B,C2,D2”, “D2”)
- - - - (“A,B,C2,D2,E2”, “E2”)
- - - - (“A,B,C2,D2,E3”, “E3”)

- TUI lover

---

不要使用Element = lastWordOf(line)，而是传递2个参数到递归调用中。相应地增加顶层调用。line_i可以包含多行文本，最好称其为result_i。最后，一些解释和说明会很有益/必要。特别是，这种改变远不止于“只是记住...”。实际上，它完全颠倒了结果构建的方向——它为每个新的递归调用引入了新鲜的“result”，而不是试图在从递归返回时构建它，并将结果前缀传递到递归中。 - Will Ness

Answer 2

正如您在问题描述中所说，问题出在结果类型：“结果应该是数组。”

以下是JavaScript的示例：

function getParentCount(el, ps){
  return ps[el] && ps[el].length
}

function getParentName(el, i, ps){
  return ps[el][i]
}
    
function getAllParents(el, ps){
  const ParentCount = getParentCount(el, ps)
  
  const result = []
  
  if (ParentCount > 0){
    for (let i=0; i<ParentCount; i++){
      const ParentName = getParentName(el, i, ps)
      const ParentPaths = getAllParents(ParentName, ps)
      
      for (let path of ParentPaths)
        result.push(el + "," + path)
    }
        
  } else {
    result.push(el)
  }
  
  return result
}

const parents = {
  A: ['B'],
  B: ['C1', 'C2'],
  C1: ['D1'],
  C2: ['D2'],
  D1: ['E1'],
  D2: ['E2', 'E3']
}

for (let path of getAllParents('A', parents))
  console.log(path)

- גלעד ברקן

---

但这不是被要求的。他们想要一个字符串作为结果，路径之间用换行符分隔。 - Will Ness

@WillNess 不，他们没有：“在这个例子中，结果应该是一个包含3个字符串（第1行、第2行、第3行）的数组，每个字符串都包含基本元素A的完整层次结构。” - גלעד ברקן

啊，好的，看代码，我把“数组”比喻成“多个项目”，理解有误了。 - Will Ness

@WillNess 那将是 literature.stackexchange.com :) - גלעד ברקן

有时候人们使用语言不够准确。 :) 他们字面上说了一件事，但是他们的代码却表达了另外一种意思... - Will Ness

@WillNess 我知道，我只是在逗你玩。 - גלעד ברקן