dsa/data_structures/
tree.rs

1use std::cmp::Ordering;
2
3/// A tree node that holds a value of type `T` generic
4///
5/// This structure represents a single node in a binary tree. It holds a value of type `T` and can
6/// be compared to other `TreeNode`s based on the value it contains.
7#[derive(Eq, Hash, PartialEq, Clone, Debug)]
8pub struct TreeNode<T> {
9    /// The `value` of this `TreeNode`
10    pub value: T,
11}
12impl<T> TreeNode<T> {
13    /// Creates a new `TreeNode` with the given `value`
14    ///
15    /// # Parameters
16    /// - `value`: The value to be stored in this `TreeNode`
17    /// 
18    /// # Returns
19    /// - A new instance of `TreeNode` containing the provided `value`
20    pub fn new(value: T) -> Self {
21        TreeNode {
22            value,
23        }
24    }
25}
26impl<T: Ord> PartialOrd for TreeNode<T> {
27    /// Compares two `TreeNode`s for partial ordering.
28    /// 
29    /// # Parameters
30    /// - other: Another `TreeNode` object to compare this `TreeNode`s value
31    /// 
32    /// # Returns
33    /// - An optional `Ordering` object that indicates whether there exists an
34    ///     `Ordering` where this `TreeNode` is less than, equal to, or greater than
35    ///     the other `TreeNode`.
36    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
37        self.value.partial_cmp(&other.value)
38    }
39}
40impl<T: Ord> Ord for TreeNode<T> {
41    /// Compares two `TreeNode`s for total ordering.
42    ///
43    /// # Parameters
44    /// - `other`: Another `TreeNode` instance to compare the value to this `TreeNode`'s
45    /// value
46    /// 
47    /// # Returns
48    /// - An `Ordering` object that indicates whether the value of
49    /// this `TreeNode` is less than, equal to, or greater than the value
50    /// of the other `TreeNode`
51    fn cmp(&self, other: &Self) -> Ordering {
52        self.value.cmp(&other.value)
53    }
54}
55
56/// A `BinaryTree` data structure that contains a `TreeNode` and two 
57/// optional child nodes (`left` and `right`)
58///
59/// This structure represents a binary tree where each node contains a `TreeNode` value and two
60/// child nodes, `left` and `right`, which are either `Some(Box<BinaryTree<T>>)`, or `None` if the
61/// node has no children.
62pub struct BinaryTree<T> {
63    /// The root of the `BinaryTree`
64    pub root: TreeNode<T>,
65    /// The left child of the `BinaryTree`, or `None` if there is no left child
66    pub left: Option<Box<BinaryTree<T>>>,
67    /// The right child of the `BinaryTree`, or `None` if there is no right child
68    pub right: Option<Box<BinaryTree<T>>>,
69}
70impl<T> BinaryTree<T> {
71    /// Creates a new `BinaryTree` with the given node, left child, and right child.
72    /// 
73    /// # Parameters
74    /// - `root`: A `TreeNode` object that represents the topmost 
75    /// node of this `BinaryTree`
76    /// - `left`: An optional `BinaryTree` `Box` pointer that points to the
77    /// left child of this `BinaryTree`, or `None` if no left child exists
78    /// - `right`: An optional `BinaryTree` `Box` pointer that points to the
79    /// right child of this `BinaryTree`, or `None` if no right child exists
80    /// 
81    /// # Returns
82    /// - A new instance of a `BinaryTree` containing the given `root` node,
83    /// `left` child, and `right` child
84    /// 
85    /// # Examples
86    /// ```
87    /// use dsa::data_structures::tree::{BinaryTree, TreeNode};
88    /// let tree = BinaryTree::new(
89    ///     TreeNode::new(1), 
90    ///     Some(Box::new(BinaryTree::new(TreeNode::new(2), None, None))),
91    ///     Some(Box::new(BinaryTree::new(TreeNode::new(3), None, None)))
92    /// );
93    /// ```
94    pub fn new(root: TreeNode<T>, 
95               left: Option<Box<BinaryTree<T>>>, 
96               right: Option<Box<BinaryTree<T>>>) -> Self {
97        BinaryTree::<T> {
98            root,
99            left,
100            right
101        }
102    }
103}