编程语言应该内置树遍历（Tree Traversal）原生支持

Programming languages should have a tree traversal primitive

Source | HN Comments

文章探讨了编程语言原生支持树遍历（`Tree Traversal`）的必要性，提出类似 `for_tree` 的控制流结构，简化树状结构的处理，类似于 `for` 循环在线性遍历中的作用。作者认为，相比递归函数，`for_tree` 更简洁、不易出错，并支持 `break`、`continue` 和 `prune` 等控制流。文章还讨论了与递归函数、基于范围的 `for` 循环以及广度优先遍历的对比，强调了 `for_tree` 在处理隐式树和非数据结构树时的优势。最后，作者提供了一个 C++ 的测试实现，展示了该概念的可行性。

Tyler Glaiel's Blog

编程语言应该有一种控制流结构，能够以一种优雅的方式处理树状结构的遍历，就像 for/foreach 循环可以处理线性遍历一样。这在当前大多数语言所采用的控制流结构中是一个缺失的环节。我经常需要做这样的事情，似乎应该有一些捷径可走。

我最近发布了一个关于这个想法的帖子，一直在思考我希望它看起来像什么。我在任何其他语言中都找不到类似的东西。我最熟悉 C++，所以我的示例代码将是 C++ 风格的，但它足够通用，你可以将它放入几乎任何其他语言中。我不是语言设计专家，所以这更像是一个粗略的想法，而不是一个正式的提案。

for_tree(Node* N = mytreeroot; N != NULL; N : {N->left, N->right}){
	print(N->value);
}

去掉具体细节，这几乎和现有的 for 循环语法相同：

for_tree(init; condition; branch){
	//body
}

它本质上是一个 for 循环，但是它会分支，而不是线性地继续。"init" 在你进入 for_tree 循环时运行，与普通的 for 循环完全相同。"condition" 必须满足才能进入循环体。"branch" 将初始值演变为多个分支 (在这里它必须编译成递归函数调用)。

“为什么不直接使用递归函数？”

好吧，与为要在每种类型的树上执行的每个操作实现递归函数相比，这要简单得多，并且不易出错，而且所有相关代码最终都会在适当的位置并且可读。无论如何，这可能会编译成与递归函数相同的代码。这只是一个很好的捷径，就像 for 是 goto 和标签的一个很好的捷径一样。

for_tree(Node* N = mytreeroot; N != NULL; N : {N->left, N->right}){
	print(N->value);
}

将编译成相当于：

void for_tree_internal(Node* N){
	print(N->value);
	for(Node* n2 : {N->left, N->right}){
		if(n2 != NULL){
			for_tree_internal(n2);
		}
	}
}
for_tree_internal(mytreeroot);

与需要为要在树上执行的每个操作实现递归函数相比，for_tree(...) 看起来是不是更简洁、更简单且更不容易出错？

此外，for_tree 将提供一些递归函数不容易实现的额外好处，例如能够使用 break、continue 和 return 从函数体内部跳出。它们的行为类似于 for 循环。

for_tree(Node* N = mytreeroot; N != NULL; N : {N->left, N->right}){
	if(N->value == 10) {
		found = true;
		break; //会跳出整个 for_tree 代码块，
            //在这个过程中展开堆栈
	}
}

这里可以添加一个额外的流程结构 "prune"，它会阻止循环遍历当前节点的分支。

for_tree(Node* N = mytreeroot; N != NULL; N : {N->left, N->right}){
	if(N->value == 10) {
		prune; //不需要检查此节点的任何子节点
	}
}

“为什么不直接使用基于范围的 `for` 循环？”

好吧，基于范围的 for 循环要求你的树存在于内存中，并且你为你的树定义了一个迭代器。使用 for_tree，你可以在完全隐式的树上运行，而无需定义任何迭代器或生成器函数。这是一个示例，我正在检查由长度为 8 或更少的 "a"、"b" 和 "c" 组成的每个字符串。

for_tree(string x = ""; x.size() <= 8; x : {x+"a", x+"b", x+"c"}){
	print(x);
}

这是一个需要“树状遍历”的操作，但不是迭代内存中存在的数据结构。你可以在 for_tree 内部完成整个操作。它完全独立于你正在或没有使用的任何底层数据结构。前面描述的 "prune" 流也是你无法从基于范围的 for 循环中获得的东西。

这里有一个小陷阱，那就是在上面的字符串示例中，它实际上是生成并拒绝了所有长度为 9 的字符串。一个普通的 for 循环也会在退出之前到达最后一个有效状态之后的状态，只是对于线性 for 循环来说，这通常不是什么大问题，因为这通常就像，一个额外的加法和条件检查。另一方面，树遍历中的“深一层”意味着检查比你需要的叶节点多很多倍的有效性。

你可以通过多种方式手动解决此问题，如果你已经在叶节点，则生成一个空分支列表：

for_tree(string x = ""; x.size() <= 8; 
x : x.size() < 8 ? {x+"a", x+"b", x+"c"} : {}){
	print(x);
}

或者只是在函数体中进行 prune：

for_tree(string x = ""; x.size() <= 8; x : {x+"a", x+"b", x+"c"}){
	print(x);
	if(x.size() == 8) prune;
}

可能有更好的解决方法，但我认为必须进一步将语法从 for 循环中分离出来。无论如何。

“如果你想进行广度优先遍历而不是深度优先遍历，该怎么办？”

因此，深度优先搜索非常简单，使用最少的额外内存，并且与我们已经使用的堆栈配合良好。 BFS 需要大量的额外内存（足以使其可能需要使用堆），并且更加复杂。如果你真的想这样做，你可以做一个像 for_tree_breadth_first(...) 这样的替代函数，但我认为 BFS 所需的额外复杂性对于“原生”结构来说可能太大了。也可能不是。

在阅读了关于这篇文章的讨论之后，我添加了这一个问题：

“大多数编程语言已经有定义了迭代器的树，为什么不直接使用它们？”

树状关系在编程时一直存在，即使没有明确地将某些东西表示为树。显然，如果你有一个 "MyTree"，你可以只使用 foreach 和迭代器来遍历它。抽象出这种控制流的好处在于能够处理隐式树或其他想要以类似于树的方式遍历的结构。如果你有以某种方式引用多个其他对象的对象，那么你就会有一个树状关系，即使你没有专门将其表示为树。爬取此关系的代码在大多数地方都是相同的，因此它是被抽象出来的黄金地段。

无论如何，作为奖励，这是一个 C++ 测试实现，它试图通过一堆模板和宏尽可能地接近这个想法。用法更难看，并且一些结构不起作用（例如，你不能从这里的 for_tree 内部返回），但我认为这是一种巧妙的概念证明。