1

这是我在 Stack Overflow 上的第一篇文章。我真的很佩服这个网站和所有帮助其他人编写代码的用户。希望我能从你那里得到一些帮助:)

我遇到的问题可以描述如下：

  1. 从给定节点（根节点）开始；
  2. 计算节点的子节点并存储（计算前不知道子节点的个数）；
  3. 在叶节点处，使用“评估函数”计算叶的值。
  4. 当所有叶子都被评估后，选择具有最大/最小值的叶子节点，并获取存储在该叶子的祖父（根的孩子）中的数据，如图所示。

遍历并建树的过程：

遍历并建树的过程

由于“评估功能”只能应用于叶节点，我认为深度优先搜索适合这里。此外，Simulink 中的 MATLAB Function Block不支持递归调用函数。所以我认为使用Stack来存储节点是一个不错的方法。

根据这里的优秀答案，逻辑非常清晰和直接。来自Gumbo的代码

stack.push(root)
while !stack.isEmpty() do
  node = stack.pop()
  for each node.childNodes do
    stack.push(stack)
  endfor
// …
endwhile

但是我在实现DFS算法的时候遇到了一些问题：

  1. 由于邻接矩阵浪费大量内存，我尝试使用邻接表来表示树。但我什至没有找到使用邻接表实现 DFS 算法的伪代码。有人可以帮助我吗？

  2. 从父节点（添加节点）计算新节点时如何更新树？

  3. 我应该让孩子从祖父（root 的孩子）那里继承数据以节省追溯步骤吗？还有其他方法可以解决流程的第四步吗？

4

0 回答 0