golang实现二叉搜索树

bigtom · · 2486 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

关于什么是二叉搜索树,不清楚的同学可以去看我写的这个数据结构与算法的网站

数据结构

首先我们定义需要的数据结构。注意,TreeNode的左右节点都是*TreeNode type的,而树只有一个Root数据域,为*TreeNode type

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

type BinarySearchTree struct {
  Root *TreeNode
}

Insert

向二叉搜索树中插入元素,首先要找到插入的位置,然后再插入。这里注意我们的实现方法为给TreeNode和BinarySearchTree这两个type添加方法。需要注意给type添加方法的方式,同时还要注意,如果你要改变方法调用者,则需要使用指针

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

遍历

树的遍历有前序,后序,中序等等。这里以中序为例。注意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
    }
  }
}

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:bigtom

查看原文:golang实现二叉搜索树

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

2486 次点击  
加入收藏 微博
3 回复  |  直到 2018-06-21 11:59:23
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传