id_tree

一个用于创建和修改树结构的库。

概述

在此实现中，Tree 拥有所有的 Node，并且所有节点间的关联关系都通过 NodeId 管理的。

本库中的 Tree 只是最基本的树结构。它们不允许循环。它们不允许创建任意的图结构。节点间的边不关联任何权重。此外，每个 Node 都可以有任意数量的子 Node。

需要注意的是，此库不支持基于比较的 Node 插入。换句话说，这不是一个二叉搜索树（或其他任何类型的搜索树）库。它纯粹是一个用于以分层方式存储数据的库。调用者必须知道他们要构建的结构，然后使用此库来实现；此库不会为您做出这些结构决策。

示例用法

use id_tree::*;

fn main() {
    use id_tree::InsertBehavior::*;

    //      0
    //     / \
    //    1   2
    //   / \
    //  3   4
    let mut tree: Tree<i32> = TreeBuilder::new()
        .with_node_capacity(5)
        .build();

    let root_id: NodeId = tree.insert(Node::new(0), AsRoot).unwrap();
    let child_id: NodeId = tree.insert(Node::new(1), UnderNode(&root_id)).unwrap();
    tree.insert(Node::new(2), UnderNode(&root_id)).unwrap();
    tree.insert(Node::new(3), UnderNode(&child_id)).unwrap();
    tree.insert(Node::new(4), UnderNode(&child_id)).unwrap();

    println!("Pre-order:");
    for node in tree.traverse_pre_order(&root_id).unwrap() {
        print!("{}, ", node.data());
    }
    // results in the output "0, 1, 3, 4, 2, "
}

项目目标

• 允许调用者尽可能多地控制分配（通过预分配）
• 快速的 Node 插入和删除
• 任意 Tree 结构的创建和操作

非目标

• 任意 Graph 结构的创建和操作
• 任何类型的基于比较的节点插入

贡献者

• Cecile Tonglet
• Drakulix
• 石博文