-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathtrees.clj
130 lines (100 loc) · 2.54 KB
/
trees.clj
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
(ns viksit-trees)
(comment
; tree representation
; 1
; / \
; 2 3
; / / \
;4 5 6
)
; Tree node
(defstruct node :value :left :right)
(def nval (accessor node :value))
(def lft (accessor node :left))
(def rt (accessor node :right))
; Convenience macro for quick tree creation
(defmacro tn
([v]
`(struct node ~v nil nil))
([v l r]
`(struct node ~v ~l ~r)))
(macroexpand '(tn 1 nil nil))
(def mytree
(tn 1
(tn 2
(tn 4) nil)
(tn 3
(tn 5) (tn 6))))
(defn tree-search [bt e]
"Test if element e is in binary tree bt"
(let [curval (bt :value) lft (bt :left) rt (bt :right)]
(if (nil? curval)
false
(do
(println (str "Value: " curval))
(or
(== curval e)
(and (not (nil? lft)) (tree-search lft e))
(and (not (nil? rt)) (tree-search rt e)))))))
(tree-search mytree 1)
(tree-search mytree 2)
(tree-search mytree 3)
(tree-search mytree 4)
(tree-search mytree 5)
(tree-search mytree 6)
(tree-search mytree 11)
(tree-search mytree 10)
; Test harness
(map #(tree-search mytree %) (range 1 11))
(for [i (range 0 10)]
(tree-search mytree i))
(doseq [i (range 0 10)]
(tree-search mytree i))
(loop [i 0]
(when-not (== i 10)
(tree-search mytree i) (recur (inc i))))
(loop [i 0 r []]
(if-not (== i 10)
(recur (inc i) (conj r (tree-search mytree i))) r))
; Traversal
; pass a function and call that
(defn pre-order [bt]
(let [curval (bt :value) lft (bt :left) rt (bt :right) r []]
(if (nil? curval)
false
(or
(println (str "Visited " curval))
(and (not (nil? lft)) (pre-order lft))
(and (not (nil? rt)) (pre-order rt))))))
(pre-order mytree)
(defn post-order [bt]
(let [curval (bt :value) lft (bt :left) rt (bt :right) r []]
(if (nil? curval)
false
(or
(and (not (nil? lft)) (post-order lft))
(and (not (nil? rt)) (post-order rt))
(println (str "Visited " curval))))))
(post-order mytree)
(defn in-order [bt]
(let [curval (bt :value) lft (bt :left) rt (bt :right) r []]
(if (nil? curval)
false
(or
(and (not (nil? lft)) (in-order lft))
(println (str "Visited " curval))
(and (not (nil? rt)) (in-order rt))))))
(in-order mytree)
(defn queue [& xs]
(when (seq xs)
(apply conj clojure.lang.PersistentQueue/EMPTY xs)))
(defn level-order [rootnode]
(loop [curlevel (queue rootnode)]
(when-not (empty? curlevel)
(if-let [n (first curlevel)]
(do
(prn (seq curlevel))
(prn (n :value))
(recur (conj (pop curlevel) (n :left) (n :right))))
(recur (pop curlevel))))))
(level-order mytree)