练习：二叉树

二元树是一种树型数据结构，其中每个节点都有两个子节点（左侧和右侧）。我们将创建一个树状结构，其中每个节点存储一个值。对于给定的节点 N，N 的左侧子树中的所有节点都包含较小的值，而 N 的右侧子树中的所有节点都将包含较大的值。

实现以下类型，以便通过指定的测试。

额外提示：对按顺序返回值的二元树实现迭代器。

1. /// A node in the binary tree.
2. #[derive(Debug)]
3. struct Node<T: Ord> {
4. value: T,
5. left: Subtree<T>,
6. right: Subtree<T>,
7. }

9. /// A possibly-empty subtree.
10. #[derive(Debug)]
11. struct Subtree<T: Ord>(Option<Box<Node<T>>>);

13. /// A container storing a set of values, using a binary tree.
14. ///
15. /// If the same value is added multiple times, it is only stored once.
16. #[derive(Debug)]
17. pub struct BinaryTree<T: Ord> {
18. root: Subtree<T>,
19. }

21. // Implement `new`, `insert`, `len`, and `has`.

23. #[cfg(test)]
24. mod tests {
25. use super::*;

27. #[test]
28. fn len() {
29. let mut tree = BinaryTree::new();
30. assert_eq!(tree.len(), 0);
31. tree.insert(2);
32. assert_eq!(tree.len(), 1);
33. tree.insert(1);
34. assert_eq!(tree.len(), 2);
35. tree.insert(2); // not a unique item
36. assert_eq!(tree.len(), 2);
37. }

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

48. check_has(&tree, &[false, false, false, false, false]);
49. tree.insert(0);
50. check_has(&tree, &[true, false, false, false, false]);
51. tree.insert(4);
52. check_has(&tree, &[true, false, false, false, true]);
53. tree.insert(4);
54. check_has(&tree, &[true, false, false, false, true]);
55. tree.insert(3);
56. check_has(&tree, &[true, false, false, true, true]);
57. }

59. #[test]
60. fn unbalanced() {
61. let mut tree = BinaryTree::new();
62. for i in 0..100 {
63. tree.insert(i);
64. }
65. assert_eq!(tree.len(), 100);
66. assert!(tree.has(&50));
67. }
68. }