关于什么是二叉搜索树，不清楚的同学可以去看我写的这个数据结构与算法的网站
数据结构
首先我们定义需要的数据结构。注意，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
}
}
}有疑问加站长微信联系（非本文作者）
