[关闭]
@aliasliyu4 2016-12-15T01:50:33.000000Z 字数 2069 阅读 1776

来,我们一起写一颗叫做二叉搜索树的🌲

前言

树这种结构我们应该是不陌生的,但是平时用到的机会还是比较少,借此机会我们一起来学习一下吧。
项目地址: https://github.com/liyu4/learn-algorithm-365/blob/master/tree/btr.go

  1. // tree provides implement of binary search trees
  2. package tree
  3. import (
  4. "fmt"
  5. "strings"
  6. )
  7. // 树中每一个节点包含的属性
  8. type Node struct {
  9. // 可以存储任意类型的数据
  10. element interface{}
  11. // 双亲
  12. parent *Node
  13. // 左孩子
  14. left *Node
  15. // 右孩子
  16. right *Node
  17. }
  18. //比较器,判断是走左子树还是右子树
  19. type comparer func(interface{}, interface{}) bool
  20. type Bst struct {
  21. compare comparer
  22. root *Node
  23. }
  24. // 创建一个空的二叉树
  25. func (b *Bst) New(compare comparer) *Bst {
  26. return &Bst{compare: compare}
  27. }
  28. // 中序遍历
  29. // 子树根的关键字位于左子树关键字和右子树关键字的中间
  30. func inorder_tree_walk(tree *Node) {
  31. if tree == nil {
  32. return
  33. }
  34. inorder_tree_walk(tree.left)
  35. fmt.Println(tree.element)
  36. inorder_tree_walk(tree.right)
  37. }
  38. // 查找一个具有给定关键字的节点,运行时间最坏情况为这颗树的高h, O(h)
  39. func (b *Bst) tree_search(tree *Node, element interface{}) *Node {
  40. if tree == nil {
  41. return nil
  42. }
  43. if tree.element == element {
  44. return tree
  45. }
  46. // 为真则走左,为假则走右
  47. if b.compare(element, tree.element) {
  48. return b.tree_search(tree.right, element)
  49. } else {
  50. return b.tree_search(tree.left, element)
  51. }
  52. }
  53. // 迭代法,避免递归的性能消耗, 你懂的
  54. func (b *Bst) iterative_tree_search(tree *Node, element interface{}) *Node {
  55. if tree == nil {
  56. return nil
  57. }
  58. for element != tree.element {
  59. if b.compare(element, tree.element) {
  60. tree = tree.right
  61. } else {
  62. tree = tree.left
  63. }
  64. }
  65. return tree
  66. }
  67. // 最小关键元素
  68. func (b *Bst) tree_minimum(tree *Node) *Node {
  69. for tree != nil {
  70. tree = tree.left
  71. }
  72. return tree
  73. }
  74. // 最大关键元素, 显然最大关键元素和最小关键元素都是由二叉树的性质决定的,并且它们的代码也是对称的。
  75. func (b *Bst) tree_maximum(tree *Node) *Node {
  76. for tree != nil {
  77. tree = tree.right
  78. }
  79. return tree
  80. }
  81. // 后继
  82. func (b *Bst) tree_successor(tree *Node) *Node {
  83. if tree.right != nil {
  84. return b.tree_minimum(tree.right)
  85. }
  86. y := tree.parent
  87. for y != nil && tree == y.right {
  88. tree = y
  89. y = y.parent
  90. }
  91. return y
  92. }
  93. // 前继
  94. func (b *Bst) tree_predecessor(tree *Node) *Node {
  95. if tree.left != nil {
  96. return b.tree_maximum(tree.left)
  97. }
  98. y := tree.parent
  99. for y != nil && tree == y.right {
  100. tree = y
  101. y = y.parent
  102. }
  103. return y
  104. }
  105. // 插入
  106. func (b *Bst) tree_insert(tree *Node, element interface{}) *Node {
  107. y := &Node{}
  108. for tree != nil {
  109. // y为双亲节点
  110. y = tree
  111. // 举例子n1 < n2 为真则走左, 为假则走右
  112. if b.compare(element, tree.element) {
  113. tree = tree.left
  114. } else {
  115. tree = tree.right
  116. }
  117. }
  118. var node *Node = &Node{element, nil, nil}
  119. node.parent = y
  120. // 说明是一颗空二叉搜索树
  121. if y == nil {
  122. b.root = node
  123. return node
  124. }
  125. // 寻找左边还是右边需要插入
  126. if b.compare(element, y.element) {
  127. y.left = node
  128. } else {
  129. y.right = node
  130. }
  131. return y
  132. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注