Lib.rs

摘要

一个库，提供了完整的二叉树访问者特质，包含常见的默认实现，例如dfs_inorder或dfs_preorder等访问策略。它还提供了两种完整的二叉树数据结构的实现，具有可变和不可变访问者，这些访问者实现了访问者特质。

lib.rs:

摘要

一个库，提供了完整的二叉树访问者特质，包含对dfs_inorder或dfs_preorder等访问策略的默认实现。还提供了一些适配器，允许你在每次调用next()时映射、连接，或者可选地产生深度。它还提供了两种完整的二叉树数据结构的实现，具有可变和不可变访问者，这些访问者实现了访问者特质。一个按广度优先布局，另一个按深度优先布局。这两种布局都假设树中的每个节点都是相同类型的。

这是一个这个crate围绕的特质

pub trait Visitor:Sized{
    type Item;
    fn next(self)->(Self::Item,Option<[Self;2]>);
}

如果你有一个访问者，你可以调用next()来消费它，并产生正在访问的节点及其子节点的引用。

迭代器在调用next()时被消耗的事实允许我们返回可变引用，而不必担心用户以其他方式创建相同的可变引用。这个属性提供了一个安全地获取子节点可变引用的方法。这对于并行化分而治之风格的问题很有用。

目标

提供一个有用的完整二叉树访问者特质，它具有类似于Iterator特质的一些功能，如zip()和map()，并且可以用于并行分而治之风格的问题。

内存局部性

在dfs中对元素进行排序可能更适合分而治之的问题。我们希望快速访问的主要内存访问模式如下：如果我有父节点，我希望能够快速访问子节点。因此，我们希望子节点靠近父节点。而在bfs排序中，根节点的子节点实际上就在其旁边，但在树的倒数第二层节点中，子节点可能相距甚远（可能是n/2个元素远！）在dfs排序中，随着你向下遍历树，你将获得更好的局部性。

dfs排序的一个缺点是，如果叶节点没有使用所有空间，那么浪费的空间将散布在整个数据结构中。在bfs排序中，所有叶节点都位于数据结构的末尾，因此在遍历树时，内存局部性惩罚可能不会那么高。

对于并行分而治之，dfs排序可能比bfs排序更好。在dfs排序中，一旦解决问题被分解，每个任务处理的内存部分不会相交。而在bfs排序中，任务仍在操作交错内存部分。