Class FullyRecursiveDepthFirstTraversal<TEdge, TNode>

A lazy, fully-recursive, depth-first IVisitStrategy<TNode, TVisitContext> implementation, i.e. a traversing strategy which goes in depth as far as possible along each path of the tree, only backtracking when a leaf is reached.

Inheritance
System.Object
TreeTraversal<TEdge, TNode>
DepthFirstTraversal<TEdge, TNode>
FullyRecursiveDepthFirstTraversal<TEdge, TNode>
Implements
IVisitStrategy<TNode, TreeTraversalVisit<TEdge, TNode>>
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: MoreStructures.RecImmTrees.Visitor
Assembly: MoreStructures.dll
Syntax
public class FullyRecursiveDepthFirstTraversal<TEdge, TNode> : DepthFirstTraversal<TEdge, TNode>, IVisitStrategy<TNode, TreeTraversalVisit<TEdge, TNode>> where TEdge : IRecImmDictIndexedTreeEdge<TEdge, TNode> where TNode : IRecImmDictIndexedTreeNode<TEdge, TNode>
Type Parameters
Name Description
TEdge
TNode
Remarks

ADVANTAGES AND DISADVANTAGES
Implemented fully recursively, so limited by stack depth and usable with tree of a "reasonable" height.

Methods

| Improve this Doc View Source

Visit(TNode)

Lazily and recursively visits the structure of the providednode, returning the sequence of IRecImmDictIndexedTreeNode<TEdge, TNode> of the structure, in depth-first order.

Declaration
public override IEnumerable<TreeTraversalVisit<TEdge, TNode>> Visit(TNode node)
Parameters
Type Name Description
TNode node

The node on where to start visit the structure.
Returns
Type Description
IEnumerable<TreeTraversalVisit<TEdge, TNode>>

A sequence emitting (node, visit context) couples, in the visit order defined by the visit strategy.
Overrides
MoreStructures.RecImmTrees.Visitor.TreeTraversal<TEdge, TNode>.Visit(TNode)
Remarks

ALGORITHM
- The algorithm visits all nodes in structure in natural recursion/depth-first order, yielding to the output sequence, so that the client code implementing the visitor can lazily process the nodes.

COMPLEXITY
- Excluding visitor, constant time work is done for each of the n nodes of the tree (such as construction of the input record for the visitor).
- Iteration-cost is constant w.r.t. n. ChildrenSorter cost depends on the actual algorithm used.
- So Time Complexity is dominated by ChildrenSorter and visitor.
In conclusion:
- Time Complexity is O(n * Ts), where Ts is the amortized time cost of ChildrenSorter per node. Taking into account the visit of each emitted node, Time Complexity is O(n * (Ts + Tv)), where Tv is the time cost of the visitor per node.
- Space Complexity is O(n). Taking into account the visit of each emitted node, Space Complexity is O(n * Sv), where Sv is the space cost of visitor per node.

Implements

Extension Methods