연습문제: 바이너리 트리
바이너리 트리는 모든 노드에 두 개의 하위 요소(왼쪽과 오른쪽)가 있는 트리 유형 데이터 구조입니다. 각 노드가 값을 저장하는 트리를 만들겠습니다. 주어진 노드 N의 경우 N의 왼쪽 하위 트리에 있는 모든 노드는 더 작은 값을 포함하고, N의 오른쪽 하위 트리에 있는 모든 노드는 더 큰 값을 포함합니다.
지정된 테스트가 통과하도록 다음 타입을 구현합니다.
추가 크레딧: 값을 순서대로 반환하는 바이너리 트리에 대한 반복자를 구현합니다.
/// A node in the binary tree. #[derive(Debug)] struct Node<T: Ord> { value: T, left: Subtree<T>, right: Subtree<T>, } /// A possibly-empty subtree. #[derive(Debug)] struct Subtree<T: Ord>(Option<Box<Node<T>>>); /// 바이너리 트리를 사용하여 값 집합을 저장하는 컨테이너입니다. /// /// 동일한 값이 여러 번 추가되면 한 번만 저장됩니다. #[derive(Debug)] pub struct BinaryTree<T: Ord> { root: Subtree<T>, } // Implement `new`, `insert`, `len`, and `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); // 고유 항목이 아닙니다. 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)); } }