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}