treex

package
v1.1.19 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Feb 26, 2025 License: MIT Imports: 2 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func LevelOrderTraversal 

func LevelOrderTraversal[ID comparable, T any, N TreeNode[ID, T], O NodeOperator[ID, T, N]](roots []N, operator O, fn func(N))

LevelOrderTraversal performs a level-order (breadth-first) traversal of the tree. The traversal visits all nodes at the current depth before moving to nodes at the next depth level. Example: 

tree:     1
        /   \
       2     3
      /
     4

LevelOrderTraversal will visit nodes in order: 1, 2, 3, 4

func PostorderTraversal 

func PostorderTraversal[ID comparable, T any, N TreeNode[ID, T], O NodeOperator[ID, T, N]](roots []N, operator O, fn func(N))

PostorderTraversal performs a post-order traversal of the tree. The traversal recursively visits all subtrees first, then visits the root node. Example: 

tree:     1
        /   \
       2     3
      /
     4

PostorderTraversal will visit nodes in order: 4, 2, 3, 1

func PreorderTraversal 

func PreorderTraversal[ID comparable, T any, N TreeNode[ID, T], O NodeOperator[ID, T, N]](roots []N, operator O, fn func(N))

PreorderTraversal performs a pre-order traversal of the tree. The traversal visits the root node first, then recursively traverses each subtree. Example: 

tree:     1
        /   \
       2     3
      /
     4

PreorderTraversal will visit nodes in order: 1, 2, 4, 3

Types

type HashNode 

type HashNode[ID comparable, T any] struct {
	Id       ID
	Path     []ID // Path from root to this node, including this node.
	Parent   *HashNode[ID, T]
	Children map[ID]*HashNode[ID, T]
	Value    T
}

HashNode represents a node in a tree structure that uses a hash map to store children. This implementation allows for O(1) child lookup by ID. Type parameters:

  • ID: The type of node identifier, must be comparable
  • T: The type of value stored in the node

func (*HashNode[ID, T]) GetChildren 

func (n *HashNode[ID, T]) GetChildren() map[ID]*HashNode[ID, T]

func (*HashNode[ID, T]) GetId 

func (n *HashNode[ID, T]) GetId() ID

func (*HashNode[ID, T]) GetParent 

func (n *HashNode[ID, T]) GetParent() *HashNode[ID, T]

func (*HashNode[ID, T]) GetPath 

func (n *HashNode[ID, T]) GetPath() []ID

func (*HashNode[ID, T]) GetValue 

func (n *HashNode[ID, T]) GetValue() T

func (*HashNode[ID, T]) IsLeaf 

func (n *HashNode[ID, T]) IsLeaf() bool

func (*HashNode[ID, T]) IsRoot 

func (n *HashNode[ID, T]) IsRoot() bool

func (*HashNode[ID, T]) Size 

func (n *HashNode[ID, T]) Size() int

type HashNodeOperator 

type HashNodeOperator[ID comparable, T any] struct{}

HashNodeOperator provides operations for HashNode trees. It implements the NodeOperator interface for HashNode types.

func (HashNodeOperator[ID, T]) AddChild 

func (HashNodeOperator[ID, T]) AddChild(node *HashNode[ID, T], child *HashNode[ID, T])

func (HashNodeOperator[ID, T]) Children 

func (HashNodeOperator[ID, T]) Children(node *HashNode[ID, T]) []*HashNode[ID, T]

func (HashNodeOperator[ID, T]) Parent 

func (HashNodeOperator[ID, T]) Parent(node *HashNode[ID, T]) *HashNode[ID, T]

type LevelOrderTrees 

type LevelOrderTrees[ID comparable, T any, N TreeNode[ID, T], O NodeOperator[ID, T, N]] struct {
	Trees[ID, T, N, O]
}

LevelOrderTrees wraps Trees to provide level-order traversal of node values. This type implements Container[T] instead of Container[N], allowing direct access to stored values rather than nodes.

func (*LevelOrderTrees[ID, T, N, O]) ForEach 

func (t *LevelOrderTrees[ID, T, N, O]) ForEach(fn func(T))

ForEach executes the given function for each node's value in level-order traversal. Implements Container[T].ForEach().

type NodeOperator 

type NodeOperator[ID comparable, T any, N TreeNode[ID, T]] interface {
	// Parent returns the parent node of the given node
	// Returns nil if the node is a root
	Parent(node N) N
	// Children returns all direct child nodes of the given node
	Children(node N) []N
	// AddChild adds a child node to the given parent node
	// This operation should update the child's parent reference and path
	AddChild(node N, child N)
}

NodeOperator defines operations that can be performed on tree nodes. Type parameters:

  • ID: The type of node identifier, must be comparable
  • T: The type of value stored in the node
  • N: The concrete type implementing TreeNode interface

type OrderedNode 

type OrderedNode[ID comparable, T any] struct {
	Id       ID
	Path     []ID // Path from root to this node, including this node.
	Parent   *OrderedNode[ID, T]
	Children []*OrderedNode[ID, T]
	Value    T
}

OrderedNode represents a node in a tree structure that maintains children in an ordered slice. This implementation preserves the order of child nodes as they are added. Type parameters:

  • ID: The type of node identifier, must be comparable
  • T: The type of value stored in the node

func (*OrderedNode[ID, T]) GetChildren 

func (n *OrderedNode[ID, T]) GetChildren() []*OrderedNode[ID, T]

func (*OrderedNode[ID, T]) GetId 

func (n *OrderedNode[ID, T]) GetId() ID

func (*OrderedNode[ID, T]) GetParent 

func (n *OrderedNode[ID, T]) GetParent() *OrderedNode[ID, T]

func (*OrderedNode[ID, T]) GetPath 

func (n *OrderedNode[ID, T]) GetPath() []ID

func (*OrderedNode[ID, T]) GetValue 

func (n *OrderedNode[ID, T]) GetValue() T

func (*OrderedNode[ID, T]) IsLeaf 

func (n *OrderedNode[ID, T]) IsLeaf() bool

func (*OrderedNode[ID, T]) IsRoot 

func (n *OrderedNode[ID, T]) IsRoot() bool

func (*OrderedNode[ID, T]) Size 

func (n *OrderedNode[ID, T]) Size() int

type OrderedNodeOperator 

type OrderedNodeOperator[ID comparable, T any] struct{}

OrderedNodeOperator provides operations for OrderedNode trees. It implements the NodeOperator interface for OrderedNode types.

func (OrderedNodeOperator[ID, T]) AddChild 

func (OrderedNodeOperator[ID, T]) AddChild(node *OrderedNode[ID, T], child *OrderedNode[ID, T])

func (OrderedNodeOperator[ID, T]) Children 

func (OrderedNodeOperator[ID, T]) Children(node *OrderedNode[ID, T]) []*OrderedNode[ID, T]

func (OrderedNodeOperator[ID, T]) Parent 

func (OrderedNodeOperator[ID, T]) Parent(node *OrderedNode[ID, T]) *OrderedNode[ID, T]

type PostorderTrees 

type PostorderTrees[ID comparable, T any, N TreeNode[ID, T], O NodeOperator[ID, T, N]] struct {
	Trees[ID, T, N, O]
}

PostorderTrees wraps Trees to provide post-order traversal of node values. This type implements Container[T] instead of Container[N], allowing direct access to stored values rather than nodes.

func (*PostorderTrees[ID, T, N, O]) ForEach 

func (t *PostorderTrees[ID, T, N, O]) ForEach(fn func(T))

ForEach executes the given function for each node's value in post-order traversal. Implements Container[T].ForEach().

type PreorderTrees 

type PreorderTrees[ID comparable, T any, N TreeNode[ID, T], O NodeOperator[ID, T, N]] struct {
	Trees[ID, T, N, O]
}

PreorderTrees wraps Trees to provide pre-order traversal of node values. This type implements Container[T] instead of Container[N], allowing direct access to stored values rather than nodes.

func (*PreorderTrees[ID, T, N, O]) ForEach 

func (t *PreorderTrees[ID, T, N, O]) ForEach(fn func(T))

ForEach executes the given function for each node's value in pre-order traversal. Implements Container[T].ForEach().

type TreeNode 

type TreeNode[ID comparable, T any] interface {
	// GetId returns the unique identifier of this node
	GetId() ID
	// GetPath returns the path from root to this node, including this node's ID
	GetPath() []ID
	// GetValue returns the value stored in this node
	GetValue() T
	// Size returns the total number of nodes in the subtree rooted at this node
	Size() int
}

TreeNode represents a node in a tree structure. Type parameters:

  • ID: The type of node identifier, must be comparable
  • T: The type of value stored in the node

type Trees 

type Trees[ID comparable, T any, N TreeNode[ID, T], O NodeOperator[ID, T, N]] struct {
	Roots []N
}

Trees represents a forest (collection of trees). Type parameters:

  • ID: The type of node identifier, must be comparable
  • T: The type of value stored in nodes
  • N: The concrete type implementing TreeNode interface
  • O: The concrete type implementing NodeOperator interface

func New 

func New[ID comparable, T any, N TreeNode[ID, T], O NodeOperator[ID, T, N]]() *Trees[ID, T, N, O]

New creates a new empty Trees instance. Type parameters follow the same constraints as Trees.

func (*Trees[ID, T, N, O]) Clear 

func (t *Trees[ID, T, N, O]) Clear()

Clear removes all trees from the forest. Implements Container.Clear().

func (*Trees[ID, T, N, O]) ForEach 

func (t *Trees[ID, T, N, O]) ForEach(fn func(N))

func (*Trees[ID, T, N, O]) GetRoots 

func (t *Trees[ID, T, N, O]) GetRoots() []N

GetRoots returns the root nodes of all trees in the forest.

func (*Trees[ID, T, N, O]) IsEmpty 

func (t *Trees[ID, T, N, O]) IsEmpty() bool

IsEmpty returns true if there are no trees in the forest. Implements Container.IsEmpty().

func (*Trees[ID, T, N, O]) Len 

func (t *Trees[ID, T, N, O]) Len() int

Len returns the total number of nodes in all trees. Implements Container.Len().

func (*Trees[ID, T, N, O]) LevelOrderTraversal 

func (t *Trees[ID, T, N, O]) LevelOrderTraversal(fn func(N))

func (*Trees[ID, T, N, O]) PostorderTraversal 

func (t *Trees[ID, T, N, O]) PostorderTraversal(fn func(N))

func (*Trees[ID, T, N, O]) PreorderTraversal 

func (t *Trees[ID, T, N, O]) PreorderTraversal(fn func(N))

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.