编程语言应该有一个树遍历原语

主要观点:应在编程语言中添加能以良好方式处理树状遍历的控制流结构,类似 for/foreach 循环处理线性遍历,当前多数语言的控制流结构在此方面存在缺失,文中给出了类似 for 循环的 for_tree 示例代码及其具体细节,如 init、condition、branch 的作用等,还提到 for_tree 比实现递归函数更简单不易出错,能提供 break、continue、return 等操作,有“prune”流可防止遍历当前节点的分支,能处理隐式树结构,无需定义迭代器或生成函数,同时也指出了一些可能存在的问题及解决方法,如在字符串示例中避免生成多余字符串,还提到了深度优先搜索和广度优先搜索的特点及实现难度,最后给出了一个尝试实现 for_tree 的 C++测试代码(包含模板和宏)。

关键信息:

  • for_tree 语法及作用:for_tree(Node* N = mytreeroot; N!= NULL; N : {N->left, N->right}){...},init 进入循环时运行,condition 满足进入循环体,branch 演化初始值为多个分支。
  • for_tree 编译后代码:void for_tree_internal(Node* N){...},包含递归调用。
  • “prune”流作用:防止遍历当前节点的分支。
  • 测试代码实现:包含多个模板和宏,如tree_break等,用于实现 for_tree 功能,通过for_tree宏对不同类型的树进行遍历操作。

重要细节:

  • for_tree 可处理隐式树结构,无需定义迭代器或生成函数,如检查由“a”“b”“c”组成的长度不超过 8 的字符串。
  • 测试代码中通过for_tree宏对自定义的Node树结构进行遍历,展示了其在实际中的应用。
  • 对于字符串示例中可能生成多余字符串的问题,给出了手动解决方法,如生成空分支列表或在函数体中进行“prune”操作。
  • 提到深度优先搜索简单、使用额外内存少,广度优先搜索需要大量额外内存且更复杂,可实现 for_tree_breadth_first 函数但可能复杂度过高。
阅读 12
0 条评论