树结构的泛型遍历

Question

我正在尝试编写更通用的树（好吧，它是二叉树）遍历，因为现在的方式是我重复了非常相似的代码。

我正在按字典序遍历树。我认为可以通过通用树遍历抽象的函数示例是（伪代码）：

items(node*, key, list&) {
    if(node->value)
        list.push({node->value, key})
    if(node->left)
        items(node->value, key + "0")
    if(node->right)
        items(node->value, key + "1")
}

draw(node*, id, ostream&) {
    drawNode(node, id)
    if (node->left)
        drawLine(node, node->left, "0", ostream&)
        draw(node->left, ++id, ostream&)
    if (node->right)
        drawLine(node, node->right, "1", ostream&)
        draw(node->right, ++id, ostream&)

我不是要功能代码，只是朝着正确的方向前进。是否应该使用将函数作为参数的模板来完成？更复杂的情况呢，其中遍历不仅仅以单个 left/right 节点的存在为条件（两个 trie 的合并似乎太像这种抽象的候选者）。

Answer 1

遍历的通用抽象是一种合适的迭代器形式。一旦遍历成为位置的线性序列，您将使用一种传统的迭代器来制定它，最有可能建模 BidirectionalIterator。当概括树（或更一般的图）的遍历时，您可能会在不同的方向上移动迭代操作。

Answer 2

Necroposting，但如果有人回答这个问题，仍然值得一试。

泛型树遍历是由函数式编程的理论家研究的，他们最终为 haskell 生成了几个可用的库。我将指向 recursion-schemes and syb（废弃你的边框）库。两者都附有一篇描述所采用方法的论文。

Syb 依赖于一种运行时反射形式并使用了相当多的类型 casts/coercion，但递归方案已移植到多种语言，包括 kotling 和 scala，因此它们与命令式语言兼容。

这些作品绝不代表递归遍历树状数据结构所能完成的工作的巅峰之作，但它们看到了一些用途，并且这些想法经过了充分测试。

树结构的泛型遍历

Generic traversal of tree structure

c++

generics

algorithm

tree

traversal