binary_tree/iterators/
inorder.rs

1use crate::BinaryTree;
2use std::fmt;
3
4pub struct InOrderIter<'a, T>
5where
6    T: 'a + Clone + Ord + Eq + fmt::Debug,
7{
8    stack: Vec<&'a BinaryTree<T>>,
9}
10
11impl<'a, T> InOrderIter<'a, T>
12where
13    T: 'a + Clone + Ord + Eq + fmt::Debug,
14{
15    fn new(tree: &'a BinaryTree<T>) -> Self {
16        let mut iter = InOrderIter { stack: Vec::new() };
17        iter.push_left(tree);
18        iter
19    }
20
21    fn push_left(&mut self, node: &'a BinaryTree<T>) {
22        let mut current = node;
23        while let Some(left) = &current.left {
24            self.stack.push(current);
25            current = left;
26        }
27        self.stack.push(current);
28    }
29}
30
31impl<'a, T> Iterator for InOrderIter<'a, T>
32where
33    T: 'a + Clone + Ord + Eq + fmt::Debug,
34{
35    type Item = &'a T;
36
37    fn next(&mut self) -> Option<Self::Item> {
38        if self.stack.is_empty() {
39            return None;
40        }
41
42        let top = self.stack.pop().unwrap();
43        if let Some(ref right) = &top.right {
44            self.push_left(right);
45        }
46
47        top.elem.as_ref().map(|v| &**v)
48    }
49}
50
51impl<'a, T> IntoIterator for &'a BinaryTree<T>
52where
53    T: 'a + Clone + Ord + Eq + fmt::Debug,
54{
55    type Item = &'a T;
56    type IntoIter = InOrderIter<'a, T>;
57
58    /// Creates a iterator that iterates in INORDER
59    /// Basic usage:
60    /// ```
61    /// let mut a = BinaryTree::new(1);
62    /// a.vec_insert([1,2,3]);
63    /// for i in a.into_iter() {
64    ///     println!("{}", *i);
65    /// }
66    /// ```
67    fn into_iter(self) -> Self::IntoIter {
68        InOrderIter::new(self)
69    }
70}
binary_tree/iterators/inorder.rs

binary_tree/iterators/
inorder.rs
