forked from TheAlgorithms/Go
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbinary-tree.go
More file actions
110 lines (93 loc) · 1.63 KB
/
Copy pathbinary-tree.go
File metadata and controls
110 lines (93 loc) · 1.63 KB
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
// basic binary tree and related operations
package binarytree
// package main
import "fmt"
type node struct {
val int
left *node
right *node
}
type btree struct {
root *node
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func newNode(val int) *node {
n := &node{val, nil, nil}
return n
}
func inorder(n *node) {
if n == nil {
return
}
inorder(n.left)
fmt.Print(n.val, " ")
inorder(n.right)
}
func preorder(n *node) {
if n == nil {
return
}
fmt.Print(n.val, " ")
inorder(n.left)
inorder(n.right)
}
func postorder(n *node) {
if n == nil {
return
}
inorder(n.left)
inorder(n.right)
fmt.Print(n.val, " ")
}
func levelorder(root *node) {
var q []*node // queue
var n *node // temporary node
q = append(q, root)
for len(q) != 0 {
n, q = q[0], q[1:]
fmt.Print(n.val, " ")
if n.left != nil {
q = append(q, n.left)
}
if n.right != nil {
q = append(q, n.right)
}
}
}
// helper function for t.depth
func _calculate_depth(n *node, depth int) int {
if n == nil {
return depth
}
return max(_calculate_depth(n.left, depth+1), _calculate_depth(n.right, depth+1))
}
func (t *btree) depth() int {
return _calculate_depth(t.root, 0)
}
/*
func main() {
t := btree{nil}
t.root = newNode(0)
t.root.left = newNode(1)
t.root.right = newNode(2)
t.root.left.left = newNode(3)
t.root.left.right = newNode(4)
t.root.right.left = newNode(5)
t.root.right.right = newNode(6)
t.root.right.right.right = newNode(10)
inorder(t.root)
fmt.Print("\n")
preorder(t.root)
fmt.Print("\n")
postorder(t.root)
fmt.Print("\n")
levelorder(t.root)
fmt.Print("\n")
fmt.Print(t.depth(), "\n")
}
*/