Tree-ds

此库提供了一个树数据结构，可用于在Rust中表示层次化数据。该库允许您对树执行以下操作

• 列举树中的所有节点
• 列举树的某个部分
• 在树中查找节点
• 在树中查找某个部分
• 将节点添加到树的某个位置
• 从树中删除节点
• 修剪树的某个部分
• 将树的整个部分嫁接到另一个树上
• 查找任何节点的根
• 查找两个节点的最低公共祖先

为什么使用这个库？

有众多crate提供了Rust中的树数据结构，但这个库的独特之处在于它提供了一个功能丰富、易于使用且API简单的树数据结构。该库也具有良好的文档记录，并拥有全面的测试套件，确保其按预期工作。最重要的是，该库被设计为快速高效，适用于性能关键的应用。

用法

将以下内容添加到您的Cargo.toml文件中

[dependencies]
tree-ds = "0.1"

节点

库的基本构建块是Node结构。Node结构是一个泛型结构，可以持有任何类型的数据。创建Node结构如下

use tree_ds::prelude::*;

let node: Node<String, i32> = Node::new("Root Node".to_string(), Some(100));

可选地，该crate提供了一个auto_id特性来自动为节点生成ID。当您不关心节点的ID，并希望避免管理ID的开销时，这非常有用。要启用auto_id特性，将以下内容添加到您的Cargo.toml文件中

[dependencies]
tree-ds = { version = "0.1", features = ["auto_id"] }

然后您可以创建一个节点如下

use tree_ds::prelude::*;

// Not that in this case, the `Q` type parameter should be of type `AutomatedId` or any other type that implements the `From<u128>` trait.
let node: Node<AutomatedId, &str> = Node::new_with_auto_id(Some("Some Node Value"));

注意：在no_std环境中生成的节点ID在序列化和反序列化以及磁盘持久化时可能不会是唯一的。这是因为no_std环境无法访问std::time模块以生成唯一的ID。相反，它使用sequential_gen crate中的SimpleGenerator来生成唯一的ID。

树

《Tree`结构体是用于表示树的主要结构体。`Tree`结构体是对树中节点所持有的数据类型通用的。`Tree`结构体可以按照以下方式创建：

use tree_ds::prelude::*;

let mut tree: Tree<String, i32> = Tree::new(Some("The Tree Name"));
// Proceed to build the tree by adding nodes to it.

以下是如何使用此库的一个简单示例：

use tree_ds::prelude::{Node, NodeRemovalStrategy, Result, Tree};

fn main() -> Result<()> {
	let mut tree = Tree::new(Some("Finances Tree"));
	let root = tree.add_node(Node::new("Risk".to_string(), Some(5000)), None)?;
	let fixed_income_node = tree.add_node(Node::new("Fixed Income".to_string(), Some(2000)), Some(&root))?;
	let equity_node = tree.add_node(Node::new("Equity".to_string(), Some(3000)), Some(&root))?;
	let debt_node = tree.add_node(Node::new("Debt".to_string(), Some(1000)), Some(&fixed_income_node))?;
	let mutual_funds_node = tree.add_node(Node::new("Mutual Funds".to_string(), Some(1000)), Some(&equity_node))?;
	let stocks_node = tree.add_node(Node::new("Stocks".to_string(), Some(2000)), Some(&equity_node))?;
	tree.add_node(Node::new("Debt Mutual Funds".to_string(), Some(500)), Some(&debt_node))?;
	tree.add_node(Node::new("Equity Mutual Funds".to_string(), Some(500)), Some(&mutual_funds_node))?;
	tree.add_node(Node::new("Large Cap Stocks".to_string(), Some(1000)), Some(&stocks_node))?;
	tree.add_node(Node::new("Mid Cap Stocks".to_string(), Some(1000)), Some(&stocks_node))?;
	tree.add_node(Node::new("Small Cap Stocks".to_string(), Some(1000)), Some(&stocks_node))?;

	println!("{}", tree);


	tree.remove_node(&stocks_node, NodeRemovalStrategy::RemoveNodeAndChildren)?;
	println!("After Removing The Stocks Node");
	println!("*******************");
	println!("{}", tree);


	let equity_sub_tree = tree.get_subtree(&equity_node, None)?;
	println!("{}", equity_sub_tree);
	Ok(())
}

这将输出：

Finances Tree
*************
Risk: 5000
├── Fixed Income: 2000
│   └── Debt: 1000
│       └── Debt Mutual Funds: 500
└── Equity: 3000
    ├── Mutual Funds: 1000
    │   └── Equity Mutual Funds: 500
    └── Stocks: 2000
        ├── Large Cap Stocks: 1000
        ├── Mid Cap Stocks: 1000
        └── Small Cap Stocks: 1000

After Removing The Stocks Node
*******************
Finances Tree
*************
Risk: 5000
├── Fixed Income: 2000
│   └── Debt: 1000
│       └── Debt Mutual Funds: 500
└── Equity: 3000
    └── Mutual Funds: 1000
        └── Equity Mutual Funds: 500

Equity
******
Equity: 3000
└── Mutual Funds: 1000
    └── Equity Mutual Funds: 500

遍历

您可以使用`traverse`方法遍历树。`traverse`方法返回一个迭代器，允许您以任何顺序遍历树。以下示例展示了如何以先序遍历树：

use tree_ds::prelude::{Node, Result, Tree, TraversalStrategy};

fn main() -> Result<()> {
	let mut tree = Tree::new(None);
	let node_1 = tree.add_node(Node::new(1, Some(2)), None)?;
	let node_2 = tree.add_node(Node::new(2, Some(3)), Some(&node_1))?;
	let node_3 = tree.add_node(Node::new(3, Some(6)), Some(&node_1))?;
	let node_4 = tree.add_node(Node::new(4, Some(5)), Some(&node_2))?;
	let node_5 = tree.add_node(Node::new(5, Some(6)), Some(&node_2))?;
	let node_6 = tree.add_node(Node::new(6, Some(7)), Some(&node_3))?;
	let preorder_nodes = tree.traverse(&node_1, TraversalStrategy::PreOrder)?;
	let expected_preorder = vec![node_1, node_2, node_4, node_5, node_3, node_6];
	assert_eq!(preorder_nodes, expected_preorder);

	let in_order_nodes = tree.traverse(&node_1, TraversalStrategy::InOrder)?;
	let expected_in_order = vec![node_4, node_2, node_5, node_1, node_3, node_6];
	assert_eq!(in_order_nodes, expected_in_order);

	let post_order_nodes = tree.traverse(&node_1, TraversalStrategy::PostOrder)?;
	let expected_post_order = vec![node_4, node_5, node_2, node_6, node_3, node_1];
	assert_eq!(post_order_nodes, expected_post_order);
	Ok(())
}

您还可以在遍历树时对迭代器返回的节点执行操作。以下示例展示了如何以先序遍历树并对节点执行操作：

let nodes = tree.traverse(&node_id, TraversalStrategy::PreOrder)?
    .iter()
    .map(|node| {
        println!("{}", node);
        node
    })
    .collect::<Vec<_>>();

`no_std`环境

此crate支持`no_std`环境。要在`no_std`环境中使用此crate，您需要启用`no_std`特性。您可以通过在`Cargo.toml`文件中添加以下内容来实现：

[dependencies]
tree-ds = { version = "0.1", features = ["no_std"] }

所有其他特性在`no_std`环境中也得到同样支持。

路线图

• 添加对更多树操作的支持。
  • 添加节点旋转。
• 添加一个宏，可以从领域特定语言（DSL）创建树。
• 添加对加权节点的支持。

许可证

本项目采用MIT许可证 - 有关详细信息，请参阅LICENSE文件。

变更日志

请参阅CHANGELOG以获取最新更改。