# golang实现二叉搜索树

bigtom · · 2738 次点击 · · 开始浏览

## 数据结构

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

type BinarySearchTree struct {
Root *TreeNode
}``````

## Insert

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

## 遍历

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

3 回复  |  直到 2018-06-21 11:59:23

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、``单行代码``
• 支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传

## 数据结构

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

type BinarySearchTree struct {
Root *TreeNode
}``````

## Insert

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

## 遍历

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