1 #lang racket
2
3 (define (entry tree) (car tree))
4
5 (define (left-
branch tree) (cadr tree))
6
7 (define (right-
branch tree) (caddr tree))
8
9 (define (make-
tree entry left right)
10 (list entry left right))
11
12 (define (tree->list-
1 tree)
13 (
if (
null?
tree)
14 '()
15 (append (tree->list-
1 (left-
branch tree))
16 (cons (entry tree)
17 (tree->list-
1 (right-
branch tree))))))
18
19 (define (tree->list-
2 tree)
20 (define (copy-to-list tree result-
list)
21 (
if (
null?
tree)
22 result-
list
23 (copy-to-list (left-
branch tree)
24 (cons (entry tree)
25 (copy-to-list (right-
branch tree)
26 result-
list)))))
27 (copy-to-list tree
'()))
28
29 (define tree1
30 (make-tree
7
31 (make-tree
3 '(1 () ()) '(
5 () ()))
32 (make-tree
9 '() '(
11 () ()))))
33
34 (define tree2
35 (make-tree
3
36 '(1 () ())
37 (make-tree
7
38 '(5 () ())
39 (make-tree
9 '() '(
11 () ())))))
40
41
42
43 ;;;;;;;;;;;;;;;;test
44 ;;;;;;;;;;;;;;产生相同的结果
45 ;;;;;;;;;;;;;;
46 (tree->list-
1 tree1)
47 (tree->list-
2 tree1)
48 (tree->list-
1 tree2)
49 (tree->list-
2 tree2)
50
51 ;;;;;;;;;;;;;;;
2.64
52 (define (list-
tree elements)
53 (car (
partial-
tree elements (length elements))))
54
55 (define (
partial-
tree elts n)
56 (
if (= n
0)
57 (cons
'() elts)
58 (let ((left-size (quotient (- n
1)
2)))
59 (let ((left-result (
partial-tree elts left-
size)))
60 (let ((left-tree (car left-
result))
61 (non-left-elts (cdr left-
result))
62 (right-size (- n (+ left-size
1))))
63 (let ((
this-entry (car non-left-
elts))
64 (right-result (
partial-tree (cdr non-left-
elts)
65 right-
size)))
66 (let ((right-tree (car right-
result))
67 (remaining-elts (cdr right-
result)))
68 (cons (make-tree
this-entry left-tree right-
tree)
69 remaining-
elts))))))))
70
71 ;;;;;;;;;;;;test(a)
72 ;;;;;;;;;;;;先算出左子树的size再构造左子树，以及剩下的非左子树
73 ;;;;;;;;;;;;的序列，以及右子树的size再根据这些构造完整的树
74 ;;;;;;;;;;;;实际上就是中序构造一颗平衡树
75 (list-tree
'(1 3 5 7 9))
76
77 ;;;;;;;;;;;;(b)
78 ;;;;;;;;;;;;O(log(n))
79
80 ;;;;;;;;;;;;;
2.65
81 (define (
new-union-
set set1 set2)
82 (list-tree (union-
set (tree->list-
2 set1) (tree->list-
2 set2))))
83
84 (define (union-
set set1 set2)
85 (cond ((
null?
set1) set2)
86 ((
null?
set2) set1)
87 ((<
(car set1) (car set2))
88 (cons (car set1) (union-
set (cdr set1) set2)))
89 ((<
(car set2) (car set1))
90 (cons (car set2) (union-
set set1 (cdr set2))))
91 ((=
(car set1) (car set2))
92 (cons (car set1) (union-
set (cdr set1) (cdr set2))))))
93
94 (define (
new-intersection-
set set1 set2)
95 (list-tree (intersection-
set (tree->list-
2 set1)
96 (tree->list-
2 set2))))
97
98 (define (intersection-
set set1 set2)
99 (
if (or (
null? set1) (
null?
set2))
100 '()
101 (let ((x1 (car set1)) (x2 (car set2)))
102 (cond ((=
x1 x2)
103 (cons x1
104 (intersection-
set (cdr set1)
105 (cdr set2))))
106 ((<
x1 x2)
107 (intersection-
set (cdr set1) set2))
108 ((<
x2 x1)
109 (intersection-
set set1 (cdr set2)))))))
110
111 ;;;;;;;;;;;;;;;;test
112 ;;;;;;;;;;;;;;;;因为union-set和intersection-
set
113 ;;;;;;;;;;;;;;;;都是O(n)而list-tree 和 tree->list-
2
114 ;;;;;;;;;;;;;;;;都是O(log(n))所以总的步数为O(n)
115 (
new-intersection-
set (list-tree
'(1 2 3 4 5))
116 (list-tree
'(3 4 5 6 7)))
117
118 (
new-union-
set (list-tree
'(1 2 3 4 5))
119 (list-tree
'(3 4 5 6 7)))
对于2.63 对步数还是没有好的理解
参考1 参考2
从参考一中可以看出tree->list-1 append数是正比于n的，但是步数应该为O（n*log（n））
因为append并不是每次都会append 个数为n的list
tree->list-2 只有cons操作，步数正比于n，O（n）
参考二中有一句话：
We can see
from the results above and
from inspecting the two procedures
that each node of the tree is visited one time by each algorithm. What
happens at each of those n steps is subtly different though. The second
procedure simply calls cons at each step, which we'll assume is a
constant-time operation
可以仔细想一下
转载于:https://www.cnblogs.com/tclan126/p/6486836.html
相关资源：数据结构—成绩单生成器
