golang实现二进制搜索树

关于什么是二叉搜索树，不清楚的学生可以访问我编写的数据结构和算法的网站

首先，我们定义所需的数据结构. 请注意，TreeNode的左右节点均为* TreeNode类型，并且树只有一个Root数据字段，即* TreeNode类型

type TreeNode struct {
  Value int
  Left *TreeNode
  Right *TreeNode
}
type BinarySearchTree struct {
  Root *TreeNode
}

将元素插入二进制搜索树，首先找到插入位置实现二叉排序树，然后插入. 注意这里我们的实现方法是将方法添加到TreeNode和BinarySearchTree的两种类型中. 注意如何向类型中添加方法，并注意，如果要更改方法调用者，则需要使用指针

func (tree BinarySearchTree) Insert (v int) {
  tree.Root.Insert(v)
}
func (node *TreeNode) Insert (v int){
  if v < node.Value {
    if node.Left != nil{
      node.Left.Insert(v)
    }else{
      node.Left = &TreeNode{v, nil, nil}
    }
  }else {
    if node.Right != nil{
      node.Right.Insert(v)
    }else{
      node.Right = &TreeNode{v, nil, nil}
    }
  }
}

树遍历具有前顺序，后顺序实现二叉排序树，中间顺序等. 这里以中间顺序为例. 注意切片指针和切片指针之间的区别

func (tree BinarySearchTree) InOrder() []int{
  var res []int
  tree.Root.InOrder(&res)
  return res
}
func (node *TreeNode) InOrder(result *[]int) {
  if node.Left != nil{
    node.Left.InOrder(result)
  }
  *result = append(*result, node.Value)
  if node.Right != nil{
    node.Right.InOrder(result)
  }
}

func (tree BinarySearchTree) FindMin() int {
  node := tree.Root
  for {
    if node.Left != nil {
      node = node.Left
    }else{
      return node.Value
    }
  }
}
func (tree BinarySearchTree) FindMax() int {
  node := tree.Root
  for {
    if node.Right != nil {
      node = node.Right
    }else{
      return node.Value
    }
  }
}

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-216714-1.html