解答

  1. use std::cmp::Ordering;
  3. /// A node in the binary tree.
  4. #[derive(Debug)]
  5. struct Node<T: Ord> {
  6.     value: T,
  7.     left: Subtree<T>,
  8.     right: Subtree<T>,
  9. }
  11. /// A possibly-empty subtree.
  12. #[derive(Debug)]
  13. struct Subtree<T: Ord>(Option<Box<Node<T>>>);
  15. /// A container storing a set of values, using a binary tree.
  16. ///
  17. /// If the same value is added multiple times, it is only stored once.
  18. #[derive(Debug)]
  19. pub struct BinaryTree<T: Ord> {
  20.     root: Subtree<T>,
  21. }
  23. impl<T: Ord> BinaryTree<T> {
  24.     fn new() -> Self {
  25.         Self { root: Subtree::new() }
  26.     }
  28.     fn insert(&mut self, value: T) {
  29.         self.root.insert(value);
  30.     }
  32.     fn has(&self, value: &T) -> bool {
  33.         self.root.has(value)
  34.     }
  36.     fn len(&self) -> usize {
  37.         self.root.len()
  38.     }
  39. }
  41. impl<T: Ord> Subtree<T> {
  42.     fn new() -> Self {
  43.         Self(None)
  44.     }
  46.     fn insert(&mut self, value: T) {
  47.         match &mut self.0 {
  48.             None => self.0 = Some(Box::new(Node::new(value))),
  49.             Some(n) => match value.cmp(&n.value) {
  50.                 Ordering::Less => n.left.insert(value),
  51.                 Ordering::Equal => {}
  52.                 Ordering::Greater => n.right.insert(value),
  53.             },
  54.         }
  55.     }
  57.     fn has(&self, value: &T) -> bool {
  58.         match &self.0 {
  59.             None => false,
  60.             Some(n) => match value.cmp(&n.value) {
  61.                 Ordering::Less => n.left.has(value),
  62.                 Ordering::Equal => true,
  63.                 Ordering::Greater => n.right.has(value),
  64.             },
  65.         }
  66.     }
  68.     fn len(&self) -> usize {
  69.         match &self.0 {
  70.             None => 0,
  71.             Some(n) => 1 + n.left.len() + n.right.len(),
  72.         }
  73.     }
  74. }
  76. impl<T: Ord> Node<T> {
  77.     fn new(value: T) -> Self {
  78.         Self { value, left: Subtree::new(), right: Subtree::new() }
  79.     }
  80. }
  82. fn main() {
  83.     let mut tree = BinaryTree::new();
  84.     tree.insert("foo");
  85.     assert_eq!(tree.len(), 1);
  86.     tree.insert("bar");
  87.     assert!(tree.has(&"foo"));
  88. }
  90. #[cfg(test)]
  91. mod tests {
  92.     use super::*;
  94.     #[test]
  95.     fn len() {
  96.         let mut tree = BinaryTree::new();
  97.         assert_eq!(tree.len(), 0);
  98.         tree.insert(2);
  99.         assert_eq!(tree.len(), 1);
  100.         tree.insert(1);
  101.         assert_eq!(tree.len(), 2);
  102.         tree.insert(2); // not a unique item
  103.         assert_eq!(tree.len(), 2);
  104.     }
  106.     #[test]
  107.     fn has() {
  108.         let mut tree = BinaryTree::new();
  109.         fn check_has(tree: &BinaryTree<i32>, exp: &[bool]) {
  110.             let got: Vec<bool> =
  111.                 (0..exp.len()).map(|i| tree.has(&(i as i32))).collect();
  112.             assert_eq!(&got, exp);
  113.         }
  115.         check_has(&tree, &[false, false, false, false, false]);
  116.         tree.insert(0);
  117.         check_has(&tree, &[true, false, false, false, false]);
  118.         tree.insert(4);
  119.         check_has(&tree, &[true, false, false, false, true]);
  120.         tree.insert(4);
  121.         check_has(&tree, &[true, false, false, false, true]);
  122.         tree.insert(3);
  123.         check_has(&tree, &[true, false, false, true, true]);
  124.     }
  126.     #[test]
  127.     fn unbalanced() {
  128.         let mut tree = BinaryTree::new();
  129.         for i in 0..100 {
  130.             tree.insert(i);
  131.         }
  132.         assert_eq!(tree.len(), 100);
  133.         assert!(tree.has(&50));
  134.     }
  135. }