-
Notifications
You must be signed in to change notification settings - Fork 0
/
binarytree.go
88 lines (78 loc) · 1.84 KB
/
binarytree.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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
package types
type BinaryNode interface {
SetValue(v interface{})
Value() (v interface{})
Left() (l BinaryNode)
Right() (l BinaryNode)
IsNil() bool
}
func PrintBinary(b BinaryNode) (pt [][]interface{}) {
deep := Deepest(b)
hei := deep*2 - 1
wid := deep*(deep+1) - 1
pt = CreateMat(hei, wid, " ")
pt[0][wid/2] = b.Value()
if !b.Left().IsNil() {
for i := 1; i < deep; i++ {
pt[i][wid/2-i] = "/"
}
}
if !b.Right().IsNil() {
for i := 1; i < deep; i++ {
pt[i][wid/2+i] = "\\"
}
}
if deep > 2 {
if !b.Left().IsNil() {
left := PrintBinary(b.Left())
CopyMat(pt, left, deep, 0)
}
if !b.Right().IsNil() {
right := PrintBinary(b.Right())
CopyMat(pt, right, deep, hei)
}
} else {
if !b.Left().IsNil() {
left := PrintBinary(b.Left())
CopyMat(pt, left, deep, 0)
}
if !b.Right().IsNil() {
right := PrintBinary(b.Right())
CopyMat(pt, right, deep, wid-1)
}
}
return
}
//MidOrderTraverse 中序遍历
func MidOrderTraverse(t BinaryNode) (result []interface{}) {
result = append(result, MidOrderTraverse(t.Left())...)
result = append(result, t.Value())
result = append(result, MidOrderTraverse(t.Right())...)
return
}
//MidOrderTraverse 中序遍历
func Deepest(t BinaryNode) int {
if t.IsNil() {
return 0
}
max := Deepest(t.Left())
r := Deepest(t.Right())
if r > max {
return 1 + r
}
return 1 + max
}
//MidOrderTraverse 先序遍历
func PreOrderTraverse(t BinaryNode) (result []interface{}) {
result = append(result, t.Value())
result = append(result, MidOrderTraverse(t.Left())...)
result = append(result, MidOrderTraverse(t.Right())...)
return
}
//PostOrderTraverse 后序遍历
func PostOrderTraverse(t BinaryNode) (result []interface{}) {
result = append(result, MidOrderTraverse(t.Left())...)
result = append(result, MidOrderTraverse(t.Right())...)
result = append(result, t.Value())
return
}