tree

package

v0.0.0-...-c1449ee Latest Latest Go to latest Published: Jul 25, 2024 License: MIT Imports: 5 Imported by: 0

Details

Valid go.mod file
Redistributable license
Tagged version
Stable version
Learn more about best practices

Repository

github.com/patstar123/go-base

Links

Open Source Insights

Documentation ¶

Index ¶

func LinkParent(root *Node)
func MergeChildren(src, dst *Node)
func MergeChildren2(src, dst *Node)
func PostorderTraversal(root *Node, handle func(current *Node) bool) bool
func PreorderFullPath(root *Node) [][]*Node
func PreorderTraversal(root *Node, handle func(current *Node) bool) bool
func SortBrother(root *Node, descOrder bool)
type ListNode
type Node
type NodeValue
type NodeValueCommI
type NodeValueCommS

Constants ¶

This section is empty.

Variables ¶

This section is empty.

Functions ¶

func LinkParent ¶

func LinkParent(root *Node)

LinkParent 关联父节点

func MergeChildren ¶

func MergeChildren(src, dst *Node)

MergeChildren 合并两个节点的子节点

func MergeChildren2 ¶

func MergeChildren2(src, dst *Node)

MergeChildren2 合并两个节点的子节点(排重)(错误版)

func PostorderTraversal ¶

func PostorderTraversal(root *Node, handle func(current *Node) bool) bool

PostorderTraversal 后序遍历函数

func PreorderFullPath ¶

func PreorderFullPath(root *Node) [][]*Node

PreorderFullPath 前序遍历所有根到末端的路径

func PreorderTraversal ¶

func PreorderTraversal(root *Node, handle func(current *Node) bool) bool

PreorderTraversal 前序遍历函数

func SortBrother ¶

func SortBrother(root *Node, descOrder bool)

SortBrother 兄弟节点排序

Types ¶

type ListNode ¶

type ListNode struct {
	Value     NodeValue
	ParentKey interface{}
}

ListNode 带父节点信息的列表节点

type Node ¶

type Node struct {
	Value    NodeValue
	Parent   *Node
	Children []*Node
}

func BuildTreeFromList ¶

func BuildTreeFromList(listNodes []*ListNode) *Node

BuildTreeFromList 从节点列表生成节点树

func DeleteNode ¶

func DeleteNode(tree, node *Node) *Node

DeleteNode 从tree中删除node

其子节点挂载到其父节点上
若不存在父节点,则其他子节点挂载到兄节点

func FindLCA ¶

func FindLCA(root *Node, nodeValue1, nodeValue2 NodeValue) *Node

FindLCA 查找树上两个节点的最小公共祖先(节点)

func GenLCASubTree ¶

func GenLCASubTree(root *Node, nodeValues []NodeValue) *Node

GenLCASubTree 生成树上任意多个节点的最小连通子树

func GenSubUnaryTreeByLCA ¶

func GenSubUnaryTreeByLCA(start, current, lca *Node) *Node

GenSubUnaryTreeByLCA 生成从start节点到lca的单叉树

func GenTwoNodesLCASubTree ¶

func GenTwoNodesLCASubTree(root *Node, nodeValue1, nodeValue2 NodeValue) *Node

GenTwoNodesLCASubTree 生成树上两个节点的最小连通子树

func MergeIntersectSubTrees ¶

func MergeIntersectSubTrees(tree1, tree2 *Node) *Node

MergeIntersectSubTrees 合并两个相交的子树

func PostorderFind ¶

func PostorderFind(root *Node, targetValue NodeValue) *Node

PostorderFind 后序搜索函数: 从root中找到target

func PreorderFind ¶

func PreorderFind(root *Node, targetValue NodeValue) *Node

PreorderFind 前序搜索函数: 从root中找到target

func (*Node) Contains ¶

func (n *Node) Contains(sub *Node) bool

Contains 判断是否包含该子树(递归遍历树)

func (*Node) Contains2 ¶

func (n *Node) Contains2(sub *Node) bool

Contains2 判断是否包含该子树(且兄弟顺序一致)(比较树结点队列)

func (*Node) Contains3 ¶

func (n *Node) Contains3(sub *Node) bool

Contains3 判断是否包含该子树(!!!有bug)

func (*Node) Contains4 ¶

func (n *Node) Contains4(sub *Node) bool

Contains4 判断是否包含该子树

type NodeValue ¶

type NodeValue interface {
	IsEqual(other NodeValue) bool
	GetKey() interface{}
	GetKeyCode() []byte

	/*Compare the result will be 0 if this == other, -1 if this < other, and +1 if this > other*/
	Compare(other NodeValue) int
}

type NodeValueCommI ¶

type NodeValueCommI struct {
	V int
}

func (*NodeValueCommI) Compare ¶

func (cv *NodeValueCommI) Compare(other NodeValue) int

func (*NodeValueCommI) GetKey ¶

func (cv *NodeValueCommI) GetKey() interface{}

func (*NodeValueCommI) GetKeyCode ¶

func (cv *NodeValueCommI) GetKeyCode() []byte

func (*NodeValueCommI) IsEqual ¶

func (cv *NodeValueCommI) IsEqual(other NodeValue) bool

type NodeValueCommS ¶

type NodeValueCommS struct {
	V string
}

func (*NodeValueCommS) Compare ¶

func (cv *NodeValueCommS) Compare(other NodeValue) int

func (*NodeValueCommS) GetKey ¶

func (cv *NodeValueCommS) GetKey() interface{}

func (*NodeValueCommS) GetKeyCode ¶

func (cv *NodeValueCommS) GetKeyCode() []byte

func (*NodeValueCommS) IsEqual ¶

func (cv *NodeValueCommS) IsEqual(other NodeValue) bool

Source Files ¶

View all Source files

Directories ¶

Path	Synopsis
ref

?	: This menu
/	: Search site
f or F	: Jump to
y or Y	: Canonical URL