# Tree
树是树节点的集合。 每个树节点都有一个值，一个指向左节点的左指针和一个指向右节点的右指针。
# 源码
# 用法
import (
tree "github.com/duke-git/lancet/v2/datastructure/tree"
)
# 目录
# 1. BSTree
# 文档
# 1. BSTree
BSTree是一种二叉搜索树数据结构，其中每个节点有两个孩子，分别称为左孩子和右孩子。 在 BSTree 中：leftNode < rootNode < rightNode。 T类型应该实现lancetconstraints.Comparator。
# NewBSTree
返回BSTree指针实例
函数签名:
func NewBSTree[T any](rootData T, comparator lancetconstraints.Comparator) *BSTree[T]
type BSTree[T any] struct {
root *datastructure.TreeNode[T]
comparator lancetconstraints.Comparator
}
type TreeNode[T any] struct {
Value T
Left *TreeNode[T]
Right *TreeNode[T]
}
例子:
package main
import (
"fmt"
tree "github.com/duke-git/lancet/v2/datastructure/tree"
)
type intComparator struct{}
func (c *intComparator) Compare(v1, v2 any) int {
val1, _ := v1.(int)
val2, _ := v2.(int)
if val1 < val2 {
return -1
} else if val1 > val2 {
return 1
}
return 0
}
func main() {
bstree := tree.NewBSTree(6, &intComparator{})
fmt.Println(bstree) //
}
# Insert
将值插入二叉搜索树
函数签名:
func (t *BSTree[T]) Insert(data T)
例子:
package main
import (
"fmt"
tree "github.com/duke-git/lancet/v2/datastructure/tree"
)
type intComparator struct{}
func (c *intComparator) Compare(v1, v2 any) int {
val1, _ := v1.(int)
val2, _ := v2.(int)
if val1 < val2 {
return -1
} else if val1 > val2 {
return 1
}
return 0
}
func main() {
bstree := tree.NewBSTree(6, &intComparator{})
bstree.Insert(7)
bstree.Insert(5)
bstree.Insert(2)
bstree.Insert(4)
fmt.Println(bstree.PreOrderTraverse()) //6, 5, 2, 4, 7
}
# Delete
删除插入二叉搜索树中指定的值
函数签名:
func (t *BSTree[T]) Delete(data T)
例子:
package main
import (
"fmt"
tree "github.com/duke-git/lancet/v2/datastructure/tree"
)
type intComparator struct{}
func (c *intComparator) Compare(v1, v2 any) int {
val1, _ := v1.(int)
val2, _ := v2.(int)
if val1 < val2 {
return -1
} else if val1 > val2 {
return 1
}
return 0
}
func main() {
bstree := tree.NewBSTree(6, &intComparator{})
bstree.Insert(7)
bstree.Insert(5)
bstree.Insert(2)
bstree.Insert(4)
bstree.Delete(4)
fmt.Println(bstree.PreOrderTraverse()) //2, 5, 6, 7
}
# PreOrderTraverse
按前序遍历树节点
函数签名:
func (t *BSTree[T]) PreOrderTraverse() []T
例子:
package main
import (
"fmt"
tree "github.com/duke-git/lancet/v2/datastructure/tree"
)
type intComparator struct{}
func (c *intComparator) Compare(v1, v2 any) int {
val1, _ := v1.(int)
val2, _ := v2.(int)
if val1 < val2 {
return -1
} else if val1 > val2 {
return 1
}
return 0
}
func main() {
bstree := tree.NewBSTree(6, &intComparator{})
bstree.Insert(7)
bstree.Insert(5)
bstree.Insert(2)
bstree.Insert(4)
fmt.Println(bstree.PreOrderTraverse()) //6, 5, 2, 4, 7
}
# InOrderTraverse
按中序遍历树节点
函数签名:
func (t *BSTree[T]) InOrderTraverse() []T
例子:
package main
import (
"fmt"
tree "github.com/duke-git/lancet/v2/datastructure/tree"
)
type intComparator struct{}
func (c *intComparator) Compare(v1, v2 any) int {
val1, _ := v1.(int)
val2, _ := v2.(int)
if val1 < val2 {
return -1
} else if val1 > val2 {
return 1
}
return 0
}
func main() {
bstree := tree.NewBSTree(6, &intComparator{})
bstree.Insert(7)
bstree.Insert(5)
bstree.Insert(2)
bstree.Insert(4)
fmt.Println(bstree.InOrderTraverse()) //2, 4, 5, 6, 7
}
# PostOrderTraverse
按后序遍历树节点
函数签名:
func (t *BSTree[T]) PostOrderTraverse() []T
例子:
package main
import (
"fmt"
tree "github.com/duke-git/lancet/v2/datastructure/tree"
)
type intComparator struct{}
func (c *intComparator) Compare(v1, v2 any) int {
val1, _ := v1.(int)
val2, _ := v2.(int)
if val1 < val2 {
return -1
} else if val1 > val2 {
return 1
}
return 0
}
func main() {
bstree := tree.NewBSTree(6, &intComparator{})
bstree.Insert(7)
bstree.Insert(5)
bstree.Insert(2)
bstree.Insert(4)
fmt.Println(bstree.PostOrderTraverse()) //5, 2, 4, 7, 6
}
# LevelOrderTraverse
按节点层次遍历树节点
函数签名:
func (t *BSTree[T]) LevelOrderTraverse() []T
例子:
package main
import (
"fmt"
tree "github.com/duke-git/lancet/v2/datastructure/tree"
)
type intComparator struct{}
func (c *intComparator) Compare(v1, v2 any) int {
val1, _ := v1.(int)
val2, _ := v2.(int)
if val1 < val2 {
return -1
} else if val1 > val2 {
return 1
}
return 0
}
func main() {
bstree := tree.NewBSTree(6, &intComparator{})
bstree.Insert(7)
bstree.Insert(5)
bstree.Insert(2)
bstree.Insert(4)
fmt.Println(bstree.LevelOrderTraverse()) //6, 5, 7, 2, 4
}
# Depth
获取树的深度
函数签名:
func (t *BSTree[T]) Depth() int
例子:
package main
import (
"fmt"
tree "github.com/duke-git/lancet/v2/datastructure/tree"
)
type intComparator struct{}
func (c *intComparator) Compare(v1, v2 any) int {
val1, _ := v1.(int)
val2, _ := v2.(int)
if val1 < val2 {
return -1
} else if val1 > val2 {
return 1
}
return 0
}
func main() {
bstree := tree.NewBSTree(6, &intComparator{})
bstree.Insert(7)
bstree.Insert(5)
bstree.Insert(2)
bstree.Insert(4)
fmt.Println(bstree.Depth()) //4
}
# HasSubTree
判断给定树是否是子树
函数签名:
func (t *BSTree[T]) HasSubTree(subTree *BSTree[T]) bool
例子:
package main
import (
"fmt"
tree "github.com/duke-git/lancet/v2/datastructure/tree"
)
type intComparator struct{}
func (c *intComparator) Compare(v1, v2 any) int {
val1, _ := v1.(int)
val2, _ := v2.(int)
if val1 < val2 {
return -1
} else if val1 > val2 {
return 1
}
return 0
}
func main() {
superTree := tree.NewBSTree(8, &intComparator{})
superTree.Insert(4)
superTree.Insert(5)
superTree.Insert(6)
superTree.Insert(9)
superTree.Insert(4)
subTree := tree.NewBSTree(5, &intComparator{})
subTree.Insert(4)
subTree.Insert(6)
fmt.Println(superTree.HasSubTree(subTree)) //true
fmt.Println(subTree.HasSubTree(superTree)) //false
}
打印树结构
函数签名:
func (t *BSTree[T]) Print()
例子:
package main
import (
"fmt"
tree "github.com/duke-git/lancet/v2/datastructure/tree"
)
type intComparator struct{}
func (c *intComparator) Compare(v1, v2 any) int {
val1, _ := v1.(int)
val2, _ := v2.(int)
if val1 < val2 {
return -1
} else if val1 > val2 {
return 1
}
return 0
}
func main() {
bstree := tree.NewBSTree(6, &intComparator{})
bstree.Insert(7)
bstree.Insert(5)
bstree.Insert(2)
bstree.Insert(4)
fmt.Println(bstree.Print())
// 6
// / \
// / \
// / \
// / \
// 5 7
// /
// /
// 2
// \
// 4
}