-
Notifications
You must be signed in to change notification settings - Fork 2
/
tree.go
73 lines (64 loc) · 1.46 KB
/
tree.go
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
package gophy
import "errors"
// Tree minimal phylogenetic tree struct
// don't need this, can use root but here if you want these convienence functions below
type Tree struct {
Rt *Node
Post []*Node
Pre []*Node
Tips []*Node
Index int // if there is an identifying index
}
// NewTree return a tree
func NewTree() *Tree {
return &Tree{}
}
func (t *Tree) populatePrePostIt(rt *Node) {
stk := NewNodeStack()
stk.Push(rt)
for stk.Empty() == false {
cur, _ := stk.Pop()
t.Pre = append(t.Pre, cur)
t.Post = append(t.Post, cur) // will be reversed
for _, n := range cur.Chs {
stk.Push(n)
}
if len(cur.Chs) == 0 {
t.Tips = append(t.Tips, cur)
}
}
for i, j := 0, len(t.Post)-1; i < j; i, j = i+1, j-1 {
t.Post[i], t.Post[j] = t.Post[j], t.Post[i]
}
}
func (t *Tree) populatePostorder(rt *Node) {
for _, n := range rt.Chs {
t.populatePostorder(n)
}
t.Post = append(t.Post, rt)
if len(rt.Chs) == 0 {
t.Tips = append(t.Tips, rt)
}
}
func (t *Tree) populatePreorder(rt *Node) {
t.Pre = append(t.Pre, rt)
for _, n := range rt.Chs {
t.populatePreorder(n)
}
}
// Instantiate will preorder and postorder
func (t *Tree) Instantiate(rt *Node) {
t.Rt = rt
t.populatePrePostIt(t.Rt)
//t.populatePreorder(t.Rt)
//t.populatePostorder(t.Rt)
}
// GetTipByName get
func (t *Tree) GetTipByName(name string) (*Node, error) {
for _, n := range t.Tips {
if n.Nam == name {
return n, nil
}
}
return nil, errors.New("no node with name: " + name)
}