Skip to content

Tutorial2.en

houzkin edited this page Nov 10, 2026 · 5 revisions

Editing and Traversing Tree Structures

The ITreeNode and IMutableTreeNode interfaces define the structure of a tree.
ITreeNode.cs

public interface ITreeNode<out TNode> where TNode : ITreeNode<TNode> {

    TNode? Parent { get; }

    IEnumerable<TNode> Children { get; }
}

public interface IMutableTreeNode<TNode> : ITreeNode<TNode>
    where TNode : IMutableTreeNode<TNode> {

    TNode AddChild(TNode child);

    TNode InsertChild(int index, TNode child);

    TNode RemoveChild(TNode child);

    IReadOnlyList<TNode> ClearChildren();
}

See also: Internal Design #Return Values of IMutableTreeNode Members

Editing a Tree Structure

The following code uses the methods for adding and removing nodes defined in GeneralTreeNode. When a node that already has a parent is added as a child, its parent-child relationship is updated accordingly.

var nodes = "ABCDEF".ToDictionary(x => x.ToString(), x => new NamedNode() { Name = x.ToString() });

// Add,Insert
nodes["A"].AddChild(nodes["B"]).AddChild(nodes["C"]).InsertChild(0, nodes["D"]).InsertChild(3, nodes["E"]);
nodes["E"].AddChild(nodes["F"]);
foreach(var root in nodes.Values.Where(n => n.IsRoot())) 
    Console.WriteLine(root.ToTreeDiagram(x => x.Name));
/*
A
├ D
├ B
├ C
└ E
  └ F
    */

// Move
nodes["B"].AddChild(nodes["C"]);
foreach(var root in nodes.Values.Where(n => n.IsRoot())) 
    Console.WriteLine(root.ToTreeDiagram(x => x.Name));
/*
A
├ D
├ B
│ └ C
└ E
  └ F
    */

// Remove
nodes["A"].RemoveChild(nodes["E"]);
foreach(var root in nodes.Values.Where(n => n.IsRoot())) 
    Console.WriteLine(root.ToTreeDiagram(x => x.Name));
/*
A
├ D
└ B
  └ C

E
└ F
    */

// Remove all child nodes.
nodes["A"].ClearChildren();
foreach(var root in nodes.Values.Where(n => n.IsRoot())) 
    Console.WriteLine(root.ToTreeDiagram(x => x.Name));
/*
A

B
└ C

D

E
└ F
    */

The addition is rejected if it would create duplicate sibling nodes or a cycle.

var nodes = "ABCDEF".ToDictionary(x => x.ToString(), x => new NamedNode() { Name = x.ToString() });
nodes.Values.AssembleAsNAryTree(2);

Console.WriteLine(nodes["A"].ToTreeDiagram(x => x.Name));
/*
A
├ B
│ ├ D
│ └ E
└ C
  └ F
	*/

nodes["A"].AddChild(nodes["B"]);
Console.WriteLine(nodes["A"].ToTreeDiagram(x => x.Name));
/* Node B cannot be added to Node A because it is a duplicate.
A
├ B
│ ├ D
│ └ E
└ C
  └ F
	*/

nodes["D"].AddChild(nodes["A"]);
Console.WriteLine(nodes["A"].ToTreeDiagram(x => x.Name));
/* Node A cannot be added to Node D because it would create a cycle.
A
├ B
│ ├ D
│ └ E
└ C
  └ F
	*/

Extension methods for IMutableTreeNode provide operations such as disassembling nodes, removing nodes that satisfy a condition, and Try methods.
An add method returns the current node (the parent node), whereas a remove method returns the removed node.
Try methods behave the same way when the operation succeeds.
This makes it easier to access removed nodes and nodes whose addition failed.

The following code disassembles a node and removes descendants that match a condition.

var root1 = new List<NodePath<string>>() {
    new("A","B","C","D"),
    new("A","B","E"),
    new("A","F"),
}.AssembleTreeByPath(x => new NamedNode() { Name = x.Last() });

var nodes = root1.LevelOrder().ToDictionary(x => x.Name, x => x);

foreach (var rt in nodes.Values.Where(x => x.IsRoot()))
    Console.WriteLine(rt.ToTreeDiagram(x => x.Name));
/*
A
├ B
│ ├ C
│ │ └ D
│ └ E
└ F
    */

var disassembleNodes = nodes["B"].Disassemble();
Console.WriteLine("Disassemble nodes: "+  string.Join(",", disassembleNodes));
// Disassemble nodes: E,C,D,B

foreach (var rt in nodes.Values.Where(x => x.IsRoot()))
    Console.WriteLine(rt.ToTreeDiagram(x => x.Name));
/*
A
└ F

B

C

E

D
*/

var root2 = "ABCDEFGHIJK".ToCharArray().AssembleAsNAryTree(3, x => new NamedNode() { Name = x.ToString() });
nodes = root2.LevelOrder().ToDictionary(x => x.Name, x => x);

foreach (var rt in nodes.Values.Where(x => x.IsRoot()))
    Console.WriteLine(rt.ToTreeDiagram(x => x.Name));
/*
A
├ B
│ ├ E
│ ├ F
│ └ G
├ C
│ ├ H
│ ├ I
│ └ J
└ D
  └ K
    */

var removedDescendants = root2.RemoveAllDescendant(x => x.BranchIndex() == 1);
Console.WriteLine("Removed Descendants: " + string.Join(",", removedDescendants));
//Disassemble nodes: C,F

foreach (var rt in nodes.Values.Where(x => x.IsRoot()))
    Console.WriteLine(rt.ToTreeDiagram(x => x.Name));
/*
A
├ B
│ ├ E
│ └ G
└ D
  └ K

C
├ H
├ I
└ J

F
*/

Traversing Nodes

Traversal methods are provided for navigating from the current node.

var root = "ABCDEF".ToCharArray().AssembleAsNAryTree(2, x => new NamedNode() { Name = x.ToString() });
Console.WriteLine(root.ToTreeDiagram(x => x.Name));
/*
A
├ B
│ ├ D
│ └ E
└ C
  └ F
*/

var lvseaq = string.Join(',', root.LevelOrder());
Console.WriteLine(lvseaq);
//A,B,C,D,E,F

var preseaq = string.Join(',', root.PreOrder());
Console.WriteLine(preseaq);
//A,B,D,E,C,F

var postseaq = string.Join(',', root.PostOrder());
Console.WriteLine(postseaq);
//D,E,B,F,C,A

var inseaq = string.Join(',', root.InOrder());
Console.WriteLine(inseaq);
//D,B,E,A,F,C
var root = new List<NodePath<string>>() {
    new ("A","B"),
    new ("A","C","D","E"),
    new ("A","C","D","F","G"),
    new ("A","C","I"),
    new ("A","H","J"),
}.AssembleTreeByPath(x => new NamedNode() { Name = x.Last() });

var nodes = root.PreOrder().ToDictionary(x => x.Name, x => x);

Console.WriteLine(nodes["A"].ToTreeDiagram(x=>x.Name));
/*
A
├ B
├ C
│ ├ D
│ │ ├ E
│ │ └ F
│ │   └ G
│ └ I
└ H
 └ J
*/
var nodeD = nodes["D"];
Console.WriteLine($"Upstream:{string.Join(",",nodeD.Upstream())}");
Console.WriteLine($"Ancestors:{string.Join(",",nodeD.Ancestors())}");
Console.WriteLine($"Leafs:{string.Join(",",nodeD.Leafs())}");
Console.WriteLine($"Siblings:{string.Join(",",nodeD.Siblings())}");
Console.WriteLine($"Generations:{string.Join(",",nodeD.Generations())}");
/*
Upstream:D,C,A
Ancestors:C,A
Leafs:E,G
Siblings:D,I
Generations:D,I,J
*/

Node Parameters

The tree created above is reused. GetNodeIndex and GetNodePath indicate a node's position within the tree.

Console.WriteLine(tree.ToTreeDiagram(x =>$"{x.Name},NodeIndex:{x.GetNodeIndex()}"));
/*
A,NodeIndex:[]
├ B,NodeIndex:[0]
├ C,NodeIndex:[1]
│ ├ D,NodeIndex:[1,0]
│ │ ├ E,NodeIndex:[1,0,0]
│ │ └ F,NodeIndex:[1,0,1]
│ │   └ G,NodeIndex:[1,0,1,0]
│ └ I,NodeIndex:[1,1]
└ H,NodeIndex:[2]
  └ J,NodeIndex:[2,0]
*/

Console.WriteLine(tree.ToTreeDiagram(x =>$"{x.Name},NodePath:{x.GetNodePath(n=>n.Name)}"));
/*
A,NodePath:A
├ B,NodePath:A/B
├ C,NodePath:A/C
│ ├ D,NodePath:A/C/D
│ │ ├ E,NodePath:A/C/D/E
│ │ └ F,NodePath:A/C/D/F
│ │   └ G,NodePath:A/C/D/F/G
│ └ I,NodePath:A/C/I
└ H,NodePath:A/H
  └ J,NodePath:A/H/J
*/

The following parameters describe the position and relationships of each node.

Console.WriteLine(root.ToTreeDiagram(x => $"{x.Name}, Depth:{x.Depth()}, Height:{x.Height()}, Width:{x.Width()}, BranchIndex:{x.BranchIndex()}"));
/*
A, Depth:0, Height:4, Width:1, BranchIndex:-1
├ B, Depth:1, Height:0, Width:3, BranchIndex:0
├ C, Depth:1, Height:3, Width:3, BranchIndex:1
│ ├ D, Depth:2, Height:2, Width:3, BranchIndex:0
│ │ ├ E, Depth:3, Height:0, Width:2, BranchIndex:0
│ │ └ F, Depth:3, Height:1, Width:2, BranchIndex:1
│ │   └ G, Depth:4, Height:0, Width:1, BranchIndex:0
│ └ I, Depth:2, Height:0, Width:3, BranchIndex:1
└ H, Depth:1, Height:1, Width:3, BranchIndex:2
  └ J, Depth:2, Height:0, Width:3, BranchIndex:0
*/

Depth: Distance from the root node, with the root having a depth of 0.
Height: Distance from the deepest leaf node, with leaf nodes having a height of 0.
Width: Number of nodes at the same level.
BranchIndex: Index assigned by the parent node.

Retrieving Nodes

The tree created above is reused. Extension methods can also retrieve nodes other than the parent node.

Console.WriteLine($"Root:{nodeD.Root()}");
//Root:A

Console.WriteLine($"NextSibling:{nodeD.NextSibling()}");
//NextSibling:I

nodeD.PreviousSiblingOrSelf().When(
    o => Console.WriteLine($"PreviousSibling:{o.Name}"),
    x => Console.WriteLine($"{x.Name} is first sibling."));
//D is first sibling.

Searching Nodes

Starting from the current node and proceeding toward its descendants, these methods search for nodes that satisfy a condition. DescendArrivals returns the terminal nodes that satisfy the condition. DescendTraces also returns the nodes along each path from the current node to a matching terminal node.

Using an Array as an Argument

When an array is passed as an argument, each level is checked against the next element in the array. All final nodes that continue to match the corresponding elements at each level are enumerated.

var root = "ABbDEFdHIJKL".ToCharArray().AssembleAsNAryTree(2, x => new NamedNode() { Name = x.ToString() });
Console.WriteLine(root.ToTreeDiagram(x => x.Name));
/*
A
├ B
│ ├ D
│ │ ├ H
│ │ └ I
│ └ E
│   ├ J
│   └ K
└ b
  ├ F
  │ └ L
  └ d
*/

var nodes = root.DescendArrivals(x => x.Name, new string[] { "A", "B", "D" },Equality<string>.ComparerBy(x=>x.ToUpper()));
Console.WriteLine(string.Join(",", nodes.Select(x => x.Name)));
//D,d

var nodeRoute1 = root.DescendTraces(x => x.Name, new string[] { "A", "B", "D" }, Equality<string>.ComparerBy(x => x.ToUpper()));
foreach(var route in nodeRoute1){
    Console.WriteLine(string.Join(",", route.Select(x => x.Name)));
}
//A,B,D
//A,B,d

Using a Predicate as an Argument

When a predicate is passed, the terminal nodes that satisfy the condition are enumerated, including the current node.

nodes.Last().Parent?.AddChild(nodes.First());
Console.WriteLine(root.ToTreeDiagram(x => x.Name));
/*
A
├ B
│ └ E
│   ├ J
│   └ K
└ b
  ├ F
  │ └ L
  ├ d
  └ D
    ├ H
    └ I
    */

var nodes2 = root.DescendArrivals(x => x.BranchIndex() > 0 || x.IsRoot());
Console.WriteLine(string.Join(",", nodes2.Select(x => x.Name)));
//d,I

var nodeRoute2 = root.DescendTraces(x=>x.BranchIndex() > 0 || x.IsRoot());
foreach(var route in nodeRoute2){
    Console.WriteLine(string.Join(",",route.Select(x => x.Name)));
}
//A,b,d
//A,b,D,I

Clone this wiki locally