algorithms_edu/algo/graph/
tree.rs

1//! This module contains tree representations and related algorithms.
2
3pub mod center;
4pub mod height;
5pub mod isomorphism;
6pub mod lca;
7pub mod rooting;
8pub mod sum;
9
10/// Representation of a tree node, which has an `id` and a `Vec` of `children`.
11/// `children` is empty if the node does not have children.
12#[derive(Debug, Eq, PartialEq)]
13pub struct Node {
14    pub id: usize,
15    pub children: Vec<Node>,
16}
17
18impl Node {
19    /// Creates a new node without children
20    pub fn new(id: usize) -> Self {
21        Self {
22            id,
23            children: vec![],
24        }
25    }
26}
27
28pub struct BinaryTreeNode {
29    pub id: usize,
30    pub left: Option<Box<BinaryTreeNode>>,
31    pub right: Option<Box<BinaryTreeNode>>,
32}
33
34impl BinaryTreeNode {
35    pub fn new(id: usize) -> Self {
36        Self {
37            id,
38            left: None,
39            right: None,
40        }
41    }
42}
43
44pub mod with_parent {
45    pub use std::cell::RefCell;
46    pub use std::rc::{Rc, Weak};
47    /// Representation of a tree node, which has an `id`, a `Vec` of `children`, as well as a `Weak` reference
48    /// to its `parent`
49    #[derive(Debug)]
50    pub struct Node {
51        pub id: usize,
52        // A `Weak` reference is required to prevent `Rc` from forming cycles
53        // If `Rc` were used, it would cause a stack overflow, for example, when you try to print it.
54        pub parent: Option<Weak<RefCell<Node>>>,
55        pub children: Vec<Rc<RefCell<Node>>>,
56    }
57
58    /// Two nodes are identical if their `id`s equal, have the same children, and have the same parent `id`.
59    /// `#[derive(PartialEq, Eq)]` does not work with `Weak` references, so we need manual implementation.
60    impl std::cmp::PartialEq for Node {
61        fn eq(&self, other: &Node) -> bool {
62            self.id == other.id
63                && self.children == other.children
64                && match (self.parent.as_ref(), other.parent.as_ref()) {
65                    (None, None) => true,
66                    (Some(x), Some(y)) => {
67                        x.upgrade().unwrap().borrow().id == y.upgrade().unwrap().borrow().id
68                    }
69                    _ => false,
70                }
71        }
72    }
73    impl std::cmp::Eq for Node {}
74
75    impl Node {
76        /// Creates a new node either with or without a parent.
77        pub fn new(id: usize, parent: Option<&Rc<RefCell<Node>>>) -> Rc<RefCell<Node>> {
78            Rc::new(RefCell::new(Self {
79                id,
80                parent: parent.map(|parent| Rc::downgrade(&parent)),
81                children: vec![],
82            }))
83        }
84        /// Add a child node to a parent node.
85        /// First, a `Weak` reference to the parent is created and stored in the child.
86        /// Then, a clone is pushed onto the parent's `Vec` of `children`
87        pub fn add_child(parent: &Rc<RefCell<Node>>, child: &Rc<RefCell<Node>>) {
88            child.borrow_mut().parent = Some(Rc::downgrade(parent));
89            parent.borrow_mut().children.push(child.clone());
90        }
91    }
92
93    #[derive(Debug, Eq, PartialEq)]
94    #[allow(clippy::vec_box)]
95    pub struct UnsafeTreeNode {
96        pub id: usize,
97        pub parent: *const UnsafeTreeNode,
98        // `Box` is required to prevent the parent pointer becoming invalid; otherwise, `Rc` can be used.
99        pub children: Vec<Box<UnsafeTreeNode>>,
100    }
101
102    impl UnsafeTreeNode {
103        pub fn new(id: usize, parent: *const UnsafeTreeNode) -> Self {
104            Self {
105                id,
106                parent,
107                children: vec![],
108            }
109        }
110    }
111}
algorithms_edu/algo/graph/tree.rs

algorithms_edu/algo/graph/
tree.rs
