https://crates.io/crates/trees
The "trees" crate aims at:
-
expressing hierarchical data conveniently and compactly.
-
storing and manipulating tree-like data structure the simple way.
The implementation is straightforward:
-
none-intrusive nodes with child-sibling pointers.
-
children nodes, or forest, are singly-linked circular list.
Quick start
- Tree notation
use trees::tr; // tr stands for tree
tr(0); // A single tree node with data 0. tr(0) has no children
tr(0) /tr(1); // tr(0) has one child tr(1)
tr(0) /tr(1)/tr(2); // tr(0) has children tr(1) and tr(2)
// tr(0) has children tr(1) and tr(4), while tr(1) has children tr(2) and tr(3), and tr(4) has children tr(5) and tr(6).
// The spaces and carriage returns are for pretty format and do not make sense.
tr(0)
/( tr(1) /tr(2)/tr(3) )
/( tr(4) /tr(5)/tr(6) );
- Forest notation
use trees::{tr,fr}; // fr stands for forest
fr::<i32>(); // An empty forest
fr() - tr(1); // forest has one child tr(1)
- tr(1); // forest has one child tr(1). The fr() can be omitted. The Neg operator for Tree converts the tree to a forest.
- tr(1) - tr(2); // forest has child tr(1) and tr(2)
tr(1) - tr(2); // forest has child tr(1) and tr(2). The leading neg can be omitted.
// forest has children tr(1) and tr(4), while tr(1) has children tr(2) and tr(3), and tr(4) has children tr(5) and tr(6).
-( tr(1) /tr(2)/tr(3) )
-( tr(4) /tr(5)/tr(6) );
// A tree tr(0) whose children equal to the forest descripted above.
tr(0) /(
-( tr(1) /( -tr(2)-tr(3) ) )
-( tr(4) /( -tr(5)-tr(6) ) )
);
- Preorder traversal
use std::string::{String,ToString};
use trees::{tr,Node};
fn tree_to_string<T:ToString>( node: &Node<T> ) -> String {
if node.is_leaf() {
node.data.to_string()
} else {
node.data.to_string()
+ &"( "
+ &node.children()
.fold( String::new(),
|s,c| s + &tree_to_string(c) + &" " )
+ &")"
}
}
let tree = tr(0) /( tr(1) /tr(2)/tr(3) ) /( tr(4) /tr(5)/tr(6) );
assert_eq!( tree_to_string( &tree ), "0( 1( 2 3 ) 4( 5 6 ) )" );