Skip to content

Commit 759ae35

Browse files
code3002code3002
authored
Add files via upload
1 parent 33106bb commit 759ae35

2 files changed

Lines changed: 236 additions & 0 deletions

File tree

‎binary-tree/binarysearchtree.go‎

Lines changed: 126 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,126 @@
1+
// Binary search tree
2+
3+
4+
package binarySearchTree
5+
6+
// package main
7+
8+
import "fmt"
9+
10+
type node struct {
11+
val int
12+
left *node
13+
right *node
14+
}
15+
16+
type btree struct {
17+
root *node
18+
}
19+
20+
func max(a, b int) int {
21+
if a > b {
22+
return a
23+
}
24+
return b
25+
}
26+
27+
func newNode(val int) *node {
28+
return &node{val, nil, nil}
29+
}
30+
31+
func inorder(n *node) {
32+
if n != nil {
33+
inorder(n.left)
34+
fmt.Print(n.val, " ")
35+
inorder(n.right)
36+
}
37+
}
38+
39+
func insert(root *node, val int) *node {
40+
if root == nil {
41+
return newNode(val)
42+
}
43+
if val < root.val {
44+
root.left = insert(root.left, val)
45+
} else {
46+
root.right = insert(root.right, val)
47+
}
48+
return root
49+
}
50+
51+
func inorderSuccessor(root *node) *node {
52+
cur := root
53+
for cur.left != nil {
54+
cur = cur.left
55+
}
56+
return cur
57+
}
58+
59+
func bst_delete(root *node, val int) *node {
60+
if root == nil {
61+
return nil
62+
}
63+
if val < root.val {
64+
root.left = bst_delete(root.left, val)
65+
} else if val > root.val {
66+
root.right = bst_delete(root.right, val)
67+
} else {
68+
// this is the node to delete
69+
// node with one child
70+
if root.left == nil {
71+
return root.right
72+
} else if root.right == nil {
73+
return root.left
74+
} else {
75+
n := root.right
76+
d := inorderSuccessor(n)
77+
d.left = root.left
78+
return root.right
79+
}
80+
}
81+
return root
82+
}
83+
84+
// helper function for t.depth
85+
func _calculate_depth(n *node, depth int) int {
86+
if n == nil {
87+
return depth
88+
}
89+
return max(_calculate_depth(n.left, depth+1), _calculate_depth(n.right, depth+1))
90+
}
91+
92+
func (t *btree) depth() int {
93+
return _calculate_depth(t.root, 0)
94+
}
95+
96+
97+
func main() {
98+
t := &btree{nil}
99+
inorder(t.root)
100+
t.root = insert(t.root, 30)
101+
102+
t.root = insert(t.root, 20)
103+
t.root = insert(t.root, 15)
104+
t.root = insert(t.root, 10)
105+
t.root = insert(t.root, 12)
106+
t.root = insert(t.root, 9)
107+
t.root = insert(t.root, 11)
108+
t.root = insert(t.root, 17)
109+
fmt.Print(t.depth(), "\n")
110+
inorder(t.root)
111+
fmt.Print("\n")
112+
t.root = bst_delete(t.root, 10)
113+
inorder(t.root)
114+
fmt.Print("\n")
115+
t.root = bst_delete(t.root, 30)
116+
inorder(t.root)
117+
fmt.Print("\n")
118+
t.root = bst_delete(t.root, 15)
119+
inorder(t.root)
120+
fmt.Print("\n")
121+
t.root = bst_delete(t.root, 20)
122+
inorder(t.root)
123+
fmt.Print("\n")
124+
fmt.Print(t.depth(), "\n")
125+
}
126+

‎binary-tree/binarytree.go‎

Lines changed: 110 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,110 @@
1+
// basic binary tree and related operations
2+
3+
package binarytree
4+
5+
// package main
6+
7+
import "fmt"
8+
9+
type node struct {
10+
val int
11+
left *node
12+
right *node
13+
}
14+
15+
type btree struct {
16+
root *node
17+
}
18+
19+
func max(a, b int) int {
20+
if a > b {
21+
return a
22+
}
23+
return b
24+
}
25+
26+
func newNode(val int) *node {
27+
n := &node{val, nil, nil}
28+
return n
29+
}
30+
31+
func inorder(n *node) {
32+
if n == nil {
33+
return
34+
}
35+
inorder(n.left)
36+
fmt.Print(n.val, " ")
37+
inorder(n.right)
38+
}
39+
40+
func preorder(n *node) {
41+
if n == nil {
42+
return
43+
}
44+
fmt.Print(n.val, " ")
45+
preorder(n.left)
46+
preorder(n.right)
47+
}
48+
49+
func postorder(n *node) {
50+
if n == nil {
51+
return
52+
}
53+
postorder(n.left)
54+
postorder(n.right)
55+
fmt.Print(n.val, " ")
56+
}
57+
58+
func levelorder(root *node) {
59+
var q []*node // queue
60+
var n *node // temporary node
61+
62+
q = append(q, root)
63+
64+
for len(q) != 0 {
65+
n, q = q[0], q[1:]
66+
fmt.Print(n.val, " ")
67+
if n.left != nil {
68+
q = append(q, n.left)
69+
}
70+
if n.right != nil {
71+
q = append(q, n.right)
72+
}
73+
}
74+
}
75+
76+
// helper function for t.depth
77+
func _calculate_depth(n *node, depth int) int {
78+
if n == nil {
79+
return depth
80+
}
81+
return max(_calculate_depth(n.left, depth+1), _calculate_depth(n.right, depth+1))
82+
}
83+
84+
func (t *btree) depth() int {
85+
return _calculate_depth(t.root, 0)
86+
}
87+
88+
/*
89+
func main() {
90+
t := btree{nil}
91+
t.root = newNode(0)
92+
t.root.left = newNode(1)
93+
t.root.right = newNode(2)
94+
t.root.left.left = newNode(3)
95+
t.root.left.right = newNode(4)
96+
t.root.right.left = newNode(5)
97+
t.root.right.right = newNode(6)
98+
t.root.right.right.right = newNode(10)
99+
100+
inorder(t.root)
101+
fmt.Print("\n")
102+
preorder(t.root)
103+
fmt.Print("\n")
104+
postorder(t.root)
105+
fmt.Print("\n")
106+
levelorder(t.root)
107+
fmt.Print("\n")
108+
fmt.Print(t.depth(), "\n")
109+
}
110+
*/

0 commit comments

Comments
 (0)