Alıştırma: İkili Ağaç

Bir ikili ağaç (binary tree), her düğümün (node) iki çocuğa (sol ve sağ) sahip olduğu bir ağaç türü veri yapısıdır. Her düğümün bir değer sakladığı bir ağaç oluşturacağız. Belirli bir N düğümü için, N’nin sol alt ağacındaki tüm düğümler daha küçük değerler içerir ve N’nin sağ alt ağacındaki tüm düğümler daha büyük değerler içerir. Belirli bir değer ağaçta yalnızca bir kez saklanmalıdır, yani aynı değere sahip düğümler olmamalıdır.

Aşağıdaki türleri gerçekleştirin (implement), böylece verilen testler geçer.

/// İkili ağaçtaki (binary tree) bir düğüm.
#[derive(Debug)]
struct Node<T: Ord> {
    value: T,
    left: Subtree<T>,
    right: Subtree<T>,
}

/// Muhtemelen boş bir alt ağaç.
#[derive(Debug)]
struct Subtree<T: Ord>(Option<Box<Node<T>>>);

/// İkili ağaç (binary tree) kullanarak bir değerler kümesini saklayan bir kap.
///
/// Aynı değer birden çok kez eklenirse, yalnızca bir kez saklanır.
#[derive(Debug)]
pub struct BinaryTree<T: Ord> {
    root: Subtree<T>,
}

impl<T: Ord> BinaryTree<T> {
    fn new() -> Self {
        Self { root: Subtree::new() }
    }

    fn insert(&mut self, value: T) {
        self.root.insert(value);
    }

    fn has(&self, value: &T) -> bool {
        self.root.has(value)
    }

    fn len(&self) -> usize {
        self.root.len()
    }
}

// `Subtree` için `new`, `insert`, `len` ve `has`'ı gerçekleştirin.

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn len() {
        let mut tree = BinaryTree::new();
        assert_eq!(tree.len(), 0);
        tree.insert(2);
        assert_eq!(tree.len(), 1);
        tree.insert(1);
        assert_eq!(tree.len(), 2);
        tree.insert(2); // benzersiz bir öğe değil
        assert_eq!(tree.len(), 2);
        tree.insert(3);
        assert_eq!(tree.len(), 3);
    }

    #[test]
    fn has() {
        let mut tree = BinaryTree::new();
        fn check_has(tree: &BinaryTree<i32>, exp: &[bool]) {
            let got: Vec<bool> =
                (0..exp.len()).map(|i| tree.has(&(i as i32))).collect();
            assert_eq!(&got, exp);
        }

        check_has(&tree, &[false, false, false, false, false]);
        tree.insert(0);
        check_has(&tree, &[true, false, false, false, false]);
        tree.insert(4);
        check_has(&tree, &[true, false, false, false, true]);
        tree.insert(4);
        check_has(&tree, &[true, false, false, false, true]);
        tree.insert(3);
        check_has(&tree, &[true, false, false, true, true]);
    }

    #[test]
    fn unbalanced() {
        let mut tree = BinaryTree::new();
        for i in 0..100 {
            tree.insert(i);
        }
        assert_eq!(tree.len(), 100);
        assert!(tree.has(&50));
    }
}