Documentation
¶
Overview ¶
Package tree provides search algorithms on trees.
For better performance, all functions in this package are unsafe for concurrency unless otherwise specified.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Bfs ¶
func Bfs(itf Interface, goal interface{}) interface{}
Bfs finds goal in itf using breadth-first search algorithm, and returns the goal node found.
It returns nil if goal is not found.
goal is only used to call the method SetGoal of itf. It's OK to handle goal in your implementation of Interface, and set goal to an arbitrary value, such as nil.
func BfsPath ¶
func BfsPath(itf Interface, goal interface{}) []interface{}
BfsPath is similar to function Bfs, except that it returns the path from the root of itf to the goal node found, instead of only the goal node.
It returns nil if goal is not found.
func Dfs ¶
func Dfs(itf Interface, goal interface{}) interface{}
Dfs finds goal in itf using depth-first search algorithm, and returns the goal node found.
It returns nil if goal is not found.
goal is only used to call the method SetGoal of itf. It's OK to handle goal in your implementation of Interface, and set goal to an arbitrary value, such as nil.
Types ¶
type Interface ¶
type Interface interface { // Root returns the root of the tree. Root() interface{} // FirstChild returns the first child of the specified node. // // If the node has no child, FirstChild returns nil. FirstChild(node interface{}) interface{} // NextSibling returns the next sibling of the specified node, // i.e., the next child of the parent of the specified node. // // If the node is the root or the last child of its parent, // NextSibling returns nil. NextSibling(node interface{}) interface{} // SetGoal sets the search goal. // // It will be called once at the beginning of the search functions. // // Its implementation can do initialization for each search in this method. SetGoal(goal interface{}) // Access examines the specified node. // // It returns an indicator found to reports whether the specified node // is the search goal. // // Sometimes it is also referred to as "visit". Access(node interface{}) (found bool) }
Interface represents a tree used in the tree search algorithm.