Golang以OO的方式实现二叉查找树

二叉查找树是一种满足如下性质的二叉树：

(1) 某个节点的左子树中的所有节点的值都比这个节点的值小

(2)某个节点的右子树中的所有节点的值都比这个节点的值大

下面有Go实现的非常详尽的代码，采用了Go风格的OO进行了封装。代码中主函数的例子的参照图如下：

这是我的二叉查找树的使用手册：

实现代码：

packagemain
2. import(
3. "fmt"
4. )
5. typeTreeNodestruct{
6. datafloat64
7. lchild*TreeNode
8. rchild*TreeNode
9. parent*TreeNode
10. }
12. typeBiSearchTreestruct{
13. root*TreeNode
14. cur*TreeNode
15. create*TreeNode
16. func(bst*BiSearchTree)Add(datafloat64){
17. bst.create=new(TreeNode)
18. bst.create.data=data
19. if!bst.IsEmpty(){
20. bst.cur=bst.root
21. for{
22. ifdata<bst.cur.data{
23. //如果要插入的值比当前节点的值小，则当前节点指向当前节点的左孩子，如果
24. //左孩子为空，就在这个左孩子上插入新值
25. ifbst.cur.lchild==nil{
26. bst.cur.lchild=bst.create
27. bst.create.parent=bst.cur
28. break
29. }else{
30. bst.cur=bst.cur.lchild
31. elseifdata>bst.cur.data{
32. //如果要插入的值比当前节点的值大，则当前节点指向当前节点的右孩子，如果
33. //右孩子为空，就在这个右孩子上插入新值
34. ifbst.cur.rchild==nil{
35. bst.cur.rchild=bst.create
36. bst.create.parent=bst.cur
37. break
38. }else{
39. bst.cur=bst.cur.rchild
40. }
41. //如果要插入的值在树中已经存在，则退出
42. return
43. bst.root=bst.create
44. bst.root.parent=nil
45. func(bst*BiSearchTree)Delete(datafloat64){
46. var(
47. deleteNodefunc(node*TreeNode)
48. node*TreeNode=bst.Search(data)
49. deleteNode=func(node*TreeNode){
50. ifnode==nil{
51. ifnode.lchild==nil&&node.rchild==nil{
52. //如果要删除的节点没有孩子，直接删掉它就可以(毫无挂念~.~!)
53. ifnode==bst.root{
54. bst.root=nil
55. ifnode.parent.lchild==node{
56. node.parent.lchild=nil
57. node.parent.rchild=nil
58. ifnode.lchild!=nil&&node.rchild==nil{
59. //如果要删除的节点只有左孩子或右孩子，让这个节点的父节点指向它的指针指向它的
60. //孩子即可
61. ifnode==bst.root{
62. node.lchild.parent=nil
63. bst.root=node.lchild
64. node.lchild.parent=node.parent
65. ifnode.parent.lchild==node{
66. node.parent.lchild=node.lchild
67. node.parent.rchild=node.lchild
68. ifnode.lchild==nil&&node.rchild!=nil{
69. node.rchild.parent=nil
70. bst.root=node.rchild
71. node.rchild.parent=node.parent
72. node.parent.lchild=node.rchild
73. node.parent.rchild=node.rchild
74. //如果要删除的节点既有左孩子又有右孩子，就把这个节点的直接后继的值赋给这个节
75. //点，然后删除直接后继节点即可
76. successor:=bst.GetSuccessor(node.data)
77. node.data=successor.data
78. deleteNode(successor)
79. deleteNode(node)
80. func(bstBiSearchTree)GetRoot()*TreeNode{
81. ifbst.root!=nil{
82. returnbst.root
83. returnnil
84. func(bstBiSearchTree)IsEmpty()bool{
85. ifbst.root==nil{
86. returntrue
87. false
88. func(bstBiSearchTree)InOrderTravel(){
89. varinOrderTravelfunc(node*TreeNode)
90. inOrderTravel=func(node*TreeNode){
91. ifnode!=nil{
92. inOrderTravel(node.lchild)
93. fmt.Printf("%g",node.data)
94. inOrderTravel(node.rchild)
95. inOrderTravel(bst.root)
96. func(bstBiSearchTree)Search(datafloat64)*TreeNode{
97. //和Add操作类似，只要按照比当前节点小就往左孩子上拐，比当前节点大就往右孩子上拐的思路
98. //一路找下去，知道找到要查找的值返回即可
99. ifbst.cur==nil{
100. bst.cur=bst.cur.lchild
101. ifdata>bst.cur.data{
102. returnbst.cur
103. func(bstBiSearchTree)GetDeepth()int{
104. vargetDeepthfunc(node*TreeNode)int
105. getDeepth=func(node*TreeNode)int{
106. ifnode==nil{
107. return0
108. 1
109. var(
110. ldeepthint=getDeepth(node.lchild)
111. rdeepthint=getDeepth(node.rchild)
112. )
113. ifldeepth>rdeepth{
114. returnldeepth+1
115. returnrdeepth+returngetDeepth(bst.root)
116. func(bstBiSearchTree)GetMin()float64{
117. //根据二叉查找树的性质，树中最左边的节点就是值最小的节点
118. ifbst.root==nil{
119. return- bst.cur=bst.root
120. for{
121. ifbst.cur.lchild!=nil{
122. returnbst.cur.data
123. func(bstBiSearchTree)GetMax()float64{
124. //根据二叉查找树的性质，树中最右边的节点就是值最大的节点
125. ifbst.cur.rchild!=nil{
126. returnbst.cur.data
127. func(bstBiSearchTree)GetPredecessor(datafloat64)*TreeNode{
128. getMax:=func(node*TreeNode)*TreeNode{
129. ifnode.rchild!=nil{
130. node=node.rchild
131. returnnode
132. node:=bst.Search(data)
133. ifnode.lchild!=nil{
134. //如果这个节点有左孩子，那么它的直接前驱就是它左子树的最右边的节点，因为比这
135. //个节点值小的节点都在左子树，而这些节点中值最大的就是这个最右边的节点
136. returngetMax(node.lchild)
137. //如果这个节点没有左孩子，那么就沿着它的父节点找，知道某个父节点的父节点的右
138. //孩子就是这个父节点，那么这个父节点的父节点就是直接前驱
139. ifnode==nil||node.parent==nil{
140. ifnode==node.parent.rchild{
141. returnnode.parent
142. node=node.parent
143. func(bstBiSearchTree)GetSuccessor(datafloat64)*TreeNode{
144. getMin:=func(node*TreeNode)*TreeNode{
145. node=node.lchild
146. //参照寻找直接前驱的函数对比着看
147. node:=bst.Search(data)
148. ifnode!=nil{
149. ifnode.rchild!=nil{
150. returngetMin(node.rchild)
151. ifnode==nil||node.parent==nil{
152. ifnode==node.parent.lchild{
153. returnnode.parent
154. node=node.parent
155. returnnil
156. func(bst*BiSearchTree)Clear(){
157. bst.cur=nil
158. bst.create=nil
159. funcmain(){
160. varbstBiSearchTree
161. bst.Add(15)
162. bst.Add(6)
163. 18)
164. 3)
165. 7)
166. 17)
167. 20)
168. 2)
169. 4)
170. 13)
171. 9)
172. 14)
173. fmt.Printf("ThenodesoftheBiSearchTreeis:")
174. bst.InOrderTravel()
175. fmt.Printf("n")
176. fmt.Printf("Thedeepthofthetreeis:%dn",bst.GetDeepth())
177. fmt.Printf("Theminis:%gn",bst.GetMin())
178. fmt.Printf("Themaxis:%gn",bst.GetMax())
179. ifbst.Search(17)!=nil{
180. fmt.Printf("The17exists.n")
181. fmt.Printf("rootnode'spredecessoris:%gn",bst.GetPredecessor(bst.GetRoot().data).data)
182. fmt.Printf("rootnode'ssuccessoris:%gn",bst.GetSuccessor(bst.GetRoot().data).data)
183. bst.Delete(13)
184. fmt.Printf("Nodesafterdeletethe13:")
185. }

如果转载请注明出处：http://blog.csdn.net/gophers/article/details/23552925

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!