解答

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. }