53 lines
844 B
Go
53 lines
844 B
Go
|
package tree
|
||
|
|
|
||
|
|
// A Tree Structure
|
||
|
|
type Tree[T any] struct {
|
||
|
|
value T
|
||
|
|
children []*Tree[T]
|
||
|
|
}
|
||
|
|
|
||
|
|
func (tree *Tree[T]) dfs(handle func(*T)) {
|
||
|
|
handle(&tree.value)
|
||
|
|
for _, child := range tree.children {
|
||
|
|
if child != nil {
|
||
|
|
child.dfs(handle)
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// DFS Depth-first Search
|
||
|
|
func (tree *Tree[T]) DFS(handle func(*T)) {
|
||
|
|
if tree == nil {
|
||
|
|
return
|
||
|
|
}
|
||
|
|
if handle == nil {
|
||
|
|
handle = func(*T) {}
|
||
|
|
}
|
||
|
|
tree.dfs(handle)
|
||
|
|
}
|
||
|
|
|
||
|
|
func (tree *Tree[T]) bfs(handle func(*T)) {
|
||
|
|
var tmp []*Tree[T]
|
||
|
|
for _, child := range tree.children {
|
||
|
|
if child != nil {
|
||
|
|
handle(&child.value)
|
||
|
|
tmp = append(tmp, child)
|
||
|
|
}
|
||
|
|
}
|
||
|
|
for _, child := range tmp {
|
||
|
|
child.bfs(handle)
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// BFS Breadth-first Search
|
||
|
|
func (tree *Tree[T]) BFS(handle func(*T)) {
|
||
|
|
if tree == nil {
|
||
|
|
return
|
||
|
|
}
|
||
|
|
if handle == nil {
|
||
|
|
handle = func(*T) {}
|
||
|
|
}
|
||
|
|
handle(&tree.value)
|
||
|
|
tree.bfs(handle)
|
||
|
|
}
|