Skip to content

Commit b466da4

Browse files
JuntaranJuntaran
committed
2017.4.18
Data structure finished
1 parent 7e7d413 commit b466da4

File tree

5 files changed

+358
-0
lines changed

5 files changed

+358
-0
lines changed

‎Data_Structure/Binary_Tree/bst.go

Lines changed: 279 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,279 @@
1+
/**
2+
* Author: Juntaran
3+
* Email: Jacinthmail@gmail.com
4+
* Date: 2017/4/17 15:33
5+
*/
6+
7+
package Binary_Tree
8+
9+
import (
10+
"errors"
11+
"fmt"
12+
)
13+
14+
// 树节点结构
15+
type TreeNode struct {
16+
Value int
17+
parent *TreeNode
18+
lchild *TreeNode
19+
rchild *TreeNode
20+
}
21+
22+
// 树结构
23+
type Tree struct {
24+
Head *TreeNode
25+
Size int
26+
}
27+
28+
29+
// 创建一个节点
30+
func NewNode(value int) *TreeNode {
31+
newNode := &TreeNode{
32+
Value: value,
33+
}
34+
return newNode
35+
}
36+
37+
// 对比节点值
38+
func (node *TreeNode) Compare(m *TreeNode) int {
39+
if node.Value < m.Value {
40+
return -1
41+
} else if node.Value > m.Value {
42+
return 1
43+
} else {
44+
return 0
45+
}
46+
}
47+
48+
// 创建一棵树
49+
func NewTree(node *TreeNode) *Tree {
50+
if node == nil {
51+
return &Tree{}
52+
}
53+
return &Tree{
54+
Head: node,
55+
Size: 1,
56+
}
57+
}
58+
59+
// 插入元素
60+
func (tree *Tree)Insert(value int) {
61+
node := NewNode(value) // node是待插入节点
62+
if tree.Size == 0 {
63+
tree.Head = node
64+
tree.Size ++
65+
return
66+
}
67+
head := tree.Head
68+
for {
69+
if node.Compare(head) == -1 {
70+
if head.lchild == nil {
71+
head.lchild = node
72+
node.parent = head
73+
break
74+
} else {
75+
head = head.lchild
76+
}
77+
} else {
78+
if head.rchild == nil {
79+
head.rchild = node
80+
node.parent = head
81+
break
82+
} else {
83+
head = head.rchild
84+
}
85+
}
86+
}
87+
tree.Size ++
88+
}
89+
90+
// 搜索元素
91+
func (tree *Tree) Search(value int) (*TreeNode, error) {
92+
head := tree.Head // 待搜索的树
93+
node := NewNode(value) // 待搜索元素
94+
95+
for head != nil {
96+
switch head.Compare(node) {
97+
case -1:
98+
head = head.rchild
99+
case 1:
100+
head = head.lchild
101+
case 0:
102+
return head, nil
103+
default:
104+
err := errors.New("Node not Found")
105+
return nil, err
106+
}
107+
}
108+
err := errors.New("Error: Search Node not Found")
109+
return nil, err
110+
}
111+
112+
// 删除元素
113+
func (tree *Tree) Delete(value int) error {
114+
count := 0
115+
Search:
116+
_, err := tree.Search(value)
117+
//fmt.Println(ret.Value)
118+
// 该元素不存在
119+
if err != nil { // err != nil 表示没有搜索到这个元素
120+
if count == 0 {
121+
return errors.New("Error: Delete not Found")
122+
}
123+
return nil
124+
}
125+
126+
var parent *TreeNode
127+
head := tree.Head
128+
node := NewNode(value)
129+
for node != nil {
130+
switch node.Compare(head) {
131+
case -1:
132+
parent = head
133+
head = head.lchild
134+
case 1:
135+
parent = head
136+
head = head.rchild
137+
case 0:
138+
// 找到的节点是叶子节点
139+
if head.lchild == nil && head.rchild == nil {
140+
if parent.lchild == head {
141+
parent.lchild = nil
142+
} else {
143+
parent.rchild = nil
144+
}
145+
count ++
146+
tree.Size --
147+
goto Search
148+
}
149+
// 搜索到该节点，且该节点左孩子不为空
150+
if head.lchild != nil {
151+
right := head.rchild
152+
temp := head.lchild.rchild
153+
head.Value = head.lchild.Value
154+
head.lchild = head.lchild.lchild
155+
if head.lchild != nil {
156+
head.lchild.parent = head
157+
}
158+
head.rchild = temp
159+
if head.rchild != nil {
160+
head.rchild.parent = head
161+
}
162+
// 如果搜索到的节点有右孩子
163+
if right != nil {
164+
// 循环，一直找左子树的最右节点
165+
tempHead := head
166+
for tempHead.rchild != nil {
167+
tempHead = tempHead.rchild
168+
}
169+
tempHead.rchild = right
170+
right.parent = tempHead
171+
}
172+
tree.Size --
173+
count ++
174+
goto Search
175+
}
176+
// 搜索到该节点，且该节点没有左孩子，只有右孩子且不为空
177+
if head.rchild != nil {
178+
head.Value = head.rchild.Value
179+
head.lchild = head.rchild.lchild
180+
if head.lchild != nil {
181+
head.lchild.parent = head
182+
}
183+
head.rchild = head.rchild.rchild
184+
if head.rchild != nil {
185+
head.rchild.parent = head
186+
}
187+
tree.Size --
188+
count ++
189+
goto Search
190+
}
191+
// 如果这棵树只有一个节点，就是待删除节点
192+
if parent == nil {
193+
tree.Head = nil
194+
tree.Size --
195+
count ++
196+
return nil
197+
}
198+
199+
}
200+
}
201+
return errors.New("Error: Delete not Found")
202+
}
203+
204+
// 树的遍历
205+
// 前序遍历
206+
func (tree *Tree)PreOrderTraverse() {
207+
fmt.Println("Start PrenOrderTraverse")
208+
preOrder(tree.Head)
209+
fmt.Println()
210+
}
211+
func preOrder(root *TreeNode) {
212+
if root == nil {
213+
return
214+
}
215+
fmt.Printf("%4d ", root.Value)
216+
preOrder(root.lchild)
217+
preOrder(root.rchild)
218+
return
219+
}
220+
221+
// 中序遍历
222+
func (tree *Tree)InOrderTraverse() {
223+
fmt.Println("Start InOrderTraverse")
224+
inOrder(tree.Head)
225+
fmt.Println()
226+
}
227+
func inOrder(root *TreeNode) {
228+
if root == nil {
229+
return
230+
}
231+
inOrder(root.lchild)
232+
fmt.Printf("%4d ", root.Value)
233+
inOrder(root.rchild)
234+
return
235+
}
236+
237+
// 后序遍历
238+
func (tree *Tree)PostOrderTraverse() {
239+
fmt.Println("Start PostOrderTraverse")
240+
postOrder(tree.Head)
241+
fmt.Println()
242+
}
243+
func postOrder(root *TreeNode) {
244+
if root == nil {
245+
return
246+
}
247+
postOrder(root.lchild)
248+
postOrder(root.rchild)
249+
fmt.Printf("%4d ", root.Value)
250+
return
251+
}
252+
253+
// 层序遍历
254+
func (tree *Tree)LevelTraverse() {
255+
fmt.Println("Start LevelTraverse")
256+
if tree.Head == nil {
257+
return
258+
}
259+
root := tree.Head
260+
var treeQueue []*TreeNode
261+
treeQueue = append(treeQueue, root)
262+
var current int = 0
263+
var last int = 1
264+
for current < len(treeQueue) {
265+
last = len(treeQueue)
266+
for current < last {
267+
fmt.Printf("%4d ", treeQueue[current].Value)
268+
if treeQueue[current].lchild != nil {
269+
treeQueue = append(treeQueue, treeQueue[current].lchild)
270+
}
271+
if treeQueue[current].rchild != nil {
272+
treeQueue = append(treeQueue, treeQueue[current].rchild)
273+
}
274+
current ++
275+
}
276+
fmt.Println()
277+
}
278+
fmt.Println()
279+
}

‎Data_Structure/Binary_Tree/main/main.go

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
/**
2+
* Author: Juntaran
3+
* Email: Jacinthmail@gmail.com
4+
* Date: 2017/4/17 15:53
5+
*/
6+
7+
package main
8+
9+
import (
10+
"Golang_Algorithm/Data_Structure/Binary_Tree"
11+
"fmt"
12+
"log"
13+
)
14+
15+
func main() {
16+
n := Binary_Tree.NewNode(1)
17+
tree := Binary_Tree.NewTree(n)
18+
19+
tree.Insert(4)
20+
tree.Insert(2)
21+
tree.Insert(6)
22+
tree.Insert(3)
23+
tree.Insert(5)
24+
tree.Insert(6)
25+
tree.Insert(4)
26+
27+
tree.PreOrderTraverse()
28+
tree.InOrderTraverse()
29+
tree.PostOrderTraverse()
30+
tree.LevelTraverse()
31+
32+
fmt.Println("size:", tree.Size)
33+
34+
m, err := tree.Search(2)
35+
if err != nil {
36+
log.Println(err)
37+
} else {
38+
fmt.Println(m.Value)
39+
}
40+
err = tree.Delete(4)
41+
if err != nil {
42+
log.Println(err)
43+
}
44+
45+
m, err = tree.Search(6)
46+
if err != nil {
47+
log.Println(err)
48+
} else {
49+
fmt.Println(m.Value)
50+
}
51+
fmt.Println("size:", tree.Size)
52+
}

‎Data_Structure/Queue/main/main.go

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -25,6 +25,13 @@ func main() {
2525
fmt.Println("Length is", testQueue.LenQueue())
2626
fmt.Println("isEmpty:", testQueue.IsEmpty())
2727

28+
ret, err := testQueue.Pos(3)
29+
if err != nil {
30+
log.Println(err)
31+
} else {
32+
fmt.Println(ret)
33+
}
34+
2835
for i := 0; i < 15; i++ {
2936
item, err := testQueue.Dequeue()
3037
if err != nil {

‎Data_Structure/Queue/queue.go

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -102,4 +102,20 @@ func (queue *Queue) PrintQueue() {
102102
}
103103
fmt.Println()
104104
}
105+
}
106+
107+
// 返回队列指定位置元素
108+
func (queue *Queue) Pos(index int) (interface{}, error) {
109+
queue.lock.Lock()
110+
defer queue.lock.Unlock()
111+
{
112+
if index >= queue.length || index < 0 {
113+
return nil, errors.New("Error: Pos Index Out of Range")
114+
}
115+
var temp = queue.current
116+
for i := 0; i < index; i++ {
117+
temp = temp.next
118+
}
119+
return temp.queueEle, nil
120+
}
105121
}

‎README.md

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,10 @@
11
# Golang Algorithm
22

33
This repository stores some Data Structures and Alogorithms implemented with Golang.
4+
I finished data structures in 2017.4.18
5+
My search/sort algorithms implemented by C language can refer to the following:
6+
* [Search](http://www.cnblogs.com/Juntaran/p/5729988.html)
7+
* [Sort](http://www.cnblogs.com/Juntaran/p/5709618.html)
48

59
Reference:
610
* [0xAX](https://github.com/0xAX/go-algorithms)

0 commit comments

Comments
 (0)