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

Go 前端之家
前端之家收集整理的这篇文章主要介绍了Golang以OO的方式实现二叉查找树，前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。

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

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

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


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

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

[cpp] view plain copy
  1. typeBiSearchTreestruct
  2. func(bst*BiSearchTree)Add(datafloat64)//插入节点
  3. func(bst*BiSearchTree)Delete(datafloat64)//删除节点
  4. func(bstBiSearchTree)GetRoot()*TreeNode//获取根节点
  5. func(bstBiSearchTree)IsEmpty()bool//检查树是否为空
  6. func(bstBiSearchTree)InOrderTravel()//中序遍历(也就是从小到大输出)
  7. func(bstBiSearchTree)Search(datafloat64)*TreeNode//查找节点
  8. func(bstBiSearchTree)GetDeepth()int//获取树的深度
  9. func(bstBiSearchTree)GetMin()float64//获取值最小的节点
  10. func(bstBiSearchTree)GetMax()float64//获取值最大的节点
  11. func(bstBiSearchTree)GetPredecessor(datafloat64)*TreeNode//获取直接前驱
  12. func(bstBiSearchTree)GetSuccessor(datafloat64)*TreeNode//获取直接后继
  13. func(bst*BiSearchTree)Clear()//清空树

实现代码：

[java] copy
    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:%d\n",bst.GetDeepth())
  177. fmt.Printf("Theminis:%g\n",bst.GetMin())
  178. fmt.Printf("Themaxis:%g\n",bst.GetMax())
  179. ifbst.Search(17)!=nil{
  180. fmt.Printf("The17exists.\n")
  181. fmt.Printf("rootnode'spredecessoris:%g\n",bst.GetPredecessor(bst.GetRoot().data).data)
  182. fmt.Printf("rootnode'ssuccessoris:%g\n",bst.GetSuccessor(bst.GetRoot().data).data)
  183. bst.Delete(13)
  184. fmt.Printf("Nodesafterdeletethe13:")
  185. }


输出结果：

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

猜你在找的Go相关文章

golang简单实现jwt验证(beego、xorm、jwt)
程序目录结构 简单实现，用户登录后返回一个jwt的token，下次请求带上token请求用户信息接...
【工程实践】利用go语言写一个简单的Pow样例
本篇博客的主要内容是用go写一个简单的Proof-of-Work共识机制，不涉及到网络通信环节，只是...
【工程实践】go语言实现MerkleTree
简介 默克尔树（MerkleTree）是一种典型的二叉树结构，其主要特点为： 最下面的叶节点包含...
第九章 goroutine
接下来学习并发编程, 并发编程是go语言最有特色的地方, go对并发编程是原生支持. goroutin...
第十一章 运用广度优先搜索走迷宫
先普及一下, 什么是广度优先搜索 广度优先搜索类似于树的层次遍历。从图中的某一顶点出发，...
第十三章 go实现分布式网络爬虫---单机版爬虫
爬虫的分类 网络爬虫分为两类 1. 通用爬虫: 类似于baidu, google. 他们会把大量的数据挖下...
第十章 channel select 总结
感觉channel在理解起来还有点费劲的, 尤其是select的使用, 既要可以读数据, 又要可以写数据...
第十五章 并发版爬虫第二版 -- 完结
并发版爬虫, 在上一篇单机版爬虫的基础上演变而来 这里只有并发引擎的代码, 基本的解析器代...
第八章--性能优化--pprof详细研究
接着上次的博客:&#160;https://www.cnblogs.com/ITPower/articles/12315637.html ppro...
第八章 测试与性能调优--生成文档和测试示例代码
java也可以生成文档, 就像一个手册一样, 可以用来查看方法, 接口, 下面我们给go项目生成文...
PHPJavaJava SEPythonC#C&C++RubyVBasp.NetGoPerlnettyDjangoDelphiJsp.NET CoreSpringFlaskSpringbootSpringMVCLuaLaravelMybatisAspGroovyThinkPHPYiiswoole
文件时间pythonm相等性PHP Warning时间问题问题解决pcntl_signal采样点wav模块动态文本调用频率限制对外暴露多个访问请求更新数据表模型结构type()方法比较速度手写体sobel算子保存模型Image类nn.Conv2dpytorch1.0kaggleDCGAN交并比range()用法打印模型反卷积卷积