bst/traverse.go at master · ergnuor/bst · GitHub

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
package bst

import (
	"math"
)

type order byte

const (
	pre order = iota
	in
	post
)

type Visitor interface {
	Visit(Payload)
}

type queue struct {
	f, b, l int
	q       []Node
}

func (q *queue) Enqueue(n Node) {
	if q.q[q.b] != nil || n == nil {
		return
	}

	q.q[q.b] = n
	q.b = int(math.Mod(float64(q.b+1), float64(q.l)))
}

func (q *queue) Dequeue() Node {
	if q.Empty() {
		return nil
	}

	n := q.q[q.f]
	q.q[q.f] = nil
	q.f = int(math.Mod(float64(q.f+1), float64(q.l)))

	return n
}

func (q *queue) Empty() bool {
	return q.q[q.f] == nil
}

func TraversePreOrder(t Tree, v Visitor) {
	orderTraverse(t, v, pre)
}

func TraverseInOrder(t Tree, v Visitor) {
	orderTraverse(t, v, in)
}

func TraversePostOrder(t Tree, v Visitor) {
	orderTraverse(t, v, post)
}

func TraverseBreadthFirst(t Tree, v Visitor) {
	l := int(math.Ceil(float64(t.Count()) / 2))
	q := &queue{l: l, q: make([]Node, l)}

	q.Enqueue(t.Root())

	for !q.Empty() {
		n := q.Dequeue()
		v.Visit(n.Payload())
		if n.Left() != nil {
			q.Enqueue(n.Left())
		}

		if n.Right() != nil {
			q.Enqueue(n.Right())
		}
	}
}

func orderTraverse(t Tree, v Visitor, o order) {
	n := t.Root()
	nodeStack := make([]Node, 0, t.MaxHeight())
	var lastPoppedNode Node

	for l := len(nodeStack); n != nil || l > 0; l = len(nodeStack) {
		if n != nil {
			if o&pre != 0 {
				v.Visit(n.Payload())
			}

			nodeStack = append(nodeStack, n)
			n = n.Left()
			continue
		}

		n = nodeStack[l-1]
		if o&in != 0 && (n.Right() == nil || n.Right() != lastPoppedNode) {
			v.Visit(n.Payload())
		}

		if n.Right() != nil && n.Right() != lastPoppedNode {
			n = n.Right()
			continue
		}

		if o&post != 0 {
			v.Visit(n.Payload())
		}
		lastPoppedNode = n
		nodeStack = nodeStack[:l-1]
		n = nil
	}
}