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
|
discard """
output: '''hello
world
99
110
223'''
"""
type
TBinaryTree[T] = object # TBinaryTree is a generic type with
# with generic param ``T``
le, ri: ref TBinaryTree[T] # left and right subtrees; may be nil
data: T # the data stored in a node
PBinaryTree*[A] = ref TBinaryTree[A] # type that is exported
proc newNode*[T](data: T): PBinaryTree[T] =
# constructor for a node
new(result)
result.data = data
proc add*[Ty](root: var PBinaryTree[Ty], n: PBinaryTree[Ty]) =
# insert a node into the tree
if root == nil:
root = n
else:
var it = root
while it != nil:
# compare the data items; uses the generic ``cmp`` proc that works for
# any type that has a ``==`` and ``<`` operator
var c = cmp(n.data, it.data)
if c < 0:
if it.le == nil:
it.le = n
return
it = it.le
else:
if it.ri == nil:
it.ri = n
return
it = it.ri
proc add*[Ty](root: var PBinaryTree[Ty], data: Ty) =
# convenience proc:
add(root, newNode(data))
proc find*[Ty2](b: PBinaryTree[Ty2], data: Ty2): bool =
# for testing this needs to be recursive, so that the
# instantiated type is checked for proper tyGenericInst envelopes
if b == nil:
result = false
else:
var c = cmp(data, b.data)
if c < 0: result = find(b.le, data)
elif c > 0: result = find(b.ri, data)
else: result = true
iterator preorder*[T](root: PBinaryTree[T]): T =
# Preorder traversal of a binary tree.
# Since recursive iterators are not yet implemented,
# this uses an explicit stack:
var stack: seq[PBinaryTree[T]] = @[root]
while stack.len > 0:
var n = stack.pop()
while n != nil:
yield n.data
add(stack, n.ri) # push right subtree onto the stack
n = n.le # and follow the left pointer
iterator items*[T](root: PBinaryTree[T]): T =
## Inorder traversal of the binary tree.
var stack: seq[PBinaryTree[T]] = @[]
var n = root
while true:
while n != nil:
add(stack, n)
n = n.le
if stack.len > 0:
n = stack.pop()
yield n.data
n = n.ri
if stack.len == 0 and n == nil: break
proc debug[T](a: PBinaryTree[T]) =
if a != nil:
debug(a.le)
echo a.data
debug(a.ri)
when true:
var
root: PBinaryTree[string]
x = newNode("hello")
add(root, x)
add(root, "world")
if find(root, "world"):
for str in items(root):
echo(str)
else:
echo("BUG")
var
r2: PBinaryTree[int]
add(r2, newNode(110))
add(r2, 223)
add(r2, 99)
for y in items(r2):
echo(y)
|