tree

type FullTree ¶

type FullTree struct {
	// contains filtered or unexported fields
}

FullTree is a tree where each non-leaf vertex has N children. N is the degree. For a full tree of height H and degree D, the total number of vertices is `(D^H -1)/(D-1)`.

func NewFullTree(height int, degree int) (*FullTree, error)

func (t *FullTree) Degree() int

func (t *FullTree) Height() int

func (t *FullTree) Root() *Vertex

func (t *FullTree) Size() int

type Tree ¶

type Tree interface {
	Root() *Vertex
	Size() int
}

type Vertex ¶

type Vertex struct {
	// BFS order of the node in the tree. starting from 0.
	Order int

	// Level of the node in the tree. Root has level 0.
	Level int

	Children []*Vertex
	Parent   *Vertex

	// The next node in BFS order.
	Next *Vertex
}

Vertex is a general vertex in a tree. Each vertex records information of its positional information in a tree. For simplicity, a leaf has empty Children[], instead a non-empty Children[] where each item in Children[] being nil.

func (v *Vertex) IsInternal() bool

func (v *Vertex) IsLeaf() bool

func (v *Vertex) IsRoot() bool