rust_algorithms/tree/
binary_tree.rs

1//! Binar daraxt va uni aylanib chiqish (traversal) usullari.
2
3use std::collections::VecDeque;
4
5/// Binar daraxtning bitta tuguni.
6#[derive(Debug, Clone, PartialEq, Eq)]
7pub struct TreeNode<T> {
8    /// Tugundagi qiymat.
9    pub value: T,
10    /// Chap shox.
11    pub left: Option<Box<TreeNode<T>>>,
12    /// O'ng shox.
13    pub right: Option<Box<TreeNode<T>>>,
14}
15
16impl<T> TreeNode<T> {
17    /// Barg (farzandsiz tugun) yaratadi.
18    pub fn leaf(value: T) -> Self {
19        Self {
20            value,
21            left: None,
22            right: None,
23        }
24    }
25
26    /// Chap va o'ng shoxlari bilan tugun yaratadi.
27    pub fn new(value: T, left: Option<TreeNode<T>>, right: Option<TreeNode<T>>) -> Self {
28        Self {
29            value,
30            left: left.map(Box::new),
31            right: right.map(Box::new),
32        }
33    }
34}
35
36/// Binar daraxt — har bir tugunning ko'pi bilan 2 ta farzandi bor.
37///
38/// ## Aylanib chiqishning 4 usuli
39///
40/// ```text
41///        1
42///      /   \
43///     2     3
44///    / \
45///   4   5
46/// ```
47///
48/// | Usul | Tartib | Natija | Qachon kerak |
49/// |---|---|---|---|
50/// | Preorder | Ildiz → Chap → O'ng | 1 2 4 5 3 | Daraxtni nusxalash/serializatsiya |
51/// | Inorder | Chap → Ildiz → O'ng | 4 2 5 1 3 | BST da **tartiblangan** ketma-ketlik |
52/// | Postorder | Chap → O'ng → Ildiz | 4 5 2 3 1 | Daraxtni o'chirish, ifoda hisoblash |
53/// | Level order | Qavat-qavat | 1 / 2 3 / 4 5 | Eng qisqa yo'l, qavatlar bilan ishlash |
54///
55/// Dastlabki uchtasi — DFS (chuqurlikka), oxirgisi — BFS (kenglikka, navbat bilan).
56///
57/// # Misol
58/// ```
59/// use rust_algorithms::tree::{BinaryTree, TreeNode};
60///
61/// //      1
62/// //     / \
63/// //    2   3
64/// //   / \
65/// //  4   5
66/// let daraxt = BinaryTree::from_root(TreeNode::new(
67///     1,
68///     Some(TreeNode::new(2, Some(TreeNode::leaf(4)), Some(TreeNode::leaf(5)))),
69///     Some(TreeNode::leaf(3)),
70/// ));
71///
72/// assert_eq!(daraxt.preorder(), vec![&1, &2, &4, &5, &3]);
73/// assert_eq!(daraxt.inorder(), vec![&4, &2, &5, &1, &3]);
74/// assert_eq!(daraxt.postorder(), vec![&4, &5, &2, &3, &1]);
75/// assert_eq!(daraxt.level_order(), vec![vec![&1], vec![&2, &3], vec![&4, &5]]);
76/// assert_eq!(daraxt.height(), 2);
77/// assert_eq!(daraxt.size(), 5);
78/// ```
79#[derive(Debug, Clone, Default)]
80pub struct BinaryTree<T> {
81    /// Daraxt ildizi.
82    pub root: Option<Box<TreeNode<T>>>,
83}
84
85impl<T> BinaryTree<T> {
86    /// Bo'sh daraxt.
87    pub fn new() -> Self {
88        Self { root: None }
89    }
90
91    /// Ildiz tugunidan daraxt yasaydi.
92    pub fn from_root(root: TreeNode<T>) -> Self {
93        Self {
94            root: Some(Box::new(root)),
95        }
96    }
97
98    /// Ildiz → Chap → O'ng.
99    pub fn preorder(&self) -> Vec<&T> {
100        fn go<'a, T>(node: &'a Option<Box<TreeNode<T>>>, out: &mut Vec<&'a T>) {
101            if let Some(n) = node {
102                out.push(&n.value);
103                go(&n.left, out);
104                go(&n.right, out);
105            }
106        }
107        let mut out = Vec::new();
108        go(&self.root, &mut out);
109        out
110    }
111
112    /// Chap → Ildiz → O'ng.
113    pub fn inorder(&self) -> Vec<&T> {
114        fn go<'a, T>(node: &'a Option<Box<TreeNode<T>>>, out: &mut Vec<&'a T>) {
115            if let Some(n) = node {
116                go(&n.left, out);
117                out.push(&n.value);
118                go(&n.right, out);
119            }
120        }
121        let mut out = Vec::new();
122        go(&self.root, &mut out);
123        out
124    }
125
126    /// Chap → O'ng → Ildiz.
127    pub fn postorder(&self) -> Vec<&T> {
128        fn go<'a, T>(node: &'a Option<Box<TreeNode<T>>>, out: &mut Vec<&'a T>) {
129            if let Some(n) = node {
130                go(&n.left, out);
131                go(&n.right, out);
132                out.push(&n.value);
133            }
134        }
135        let mut out = Vec::new();
136        go(&self.root, &mut out);
137        out
138    }
139
140    /// Inorderning **rekursiyasiz** varianti — stack bilan.
141    ///
142    /// Chuqur daraxtlarda rekursiya stackni to'ldirishi mumkin; bu variant xavfsiz.
143    ///
144    /// # Misol
145    /// ```
146    /// use rust_algorithms::tree::{BinaryTree, TreeNode};
147    ///
148    /// let t = BinaryTree::from_root(TreeNode::new(
149    ///     2, Some(TreeNode::leaf(1)), Some(TreeNode::leaf(3)),
150    /// ));
151    /// assert_eq!(t.inorder_iterative(), t.inorder());
152    /// ```
153    pub fn inorder_iterative(&self) -> Vec<&T> {
154        let mut out = Vec::new();
155        let mut stack: Vec<&TreeNode<T>> = Vec::new();
156        let mut kursor = self.root.as_deref();
157
158        while kursor.is_some() || !stack.is_empty() {
159            // iloji boricha chapga tushamiz
160            while let Some(n) = kursor {
161                stack.push(n);
162                kursor = n.left.as_deref();
163            }
164            let n = stack.pop().unwrap();
165            out.push(&n.value);
166            kursor = n.right.as_deref();
167        }
168        out
169    }
170
171    /// Qavatma-qavat (BFS) — har bir qavat alohida vektor.
172    pub fn level_order(&self) -> Vec<Vec<&T>> {
173        let mut out = Vec::new();
174        let mut navbat: VecDeque<&TreeNode<T>> = VecDeque::new();
175        if let Some(r) = self.root.as_deref() {
176            navbat.push_back(r);
177        }
178        while !navbat.is_empty() {
179            let n = navbat.len(); // shu qavatdagi tugunlar soni
180            let mut qavat = Vec::with_capacity(n);
181            for _ in 0..n {
182                let node = navbat.pop_front().unwrap();
183                qavat.push(&node.value);
184                if let Some(l) = node.left.as_deref() {
185                    navbat.push_back(l);
186                }
187                if let Some(r) = node.right.as_deref() {
188                    navbat.push_back(r);
189                }
190            }
191            out.push(qavat);
192        }
193        out
194    }
195
196    /// Balandlik: ildizdan eng uzoq bargacha qirralar soni. Bo'sh daraxtda 0.
197    pub fn height(&self) -> usize {
198        fn go<T>(node: &Option<Box<TreeNode<T>>>) -> usize {
199            match node {
200                None => 0,
201                Some(n) => {
202                    if n.left.is_none() && n.right.is_none() {
203                        0
204                    } else {
205                        1 + go(&n.left).max(go(&n.right))
206                    }
207                }
208            }
209        }
210        go(&self.root)
211    }
212
213    /// Tugunlar soni.
214    pub fn size(&self) -> usize {
215        fn go<T>(node: &Option<Box<TreeNode<T>>>) -> usize {
216            match node {
217                None => 0,
218                Some(n) => 1 + go(&n.left) + go(&n.right),
219            }
220        }
221        go(&self.root)
222    }
223
224    /// Barglar (farzandsiz tugunlar) soni.
225    pub fn leaf_count(&self) -> usize {
226        fn go<T>(node: &Option<Box<TreeNode<T>>>) -> usize {
227            match node {
228                None => 0,
229                Some(n) if n.left.is_none() && n.right.is_none() => 1,
230                Some(n) => go(&n.left) + go(&n.right),
231            }
232        }
233        go(&self.root)
234    }
235
236    /// Daraxtni "ko'zguga" aylantiradi: chap va o'ng shoxlarni almashtiradi.
237    ///
238    /// # Misol
239    /// ```
240    /// use rust_algorithms::tree::{BinaryTree, TreeNode};
241    ///
242    /// let mut t = BinaryTree::from_root(TreeNode::new(
243    ///     1, Some(TreeNode::leaf(2)), Some(TreeNode::leaf(3)),
244    /// ));
245    /// t.invert();
246    /// assert_eq!(t.inorder(), vec![&3, &1, &2]);
247    /// ```
248    pub fn invert(&mut self) {
249        fn go<T>(node: &mut Option<Box<TreeNode<T>>>) {
250            if let Some(n) = node {
251                std::mem::swap(&mut n.left, &mut n.right);
252                go(&mut n.left);
253                go(&mut n.right);
254            }
255        }
256        go(&mut self.root);
257    }
258
259    /// Daraxt balanslanganmi? (har bir tugunda chap/o'ng balandlik farqi ≤ 1)
260    pub fn is_balanced(&self) -> bool {
261        // -1 = balanslanmagan
262        fn go<T>(node: &Option<Box<TreeNode<T>>>) -> i64 {
263            match node {
264                None => 0,
265                Some(n) => {
266                    let l = go(&n.left);
267                    if l < 0 {
268                        return -1;
269                    }
270                    let r = go(&n.right);
271                    if r < 0 || (l - r).abs() > 1 {
272                        return -1;
273                    }
274                    1 + l.max(r)
275                }
276            }
277        }
278        go(&self.root) >= 0
279    }
280}
281
282#[cfg(test)]
283mod tests {
284    use super::*;
285
286    fn namuna() -> BinaryTree<i32> {
287        //        1
288        //      /   \
289        //     2     3
290        //    / \     \
291        //   4   5     6
292        BinaryTree::from_root(TreeNode::new(
293            1,
294            Some(TreeNode::new(
295                2,
296                Some(TreeNode::leaf(4)),
297                Some(TreeNode::leaf(5)),
298            )),
299            Some(TreeNode::new(3, None, Some(TreeNode::leaf(6)))),
300        ))
301    }
302
303    #[test]
304    fn traversallar() {
305        let t = namuna();
306        assert_eq!(t.preorder(), vec![&1, &2, &4, &5, &3, &6]);
307        assert_eq!(t.inorder(), vec![&4, &2, &5, &1, &3, &6]);
308        assert_eq!(t.postorder(), vec![&4, &5, &2, &6, &3, &1]);
309        assert_eq!(t.inorder_iterative(), t.inorder());
310    }
311
312    #[test]
313    fn qavatlar() {
314        let t = namuna();
315        assert_eq!(
316            t.level_order(),
317            vec![vec![&1], vec![&2, &3], vec![&4, &5, &6]]
318        );
319    }
320
321    #[test]
322    fn olchamlar() {
323        let t = namuna();
324        assert_eq!(t.size(), 6);
325        assert_eq!(t.height(), 2);
326        assert_eq!(t.leaf_count(), 3);
327        assert!(t.is_balanced());
328    }
329
330    #[test]
331    fn bosh_daraxt() {
332        let t: BinaryTree<i32> = BinaryTree::new();
333        assert_eq!(t.size(), 0);
334        assert_eq!(t.height(), 0);
335        assert_eq!(t.leaf_count(), 0);
336        assert!(t.preorder().is_empty());
337        assert!(t.level_order().is_empty());
338        assert!(t.is_balanced());
339    }
340
341    #[test]
342    fn qiyshiq_daraxt_balanslanmagan() {
343        // 1 → 2 → 3 (faqat chapga)
344        let t = BinaryTree::from_root(TreeNode::new(
345            1,
346            Some(TreeNode::new(2, Some(TreeNode::leaf(3)), None)),
347            None,
348        ));
349        assert!(!t.is_balanced());
350        assert_eq!(t.height(), 2);
351    }
352
353    #[test]
354    fn invert_ikki_marta_asliga_qaytaradi() {
355        let asl = namuna();
356        let mut t = namuna();
357        t.invert();
358        t.invert();
359        assert_eq!(t.inorder(), asl.inorder());
360    }
361}
rust_algorithms/tree/binary_tree.rs

rust_algorithms/tree/
binary_tree.rs
