8000 tests and traversal for binary_tree · developgo/algorithms_with_Go@226bf24 · GitHub
[go: up one dir, main page]
Skip to content

Commit 226bf24

Browse files
danruseidanrusei
committed
tests and traversal for binary_tree
1 parent 4c9dc85 commit 226bf24

File tree

3 files changed

+126
-2
lines changed

3 files changed

+126
-2
lines changed

‎binary_tree/README.md

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -18,8 +18,11 @@ In computer science, a binary tree is a tree data structure in which each node h
1818
* A **perfect binary** tree is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level.
1919
* A **balanced binary tree** is a binary tree structure in which the left and right subtrees of every node differ in height by no more than 1.
2020

21-
# Common operations
21+
## Common operations
2222

2323
* **Insertion** - Nodes can be inserted into binary trees in between two other nodes or added after a leaf node. In binary trees, a node that is inserted is specified as to which child it is.
2424
* **Deletion** - Deletion is the process whereby a node is removed from the tree. Only certain nodes in a binary tree can be removed unambiguously.
2525
* **Traversal** - Pre-order, in-order, and post-order traversal visit each node in a tree by recursively visiting each node in the left and right subtrees of the root.
26+
* **In-Order** -the left subtree is visited first, then the root and later the right sub-tree.
27+
* **Pre-Order** - the root node is visited first, then the left subtree and finally the right subtree.
28+
* **Post-order** - traverse the left subtree, then the right subtree and finally the root node.

‎binary_tree/binary_tree.go

Lines changed: 75 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,2 +1,76 @@
11
package binarytree
2-
2+
3+
import "fmt"
4+
5+
// Tree is a binary tree with integer values.
6+
type Tree struct {
7+
Value int
8+
Left *Tree
9+
Right *Tree
10+
}
11+
12+
// NewTree instantiate the binary tree
13+
func NewTree(k int) *Tree {
14+
return &Tree{
15+
Value: k,
16+
Left: nil,
17+
Right: nil,
18+
}
19+
20+
}
21+
22+
// Insert a new value to the binary tree
23+
func (t *Tree) Insert(val int) *Tree {
24+
if t == nil {
25+
return NewTree(val)
26+
}
27+
if val < t.Value {
28+
t.Left = t.Left.Insert(val)
29+
} else {
30+
t.Right = t.Right.Insert(val)
31+
}
32+
return t
33+
}
34+
35+
// InOrderTraverse - the left subtree is visited first, then the root and later the right sub-tree.
36+
func (t *Tree) InOrderTraverse(f func(int)) {
37+
if t != nil {
38+
t.Left.InOrderTraverse(f)
39+
f(t.Value)
40+
t.Right.InOrderTraverse(f)
41+
}
42+
}
43+
44+
// PreOrderTraverse - the root node is visited first, then the left subtree and finally the right subtree.
45+
func (t *Tree) PreOrderTraverse(f func(int)) {
46+
if t != nil {
47+
f(t.Value)
48+
t.Left.PreOrderTraverse(f)
49+
t.Right.PreOrderTraverse(f)
50+
}
51+
}
52+
53+
// PostOrderTraverse - traverse the left subtree, then the right subtree and finally the root node
54+
func (t *Tree) PostOrderTraverse(f func(int)) {
55+
if t != nil {
56+
t.Left.PostOrderTraverse(f)
57+
t.Right.PostOrderTraverse(f)
58+
f(t.Value)
59+
}
60+
}
61+
62+
// Used to print the binary tree
63+
func (t *Tree) String() string {
64+
if t == nil {
65+
return "()"
66+
}
67+
s := ""
68+
if t.Left != nil {
69+
s += t.Left.String() + " "
70+
}
71+
s += fmt.Sprint(t.Value)
72+
if t.Right != nil {
73+
s += " " + t.Right.String()
74+
}
75+
return "(" + s + ")"
76+
}

‎binary_tree/binary_tree_test.go

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
package binarytree
2+
3+
import "fmt"
4+
5+
func createTree() *Tree {
6+
bst := NewTree(5)
7+
bst.Insert(8).Insert(4).Insert(10).Insert(2).Insert(6).Insert(1).Insert(3).Insert(7).Insert(9)
8+
return bst
9+
}
10+
11+
func ExampleTreeInsert() {
12+
13+
bst := createTree()
14+
fmt.Println(bst)
15+
// Output:
16+
// ((((1) 2 (3)) 4) 5 ((6 (7)) 8 ((9) 10)))
17+
}
18+
19+
func ExampleInOrderTraverse() {
20+
21+
bst := createTree()
22+
bst.InOrderTraverse(func(i int) {
23+
fmt.Printf("%d\t", i)
24+
})
25+
// Output:
26+
// 1 2 3 4 5 6 7 8 9 10
27+
}
28+
29+
func ExamplePreOrderTraverse() {
30+
31+
bst := createTree()
32+
bst.PreOrderTraverse(func(i int) {
33+
fmt.Printf("%d\t", i)
34+
})
35+
// Output:
36+
// 5 4 2 1 3 8 6 7 10 9
37+
}
38+
39+
func ExamplePostOrderTraverse() 5EF3 {
40+
41+
bst := createTree()
42+
bst.PostOrderTraverse(func(i int) {
43+
fmt.Printf("%d\t", i)
44+
})
45+
// Output:
46+
// 1 3 2 4 7 6 9 10 8 5
47+
}

0 commit comments

Comments
 (0)
0