Skip to content

Tutorial2.ja

houzkin edited this page Nov 11, 2026 · 6 revisions

ツリー構造の編集・走査

ツリー構造を表すインターフェイスとして、ITreeNodeとIMutableTreeNodeを定義しています。
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();
}

参照: InternalDesign #IMutableTreeNodeのメンバーの戻り値

ツリー構造の編集

次のコードで、GeneralTreeNodeにて定義されている追加・削除メソッドを使用します。 既に親ノードが設定されているノードを子ノードとして追加する場合、親子関係も変更されます。

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
    */

追加によって兄弟ノードの重複あるいは循環が発生する場合は、追加処理は実行されません。

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
	*/

IMutableTreeNodeに対する拡張メソッドによって、ノードの分解や条件を満たすノードの削除、Tryメソッドなどを利用できます。
各編集メソッドの戻り値は、追加メソッドの場合は現在のノード(親となるノード)、削除メソッドの場合は削除されたノードとなります。
Tryメソッドで、正常に処理が実行された場合も同様の振る舞いです。
これにより、削除されたノードや追加に失敗したノードにアクセスしやすくなります。

次のコードで、ノードの分解と条件に一致した子孫の削除を行います。

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
*/

ノードの走査

対象ノードからの走査方法を提供しています。

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
*/

ノードのパラメータ

上記ツリーを流用します。 GetNodeIndex、GetNodePathで、ツリー内の位置を示します。

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
*/

各ノードの位置関係などを示すパラメータを示します。

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 : ルートノードを0とした、ルートノードからの距離
Height : リーフノードを0とした、最深のリーフノードからの距離
Width : 同世代にあたるノードの数
BranchIndex : 親ノードから割り当てられているインデックス

ノードの取得

再度、上記ツリーを流用します。 拡張メソッドによって、親ノード以外のノードも取得できます。

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.

ノードの探索

対象ノードから子孫方向に向けて、各ノード毎に、条件に一致するノードを探索します。 DescendArrivalsメソッドは、条件を満たした末端のノード、DescendTracesは対象ノードから条件を満たした末端までの経路となったノードも返します。

引数に配列を使う

引数に配列を取る場合は、階層を降りる度に次の要素と一致するかどうかを条件とします。 各階層にて各対応要素と一致し続けた、最後の要素を全て列挙します。

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

引数に条件式を使う

配列に条件式を取った場合は、対象ノードを含め、条件が一致した末端の要素を列挙します。

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