關(guān)于什么是二叉搜索樹，不清楚的同學(xué)可以去看我寫的這個(gè)數(shù)據(jù)結(jié)構(gòu)與算法的網(wǎng)站

數(shù)據(jù)結(jié)構(gòu)

首先我們定義需要的數(shù)據(jù)結(jié)構(gòu)。注意，TreeNode的左右節(jié)點(diǎn)都是*TreeNode type的，而樹只有一個(gè)Root數(shù)據(jù)域，為*TreeNode type

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

type BinarySearchTree struct {
  Root *TreeNode
}

Insert

向二叉搜索樹中插入元素，首先要找到插入的位置，然后再插入。這里注意我們的實(shí)現(xiàn)方法為給TreeNode和BinarySearchTree這兩個(gè)type添加方法。需要注意給type添加方法的方式，同時(shí)還要注意，如果你要改變方法調(diào)用者，則需要使用指針

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}
    }
  }
}

遍歷

樹的遍歷有前序，后序，中序等等。這里以中序?yàn)槔?。注意slice與slice指針的不同

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
    }
  }
}

查找

func (tree BinarySearchTree) Contains(v int) bool {
  node := tree.Root
  for {
    if node == nil{
      return false
    }else if (node.Value == v) {
      return true
    }else if (node.Value > v){
      node = node.Left
    }else{
      node = node.Right
    }
  }
}