Struct Tree

pub struct Tree<Q, T>
where
    Q: PartialEq + Eq + Clone,
    T: PartialEq + Eq + Clone,
{ /* private fields */ }

A tree data structure.

This struct represents a tree data structure. A tree is a data structure that consists of nodes connected by edges. Each node has a parent node and zero or more child nodes. The tree has a root node that is the topmost node in the tree. The tree can be used to represent hierarchical data structures such as file systems, organization charts, and family trees. A tree can have any number of nodes and each node can have any number of children. The tree can be traversed in different orders such as pre-order, post-order, and in-order. The tree can be named for easy identification when working with multiple trees or subtrees.

Type Parameters

• Q - The type of the node id.
• T - The type of the node value.

Example

let tree: Tree<i32, i32> = Tree::new(Some("Sample Tree"));

Implementations

impl<Q, T> Tree<Q, T>

where Q: PartialEq + Eq + Clone + Display + Hash + Ord, T: PartialEq + Eq + Clone,

pub fn new(tree_name: Option<&str>) -> Self

Create a new tree.

This method creates a new tree with no nodes.

Returns

A new tree with no nodes.

Example

let tree: Tree<i32, i32> = Tree::new(Some("Sample Tree"));

pub fn add_node(&mut self, node: Node<Q, T>, parent_id: Option<&Q>) -> Result<Q>

Add a node to the tree.

This method adds a node to the tree. The node is added as a child of the parent node with the given parent id. If the parent id is None, the node is added as a root node. The node id is used to identify the node and the value is the value of the node. The value can be used to store any data that you want to associate with the node.

Arguments

• node_id - The id of the node.
• value - The value of the node.
• parent_id - The id of the parent node. If None, the node is added as a root node.

Returns

The id of the node that was added to the tree. However, if no parent id is provided and the tree already has a root node, an error is returned.

Example

let mut tree: Tree<i32, i32> = Tree::new(Some("Sample Tree"));
let node_id = tree.add_node(Node::new(1, Some(2)), None);

assert!(node_id.is_ok());
// This should return an error because the tree already has a root node.
let another_node_id = tree.add_node(Node::new(2, Some(3)), None);
assert!(another_node_id.is_err());

pub fn get_name(&self) -> Option<&str>

Get the name of the tree.

This method gets the name of the tree.

Returns

The name of the tree.

Example

let tree: Tree<i32, i32> = Tree::new(Some("Sample Tree"));

assert_eq!(tree.get_name(), Some("Sample Tree"));

pub fn rename(&mut self, name: Option<&str>)

Set the name of the tree.

This method sets the name of the tree.

Arguments

• name - The name of the tree.

Example

let mut tree: Tree<i32, i32> = Tree::new(Some("Sample Tree"));
tree.rename(Some("New Name"));
assert_eq!(tree.get_name(), Some("New Name"));

pub fn get_node_by_id(&self, node_id: &Q) -> Option<Node<Q, T>>

Get a node in the tree.

This method gets the node with the given node id in the tree.

Arguments

• node_id - The id of the node.

Returns

The node with the given node id in the tree or None if the node is not found.

Example

let mut tree: Tree<i32, i32> = Tree::new(Some("Sample Tree"));

let node = Node::new(1, Some(2));
let node_id = tree.add_node(node.clone(), None).unwrap();

assert_eq!(tree.get_node_by_id(&node_id), Some(node));

pub fn get_root_node(&self) -> Option<Node<Q, T>>

Get the root node of the tree.

This method gets the root node of the tree. The root node is the topmost node in the tree. The root node has no parent node.

Returns

The root node of the tree or None if the tree has no root node.

Example

let mut tree: Tree<i32, i32> = Tree::new(Some("Sample Tree"));

let node = Node::new(1, Some(2));
tree.add_node(node.clone(), None).unwrap();

assert_eq!(tree.get_root_node(), Some(node));

pub fn get_node_height(&self, node_id: &Q) -> Result<i32>

Get the height of the node.

This method gets the height of the node. The height of the node is the number of edges present in the longest path connecting the node to a leaf node.

Returns

The height of the node. If the node is a leaf node, the height is 0. This method returns an error if the node is not found in the tree.

Example

let mut tree: Tree<i32, i32> = Tree::new(Some("Sample Tree"));

let node_1 = tree.add_node(Node::new(1, Some(2)), None).unwrap();
let node_2 = tree.add_node(Node::new(2, Some(3)), Some(&node_1)).unwrap();
let node_3 = tree.add_node(Node::new(3, Some(6)), Some(&node_2)).unwrap();

assert!(tree.get_node_height(&node_2).is_ok());
assert_eq!(tree.get_node_height(&node_2).unwrap(), 1);

pub fn get_node_depth(&self, node_id: &Q) -> Result<i32>

Get the depth of a node in the tree.

This method gets the depth of a node in the tree. The depth of a node is the length of the path from the root node to the node. The depth of the node is the number of edges on the path from the root node to the node.

Arguments

• node_id - The id of the node.

Returns

The depth of the node in the tree. This method returns an error if the node is not found in the tree.

Example

let mut tree: Tree<i32, i32> = Tree::new(Some("Sample Tree"));

let node_1 = tree.add_node(Node::new(1, Some(2)), None).unwrap();
let node_2 = tree.add_node(Node::new(2, Some(3)), Some(&node_1)).unwrap();
let node_3 = tree.add_node(Node::new(3, Some(6)), Some(&node_2)).unwrap();
let depth_result = tree.get_node_depth(&node_3);
assert!(depth_result.is_ok());
assert_eq!(depth_result.unwrap(), 2);

pub fn get_ancestor_ids(&self, node_id: &Q) -> Result<Vec<Q>>

Get the ancestors of a node in the tree.

This method gets the ancestors of a node in the tree. The ancestors of a node are all the nodes that are on the path from the root node to the node, not including the node itself.

Arguments

• node_id - The id of the node.

Returns

The ancestors of the node from closest to furthest. This method returns an error if the node is not found in the tree.

Example

let mut tree: Tree<i32, i32> = Tree::new(Some("Sample Tree"));

let node_1 = tree.add_node(Node::new(1, Some(2)), None).unwrap();
let node_2 = tree.add_node(Node::new(2, Some(3)), Some(&node_1)).unwrap();
let node_3 = tree.add_node(Node::new(3, Some(6)), Some(&node_2)).unwrap();
let depth_result = tree.get_ancestor_ids(&node_3);
assert!(depth_result.is_ok());
assert_eq!(depth_result.unwrap(), vec![2, 1]);

pub fn get_height(&self) -> Result<i32>

Get the height of the tree.

This method gets the height of the tree. The height of the tree is the length of the longest path from the root node to a leaf node. The height of the tree is the number of edges on the longest path from the root node to a leaf node.

Returns

The height of the tree. This method returns an error if the tree has no root node.

Example

let mut tree: Tree<i32, i32> = Tree::new(Some("Sample Tree"));

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_2))?;
let tree_height = tree.get_height();
assert!(tree_height.is_ok());
assert_eq!(tree_height?, 2);

pub fn get_node_degree(&self, node_id: &Q) -> Result<i32>

Get the degree of a node in the tree.

This method gets the degree of a node in the tree. The degree of a node is the number of children that the node has.

Arguments

• node_id - The id of the node.

Returns

The degree of the node in the tree. This method returns an error if the node is not found in the tree.

Example

let mut tree: Tree<i32, i32> = Tree::new(Some("Sample Tree"));

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))?;

assert_eq!(tree.get_node_degree(&node_1)?, 2);
assert_eq!(tree.get_node_degree(&node_2)?, 0);
assert_eq!(tree.get_node_degree(&node_3)?, 0);

pub fn get_nodes(&self) -> &Nodes<Q, T>

Get the nodes in the tree.

This method gets the nodes in the tree.

Returns

The nodes in the tree.

Example

let mut tree: Tree<i32, i32> = Tree::new(Some("Sample Tree"));

let node = Node::new(1, Some(2));
tree.add_node(node.clone(), None).unwrap();

assert_eq!(tree.get_nodes().len(), 1);

pub fn remove_node( &mut self, node_id: &Q, strategy: NodeRemovalStrategy, ) -> Result<()>

Remove a node from the tree.

This method removes a node from the tree. The node is removed using the given removal strategy. The removal strategy determines how the node and its children are removed from the tree. The RetainChildren strategy retains the children of the node when the node is removed. The RemoveNodeAndChildren strategy removes the node and its children when the node is removed.

Arguments

• node_id - The id of the node to remove.
• strategy - The strategy to use when removing the node.

Returns

An error if the node is not found in the tree or if the node is the root node and the removal strategy is RetainChildren.

Example

let mut tree: Tree<i32, i32> = Tree::new(Some("Sample Tree"));

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))?;
tree.add_node(Node::new(3, Some(6)), Some(&node_2))?;

tree.remove_node(&node_2, NodeRemovalStrategy::RetainChildren)?;
assert_eq!(tree.get_nodes().len(), 2);

pub fn get_subtree( &self, node_id: &Q, generations: Option<i32>, ) -> Result<SubTree<Q, T>>

Get a subsection of the tree.

This method gets a subsection of the tree starting from the node with the given node id. The subsection is a list of nodes that are descendants of the node with the given node id upto the given number of descendants. If the number of descendants is None, all the descendants of the node are included in the subsection.

Arguments

• node_id - The id of the node to get the subsection from.
• generations - The number of descendants to include in the subsection. If None, all the descendants of the node are included in the subsection.

Returns

The subsection of the tree starting from the node with the given node id.

Example

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_2))?;

let subsection = tree.get_subtree(&node_2, None)?;
assert_eq!(subsection.get_nodes().len(), 2);

pub fn get_sibling_ids(&self, node_id: &Q, inclusive: bool) -> Result<Vec<Q>>

Get the siblings of a node in the tree.

This method gets the siblings of a node in the tree. The siblings of a node are the children that share the same parent as the node.

Arguments

• node_id - The id of the node to get the siblings of.
• inclusive - A flag that indicates whether to include the node in the siblings list.

Returns

The siblings of the node in the tree.

Example

let mut tree: Tree<i32, i32> = Tree::new(Some("Sample Tree"));
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))?;
tree.add_node(Node::new(3, Some(6)), Some(&node_1))?;
tree.add_node(Node::new(4, Some(7)), Some(&node_1))?;

let siblings = tree.get_sibling_ids(&node_2, false)?;
assert_eq!(siblings.len(), 2);

let siblings = tree.get_sibling_ids(&node_2, true)?;
assert_eq!(siblings.len(), 3);

pub fn add_subtree(&mut self, node_id: &Q, subtree: SubTree<Q, T>) -> Result<()>

Add a subsection to the tree.

This method adds a subsection to the tree. The subsection is a list of nodes that are descendants of the node with the given node id. The subsection is added as children of the node with the given node id.

Arguments

• node_id - The id of the node to add the subsection to.
• subtree - The subsection to add to the tree.

Returns

This function return an error if:

• The node is not found in the tree.
• The subsection has no root node.

Example

let mut tree: Tree<i32, i32> = Tree::new(Some("Sample Tree"));
let node_id = tree.add_node(Node::new(1, Some(2)), None)?;
let mut subtree = SubTree::new(Some("Sample Tree"));
let node_2 = subtree.add_node(Node::new(2, Some(3)), None)?;
subtree.add_node(Node::new(3, Some(6)), Some(&node_2))?;
tree.add_subtree(&node_id, subtree)?;
assert_eq!(tree.get_nodes().len(), 3);

pub fn traverse(&self, node_id: &Q, order: TraversalStrategy) -> Result<Vec<Q>>

Traverse the subtree from the given node.

This method traverses the subtree from the given node in the given order.

Arguments

• order - The order to traverse the tree.
• node_id - The id of the node to start the traversal from.

Returns

The nodes in the tree in the given order. This method returns an error if the node is not found in the tree.

Example

let mut tree: Tree<i32, i32> = Tree::new(Some("Sample Tree"));
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_2))?;

let ordered_nodes = tree.traverse(&node_1, TraversalStrategy::PreOrder)?;

Trait Implementations

impl<Q, T> Clone for Tree<Q, T>

where Q: PartialEq + Eq + Clone + Clone, T: PartialEq + Eq + Clone + Clone,

fn clone(&self) -> Tree<Q, T>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<Q, T> Debug for Tree<Q, T>

where Q: PartialEq + Eq + Clone + Debug, T: PartialEq + Eq + Clone + Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<Q, T> Default for Tree<Q, T>

where Q: PartialEq + Eq + Clone, T: PartialEq + Eq + Clone,

fn default() -> Self

Create a new tree with no nodes.

impl<Q, T> Display for Tree<Q, T>

where Q: PartialEq + Eq + Clone + Display + Hash + Ord, T: PartialEq + Eq + Clone + Display + Default,

fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult

Print the tree.

impl<Q, T> Drop for Tree<Q, T>

where Q: PartialEq + Eq + Clone, T: PartialEq + Eq + Clone,

fn drop(&mut self)

Executes the destructor for this type.

impl<Q, T> Hash for Tree<Q, T>

where Q: PartialEq + Eq + Clone + Hash, T: PartialEq + Eq + Clone + Hash,

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<Q, T> PartialEq for Tree<Q, T>

where Q: PartialEq + Eq + Clone + PartialEq, T: PartialEq + Eq + Clone + PartialEq,

fn eq(&self, other: &Tree<Q, T>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<Q, T> Eq for Tree<Q, T>

where Q: PartialEq + Eq + Clone + Eq, T: PartialEq + Eq + Clone + Eq,

impl<Q, T> StructuralPartialEq for Tree<Q, T>

where Q: PartialEq + Eq + Clone, T: PartialEq + Eq + Clone,