關(guān)于什么是二叉搜索樹线欲，不清楚的同學(xué)可以去看我寫的這個數(shù)據(jù)結(jié)構(gòu)與算法的網(wǎng)站
數(shù)據(jù)結(jié)構(gòu)
首先我們定義需要的數(shù)據(jù)結(jié)構(gòu)。注意绑莺，TreeNode的左右節(jié)點都是*TreeNode type的，而樹只有一個Root數(shù)據(jù)域颤绕，為*TreeNode type
type TreeNode struct {
Value int
Left *TreeNode
Right *TreeNode
}
type BinarySearchTree struct {
Root *TreeNode
}
Insert
向二叉搜索樹中插入元素，首先要找到插入的位置祟身，然后再插入奥务。這里注意我們的實現(xiàn)方法為給TreeNode和BinarySearchTree這兩個type添加方法。需要注意給type添加方法的方式袜硫，同時還要注意氯葬，如果你要改變方法調(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}
}
}
}
遍歷
樹的遍歷有前序父款，后序溢谤，中序等等。這里以中序為例憨攒。注意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
}
}
}
