golang实现二叉搜索树

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

数据结构

首先我们定义需要的数据结构。注意,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实现二叉搜索树

• 编辑
• 预览