9 个稳定版本

1.2.1	2023 年 12 月 28 日
1.2.0	~~2023 年 11 月 24 日~~
1.1.3	2023 年 10 月 25 日
1.1.0	2023 年 9 月 23 日
1.0.2	2023 年 8 月 31 日

#145 在算法中

42 每月下载量
在 2 crates 中使用

MIT 许可证

315KB
6.5K SLoC

tree_iterators_rs

如果您喜欢使用这个 crate，请为 github 仓库点 star。

tree_iterators_rs 是一个库，旨在为用户提供在 Rust 中轻松处理树数据结构的实用工具（迭代器）。它为大多数用例提供了默认实现。这些包括

TreeNode - 该结构体具有基于 Vec 的子列表。文档
BinaryTreeNode - 该结构体包含对左节点和右节点的可选盒式引用。文档

此 crate 的编写方式允许您使用其他集合类型构建自己的实现。集合类型只需实现 Iterator 特性即可。

功能标志

此 crate 只包含一个功能标志

"serde" - 此标志可用于为 TreeNode 和 BinaryTreeNode 实现 Serialize 和 Deserialize。

优势

此 crate 不使用任何不安全代码！

使用此库的最大好处是各种树迭代器可以在 for 和 while 循环语法中互换使用。这意味着您可以将代码编写为今天使用广度优先搜索，并且可以轻松地将其交换为明天的深度优先前序或后序搜索，而无需显着更改代码结构。在语法上，此库还能够隐藏大量复杂性并提供友好的接口。

此库的另一个优点是其与 Rust 中其余迭代器的紧密集成。因为每个 API 都返回一个迭代器，所以您可以对树使用迭代器 API，如 filter、map 和 reduce，这可以非常有效地简化代码。

入门

开始使用最简单的方法是将这个crate作为依赖项添加，并添加一个使用语句来引入其预定义（use tree_iterators_rs::prelude::*;）。然后，您可以使用提供的BinaryTreeNode或TreeNode结构体创建您的数据结构，并使用它们的迭代器实现。这些结构体提供了此crate中所有功能的默认实现。附加到这些结构体的方法包括以下内容（所有这些方法都可在此文件中找到开源代码）

拥有迭代器API - 这些与into_iter()调用类似，将TreeNode的所有权移交给它。
- bfs()
- dfs_preorder()
- dfs_postorder()
- dfs_inorder() - 此迭代器仅适用于BinaryTreeNode
可变借用API - 这些不获取所有权，行为类似于iter_mut()调用。
- bfs_iter_mut()
- dfs_preorder_iter_mut()
- dfs_postorder_iter_mut()
- dfs_inorder_iter_mut - 此迭代器仅适用于BinaryTreeNode
借用API - 这些不获取所有权，行为类似于iter()调用。
- bfs_iter()
- dfs_preorder_iter()
- dfs_postorder_iter()
- dfs_inorder_iter() - 此迭代器仅适用于BinaryTreeNode
此外，所有这些API都有额外的修改方法，包括.leaves()和attach_ancestors()。这些方法都可以在迭代器调用之后链式调用（更多详细信息请参阅示例）。

示例

以下所有示例中，我们将使用以下树结构。它足够复杂，可以充分传达树迭代器的行为，同时不会过于繁杂。以下是使用BinaryTreeNode和TreeNode结构体构建此树的代码。

flowchart TD
A[0] --> B{1}
A --> C{2}
B --> D{3}
B --> E{4}
D --> Z{None}
D --> Y{None}
E --> X{None}
E --> W{None}
C --> F{5}
F --> V{None}
F --> U{None}
C --> G{6}
G --> H{7}
G --> T{None}
H --> S{None}
H --> I{8}
I --> J{9}
I --> R{None}
J --> Q{None}
J --> K{10}
K --> P{None}
K --> O{None}

使用BinaryTreeNode

use tree_iterators_rs::prelude::*;

pub fn create_example_binary_tree() -> BinaryTreeNode<usize> {
    BinaryTreeNode {
        value: 0,
        left: Some(Box::new(BinaryTreeNode {
            value: 1,
            left: Some(Box::new(BinaryTreeNode {
                value: 3,
                left: None,
                right: None,
            })),
            right: Some(Box::new(BinaryTreeNode {
                value: 4,
                left: None,
                right: None,
            })),
        })),
        right: Some(Box::new(BinaryTreeNode {
            value: 2,
            left: Some(Box::new(BinaryTreeNode {
                value: 5,
                left: None,
                right: None,
            })),
            right: Some(Box::new(BinaryTreeNode {
                value: 6,
                left: Some(Box::new(BinaryTreeNode {
                    value: 7,
                    left: None,
                    right: Some(Box::new(BinaryTreeNode {
                        value: 8,
                        left: Some(Box::new(BinaryTreeNode {
                            value: 9,
                            left: None,
                            right: Some(Box::new(BinaryTreeNode {
                                value: 10,
                                left: None,
                                right: None,
                            })),
                        })),
                        right: None,
                    })),
                })),
                right: None,
            })),
        })),
    }
}

使用TreeNode

use tree_iterators_rs::prelude::*;

pub fn create_example_tree() -> TreeNode<usize> {
    TreeNode {
        value: 0,
        children: Some(vec![
            TreeNode {
                value: 1,
                children: Some(vec![
                    TreeNode {
                        value: 3,
                        children: None,
                    },
                    TreeNode {
                        value: 4,
                        children: None,
                    },
                ]),
            },
            TreeNode {
                value: 2,
                children: Some(vec![
                    TreeNode {
                        value: 5,
                        children: None,
                    },
                    TreeNode {
                        value: 6,
                        children: Some(vec![TreeNode {
                            value: 7,
                            children: Some(vec![TreeNode {
                                value: 8,
                                children: Some(vec![TreeNode {
                                    value: 9,
                                    children: Some(vec![TreeNode {
                                        value: 10,
                                        children: None,
                                    }]),
                                }]),
                            }]),
                        }]),
                    },
                ]),
            },
        ]),
    }
}

广度优先搜索（BFS）

所有3个API的使用方法相同，只是借用模型不同，所以只给出一个示例。假设我们想将测试树中的所有值连接成一个字符串。我们可以这样做：

use tree_iterators_rs::{
	examples::create_example_tree,
	prelude::*
};

// Tree creation (see above documentation)
let root = create_example_tree();

let mut result = String::new();
for value in root.bfs() {
	result.push_str(&value.to_string());
	result.push_str(", ");
}

// result: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
println!("{}", result);

此代码也可以使用Rust的迭代器API编写

use tree_iterators_rs::{
	examples::create_example_tree,
	prelude::*
};

// Tree creation (see above documentation)
let root = create_example_tree();

let result = 
	root.bfs()
		.map(|val| val.to_string())
		.collect::<Vec<String>>()
		.join(", ");

// result: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
println!("{}", result);

不使用此crate的等效代码如下

use tree_iterators_rs::examples::create_example_tree;
use std::collections::VecDeque;

// Tree creation (see above documentation)
let root = create_example_tree();

let mut result = String::new();

let mut queue = VecDeque::new();
queue.push_back(root);
while queue.len() > 0 {
	if let Some(front) = queue.pop_front() {
		if let Some(children) = front.children {
			for child in children {
				queue.push_back(child);
			}
		}

		result.push_str(&front.value.to_string());
		result.push_str(", ");
	}
}

// result: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
println!("{}", result);

深度优先前序搜索（DFS Preorder）

与BFS示例类似，所有3个API的使用方法相同，只是借用模型不同，所以只给出一个示例。假设我们想将测试树中的所有值连接成一个字符串。我们可以这样做：

use tree_iterators_rs::{
	examples::create_example_tree,
	prelude::*
};

// Tree creation (see above documentation)
let root = create_example_tree();

let mut result = String::new();
for value in root.dfs_preorder() {
	result.push_str(&value.to_string());
	result.push_str(", ");
}

// result: 0, 1, 3, 4, 2, 5, 6, 7, 8, 9, 10,
println!("{}", result);

此代码也可以使用Rust的迭代器API编写

use tree_iterators_rs::{
	examples::create_example_tree,
	prelude::*
};

// Tree creation (see above documentation)
let root = create_example_tree();

let result = 
	root.dfs_preorder()
		.map(|val| val.to_string())
		.collect::<Vec<String>>()
		.join(", ");

// result: 0, 1, 3, 4, 2, 5, 6, 7, 8, 9, 10
println!("{}", result);

不使用此crate的等效代码如下

use tree_iterators_rs::examples::create_example_tree;

// Tree creation (see above documentation)
let root = create_example_tree();

let mut result = String::new();

let mut stack = vec![root];
while stack.len() > 0 {
	if let Some(top) = stack.pop() {
		if let Some(mut children) = top.children {
			children.reverse();
			for child in children {
				stack.push(child);
			}
		}

		result.push_str(&top.value.to_string());
		result.push_str(", ");
	}
}

// result: 0, 1, 3, 4, 2, 5, 6, 7, 8, 9, 10,
println!("{}", result);

仅二叉树 - 深度优先中序搜索（DFS In Order）

与前面的示例类似，所有3个API的使用方法相同，只是借用模型不同，所以只给出一个示例。假设我们想将测试树中的所有值连接成一个字符串。我们可以这样做：

use tree_iterators_rs::{
	examples::create_example_binary_tree,
	prelude::*
};

// Tree creation (see above documentation)
let root = create_example_binary_tree();

let mut result = String::new();
for value in root.dfs_inorder() {
	result.push_str(&value.to_string());
	result.push_str(", ");
}

// result: 3, 1, 4, 0, 5, 2, 7, 9, 10, 8, 6,
println!("{}", result);

此代码也可以使用Rust的迭代器API编写

use tree_iterators_rs::{
	examples::create_example_binary_tree,
	prelude::*
};

// Tree creation (see above documentation)
let root = create_example_binary_tree();

let result = root.dfs_preorder()
	.map(|val| val.to_string())
	.collect::<Vec<String>>()
	.join(", ");

// result: 3, 1, 4, 0, 5, 2, 7, 9, 10, 8, 6
println!("{}", result);

不使用此crate的等效代码如下。请注意，dfs_inorder API不使用递归，因此不会产生此示例中的栈帧开销。为了示例的简洁性，选择了递归。Rust的所有权模型很难用于此遍历类型，会使示例比必要的更复杂。

use tree_iterators_rs::{
	examples::create_example_binary_tree,
	prelude::*
};

fn dfs_inorder(node: Option<Box<BinaryTreeNode<usize>>>, result: &mut String) {
	match node {
		None => {}
		Some(node) => {
			dfs_inorder(node.left, result);
			result.push_str(&node.value.to_string());
			result.push_str(", ");
			dfs_inorder(node.right, result)
		}
	}            
}

// Tree creation (see above documentation)
let root = create_example_binary_tree();

let mut result = String::new();
dfs_inorder(Some(Box::new(root)), &mut result);

// result: 3, 1, 4, 0, 5, 2, 7, 9, 10, 8, 6,
println!("{}", result);

深度优先后序搜索（DFS Postorder）

与BFS和其他DFS示例类似，这3个API的使用方法除了借用模型外都是相同的，所以这里只给出一个示例。假设我们想将测试树中的所有值连接成一个字符串。我们可以这样做：

use tree_iterators_rs::{
	examples::create_example_tree,
	prelude::*
};

// Tree creation (see above documentation)
let root = create_example_tree();

let mut result = String::new();
for value in root.dfs_postorder() {
	result.push_str(&value.to_string());
	result.push_str(", ");
}

// result: 3, 4, 1, 5, 10, 9, 8, 7, 6, 2, 0,
println!("{}", result);

此代码也可以使用Rust的迭代器API编写

use tree_iterators_rs::{
	examples::create_example_tree,
	prelude::*
};

// Tree creation (see above documentation)
let root = create_example_tree();

let result = 
	root.dfs_postorder()
		.map(|val| val.to_string())
		.collect::<Vec<String>>()
		.join(", ");

// result: 3, 4, 1, 5, 10, 9, 8, 7, 6, 2, 0
println!("{}", result);

如果不使用这个crate，等价的代码如下。需要注意的是，dfs_postorder API不使用递归，因此不会产生这个示例中栈帧的额外开销。出于示例的简洁性考虑，这里选择了递归。Rust的所有权模型在处理这种遍历类型时比较困难，会使示例变得比必要的更复杂。

use tree_iterators_rs::{
	examples::create_example_tree,
	prelude::*
};

fn dfs_postorder(node: TreeNode<usize>, result: &mut String) {
	if let Some(children) = node.children {
		for child in children {
			dfs_postorder(child, result);
		}
	}

	result.push_str(", ");
	result.push_str(&node.value.to_string());
}

// Tree creation (see above documentation)
let root = create_example_tree();

let mut result = String::new();
dfs_postorder(root, &mut result);

// result: 3, 4, 1, 5, 10, 9, 8, 7, 6, 2, 0,
println!("{}", result);

迭代器修改器

附加祖先

attach_ancestors() 是一个可以在上述任何API之后调用的方法，可以将迭代器结构改变为返回包含树中所有祖先和当前值的切片。如果调用其中一个，那么（现在是流式的）迭代器将产生一个切片，其中索引为0的项是根值，索引为 len() - 1 的项是当前值，而中间的项是其他祖先。例如，当我们遍历到值为10的位置（参见上方文档）时，切片看起来是这样的：[0, 2, 6, 7, 8, 9, 10]。

例如，我们可以使用这个API来过滤出示例树中所有祖先和当前节点都是偶数的值。

注意：务必添加对 streaming_iterator::StreamingIterator 的使用语句，以引入从 streaming_iterator crate 中的 filter、map、reduce、for_each 等方法。

use streaming_iterator::StreamingIterator;
use tree_iterators_rs::{
	examples::create_example_tree,
	prelude::*
};

let root = create_example_tree();
let mut result = String::new();

root.dfs_preorder_iter()
	.attach_ancestors()
	.filter(|slice| 
		slice.iter().all(|value| **value % 2 == 0)
	)
	.map(|slice| slice[slice.len() - 1])
	.for_each(|value| {
		result.push(' ');
		result.push_str(&value.to_string())
	});

// result: 0 2 6
println!("{}", result);

如果我们使用二叉树，我们也可以用顺序迭代器做到同样的效果。

use streaming_iterator::StreamingIterator;
use tree_iterators_rs::{
	examples::create_example_binary_tree,
	prelude::*
};

let root = create_example_binary_tree();
let mut result = String::new();

root.dfs_inorder_iter()
	.attach_ancestors()
	.filter(|slice| 
		slice.iter().all(|value| **value % 2 == 0)
	)
	.map(|slice| slice[slice.len() - 1])
	.for_each(|value| {
		result.push(' ');
		result.push_str(&value.to_string())
	});

// result: 0 2 6
println!("{}", result);

我们也可以用后序迭代器来实现，以得到反向的结果。

use streaming_iterator::StreamingIterator;
use tree_iterators_rs::{
	examples::create_example_tree,
	prelude::*
};

let root = create_example_tree();
let mut result = String::new();

root.dfs_postorder_iter()
	.attach_ancestors()
	.filter(|slice| 
		slice.iter().all(|value| **value % 2 == 0)
	)
	.map(|slice| slice[slice.len() - 1])
	.for_each(|value| {
		result.push(' ');
		result.push_str(&value.to_string())
	});

// result: 6 2 0
println!("{}", result);

我们还可以用广度优先搜索来实现，这恰好与深度优先前序迭代器得到相同的结果。

use streaming_iterator::StreamingIterator;
use tree_iterators_rs::{
	examples::create_example_tree,
	prelude::*
};

let root = create_example_tree();
let mut result = String::new();

root.bfs_iter()
	.attach_ancestors()
	.filter(|slice| 
		slice.iter().all(|value| **value % 2 == 0)
	)
	.map(|slice| slice[slice.len() - 1])
	.for_each(|value| {
		result.push(' ');
		result.push_str(&value.to_string())
	});

// result: 0 2 6
println!("{}", result);

叶子节点

leaves() 是一个可以在上述任何API之后调用（包括 attach_ancestors() - 见这里）的方法，可以将迭代器结构改为仅返回树中叶子节点。在示例树（参见上方文档）中，这将始终得到序列 3, 4, 5, 10。一旦调用此方法，迭代器将转换为广度优先（如果迭代器之前是广度优先）或深度优先后序搜索（如果迭代器之前是前序、中序或后序深度优先搜索之一）。

在示例中，我将使用深度优先前序搜索，但这种方法适用于所有遍历类型。如果您只想接收树的叶子节点，可以立即调用此方法：

use tree_iterators_rs::{
	examples::create_example_tree,
	prelude::*
};

let root = create_example_tree();

let result = root.dfs_preorder()
	.leaves()
	.map(|val| val.to_string())
	.collect::<Vec<String>>()
	.join(", ");

// result: 3, 4, 5, 10
println!("{}", result);

或者，此方法可以用作执行正常遍历并在其中途切换到仅包含叶子的遍历。可以这样操作（所有遍历类型都支持此操作）：

use tree_iterators_rs::{
	examples::create_example_tree,
	prelude::*
};

let root = create_example_tree();

let mut dfs_preorder = root.dfs_preorder();

let mut results = Vec::new();
// take the first 2 non-leaves before switching to a leaves-only iterator
results.push(dfs_preorder.next().unwrap().to_string());
results.push(dfs_preorder.next().unwrap().to_string());

// once leaves is called, iteration switches to a depth-first postorder search
for leaf in dfs_preorder.leaves() {
	results.push(leaf.to_string());
}

let result = results.join(", ");

// result: 0, 1, 3, 4, 5, 10,
println!("{}", result);

自定义树节点实现

这个crate的API由3个特质提供支持。特质包括

OwnedTreeNode/OwnedBinaryTreeNode - 这些特质为 bfs()、dfs_preorder()、dfs_inorder() 和 dfs_postorder() API 提供支持。
MutBorrowedTreeNode/MutBorrowedBinaryTreeNode - 这些特质为 bfs_iter_mut()、dfs_preorder_iter_mut()、dfs_inorder_iter_mut 和 dfs_postorder() API 提供支持。
BorrowedTreeNode 和 BorrowedBinaryTreeNode - 这些特质为 bfs_iter()、dfs_preorder_iter()、dfs_inorder_iter() 和 dfs_postorder_iter() API 提供了动力。

您可以挑选并实施您需要的特质。它们除了命名约定和从它们所需方法实现返回的值的所有权外，其余都相同。

示例

例如，我们可以实现另一个 TreeNode 变体，它使用链表来存储其子节点。这里所有的代码都是 MIT 许可的，您可以根据许可证的条件直接复制或修改它。

use tree_iterators_rs::prelude::*;
use std::collections::LinkedList;

struct LLTreeNode<T> {
    value: T,
    children: LinkedList<LLTreeNode<T>>
}

这是一个不错的开始，但现实地讲，我们希望它实现我们可用的所有树遍历 API。

拥有实现

我们可以从如下所示的 OwnedTreeNode 实现开始。由于我们选择使用 LinkedList 作为子属性，我们必须将其迭代器包装在 Some() Option 变体中。实现这一点的难点在于确定 LinkedList 的 into_iter() 方法返回类型的类型。

use tree_iterators_rs::prelude::*;
use std::collections::{
	LinkedList,
	linked_list::IntoIter
};

struct LLTreeNode<T> {
    value: T,
    children: LinkedList<LLTreeNode<T>>
}

impl<T> OwnedTreeNode for LLTreeNode<T> {
    type OwnedValue = T;
    type OwnedChildren = IntoIter<LLTreeNode<T>>;

    fn get_value_and_children(self) -> (Self::OwnedValue, Option<Self::OwnedChildren>) {
        (
            self.value,
            Some(self.children.into_iter())
        )
    }
}

现在我们已经实现了 OwnedTreeNode，我们的类型具有 bfs()、dfs_preorder() 和 dfs_postorder() 方法。

可变借用实现

可变借用实现与拥有的实现非常相似。唯一的不同之处在于 'Value' 关联类型已更改为可变引用，并且我们调用 iter_mut() 而不是 into_iter()。

use tree_iterators_rs::prelude::*;
use std::collections::{
	LinkedList,
	linked_list::IterMut
};

struct LLTreeNode<T> {
    value: T,
    children: LinkedList<LLTreeNode<T>>
}

impl<'a, T> MutBorrowedTreeNode<'a> for LLTreeNode<T> 
    where Self: 'a {

    type MutBorrowedValue = &'a mut T;
    type MutBorrowedChildren = IterMut<'a, LLTreeNode<T>>;

    fn get_value_and_children_iter_mut(&'a mut self) -> (Self::MutBorrowedValue, Option<Self::MutBorrowedChildren>) {
        (
            &mut self.value,
            Some(self.children.iter_mut())
        )
    }
}

现在我们已经实现了 MutBorrowedTreeNode，我们的类型具有 bfs_iter_mut()、dfs_preorder_iter_mut() 和 dfs_postorder_iter_mut() 方法。

借用实现

借用实现也与拥有的实现非常相似。唯一的不同之处在于 'Value' 关联类型已更改为不可变引用，并且我们调用 iter() 而不是 into_iter()。

use tree_iterators_rs::prelude::*;
use std::collections::{
	LinkedList,
	linked_list::Iter
};

struct LLTreeNode<T> {
    value: T,
    children: LinkedList<LLTreeNode<T>>
}

impl<'a, T> BorrowedTreeNode<'a> for LLTreeNode<T> 
    where Self: 'a {

    type BorrowedValue = &'a T;
    type BorrowedChildren = Iter<'a, LLTreeNode<T>>;

    fn get_value_and_children_iter(&'a self) -> (Self::BorrowedValue, Option<Self::BorrowedChildren>) {
        (
            &self.value,
            Some(self.children.iter())
        )
    }
}

现在我们已经实现了 BorrowedTreeNode，我们的类型具有 bfs_iter()、dfs_preorder_iter() 和 dfs_postorder_iter() 方法。

奇异用例

这个库在特质声明上故意非常宽松，因此它为一些相当奇异的数据转换和用例打开了大门。每个迭代器尽可能懒惰，并且只为树中的每个节点调用一次 get_value_and_children 方法变体。这意味着如果您选择的话，您可以在遍历过程中懒惰地构建/生成树。这为使用这个库做一些疯狂的事情打开了大门。我很乐意听到您想出的一些类似用例。请在此 GitHub 仓库上留下笔记/问题！

依赖项

~97–275KB