Class DepthFirstTraversal<TEdge, TNode>

Base class for all DFS strategies, i.e. all traversing strategies 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>
FullyIterativeDepthFirstTraversal<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 abstract class DepthFirstTraversal<TEdge, TNode> : TreeTraversal<TEdge, TNode>, IVisitStrategy<TNode, TreeTraversalVisit<TEdge, TNode>> where TEdge : IRecImmDictIndexedTreeEdge<TEdge, TNode> where TNode : IRecImmDictIndexedTreeNode<TEdge, TNode>
Type Parameters
Name Description
TEdge
TNode
Remarks

TRAVERSAL VS VISIT
The word "traversal" in TreeTraversal<TEdge, TNode> and its derivations, is here used with narrower scope than the word "visit" in IVisitStrategy<TNode, TVisitContext>.
- "Traversal" is used here as common class between DFS and BFS, as a visit strategy that starts from the root of the tree and proceeds downwards, following edges and terminating when leafs are reached.
- "Visit" is used in a more general sense, as any algorithm which "touches" 0 or more nodes of the tree, walking the tree in any possible way (up, down, sideways, ...).

Examples

Given the following tree structure:

0
|- 0 -> 1
|       |- 1 -> 2
|       |- 2 -> 3
|       |       |- 3 -> 4
|       |- 4 -> 5
|- 5 -> 6
|- 6 -> 7
        |- 7 -> 8
                |- 8 -> 9
                |- 9 -> 10

A DFS visit strategy "parent first" would visit nodes and edges in either of the following ways, depending on how children are sorted (lower-id edge first, lower-id edge last, median-id edge first, ...):
- { (null, 0), (0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9), (9, 10) }
- { (null, 0), (6, 7), (7, 8), (9, 10), (8, 9), (5, 6), (0, 1), (4, 5), (2, 3), (3, 4), (1, 2) }
- { (null, 0), (5, 6), (6, 7), (7, 8), (9, 10), (8, 9), (0, 1), (2, 3), (3, 4), (4, 5), (1, 2) }
- ...

A DFS visit strategy "children first" would visit nodes and edges in either of the following ways, depending on how children are sorted:
- { (1, 2), (3, 4), (2, 3), (4, 5), (0, 1), (5, 6), (8, 9), (9, 10), (7, 8), (6, 7), (null, 0) }
- { (9, 10), (8, 9), (7, 8), (6, 7), (5, 6), (4, 5), (3, 4), (2, 3), (1, 2), (0, 1), (null, 0) }
- ...

Implements

Extension Methods