golang实现二叉搜索树
bigtom ·关于什么是二叉搜索树,不清楚的同学可以去看我写的这个数据结构与算法的网站
数据结构
首先我们定义需要的数据结构。注意,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
}
}
}不可以这样用的
数组这个东西在扩容的时候,底部的指针会变,很容易发生不可预估的意外
所以不能用append来做处理,这是我修改后的
```go
//transfer a bt to a array asc sorted
func (bt *BinaryNode) ToAscArray(rs *[]interface{},flag *int){
if bt.Left!=nil {
bt.Left.ToAscArray(rs,flag)
}
(*rs)[*flag] = bt.Data
*flag++
if bt.Right!=nil{
bt.Right.ToAscArray(rs,flag)
}
}
```
#1
更多评论
像这样使用
```go
func TestBinaryNode_ToAscArray(t *testing.T) {
Init()
var sum = 0
var rs = make([]interface{},node.GetNodesNum(&sum))
var tmp =0
node.ToAscArray(&rs,&tmp)
t.Log(rs)
t.Log(tmp)
}
```
#2
封装一下
```go
//transfer a bt to an array desc escaping args
func (bt *BinaryNode) ToDescArrayEscapingArgs() []interface{} {
var sum int
var rs []interface{}
var flag int
bt.GetNodesNum(&sum)
rs = make([]interface{}, sum)
bt.ToDescArray(&rs, &flag)
return rs
}
```
#3
关于什么是二叉搜索树,不清楚的同学可以去看我写的这个数据结构与算法的网站
数据结构
首先我们定义需要的数据结构。注意,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
}
}
}