Exercício: Árvore Binária
Uma árvore binária é uma estrutura de dados do tipo árvore onde cada nó tem dois filhos (esquerdo e direito). Criaremos uma árvore onde cada nó armazena um valor. Para um determinado nó N, todos os nós na subárvore esquerda de N contêm valores menores, e todos os nós na subárvore direita de N conterão valores maiores.
Implemente os seguintes tipos, para que os testes fornecidos passem.
Extra: implemente um iterador sobre uma árvore binária que retorna os valores em ordem.
/// Um nó na árvore binária. #[derive(Debug)] struct Node<T: Ord> { value: T, left: Subtree<T>, right: Subtree<T>, } /// Uma subárvore possivelmente vazia. #[derive(Debug)] struct Subtree<T: Ord>(Option<Box<Node<T>>>); /// Um contêiner que armazena um conjunto de valores, usando uma árvore binária. /// /// Se o mesmo valor for adicionado várias vezes, ele é armazenado apenas uma vez. #[derive(Debug)] pub struct BinaryTree<T: Ord> { root: Subtree<T>, } // Implemente `new`, `insert`, `len` e `has`. #[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); // não é um item único assert_eq!(tree.len(), 2); } #[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)); } }