C# のデータ構造とアルゴリズムにおけるツリーの役割を紹介します

C# データ構造とアルゴリズムツリー

まず、Windows でコマンド ラインに「tree」と入力します。現在のフォルダーの下にあるすべてのサブフォルダーとファイルがツリー形式で返されます。

上図の通り、木です。

逆さまのリンゴの木のように、各要素はノードと呼ばれます。図に示すように、A はツリーのボスであり、ルートと呼ばれます。ノードに要素がある場合、このノードはその子ノードに対するルートであり、このツリーは A のサブツリーです。たとえば、ツリー D は A のサブツリーです。

子ノードを持たないノードはリーフノードと呼ばれます。

これらのツリーのルートは、ルートからのすべての有向エッジによって接続されています。たとえば、ツリー E はルート A から有向エッジ T _AEによって接続されています。木 J はルート E からの有向辺_TEJによって接続されます。

そして、あるノードから別のノードまでのすべてのノードのシーケンスはパスと呼ばれ、パス上のエッジの数はパスの長さになります。パスの長さは、通過するノードの数から 1 を引いた数であることがわかります。たとえば、パス EQ の場合、長さは 2 です。

深さは、ルート ノードとこのノード間のパスの長さです。たとえば、ノード P と Q の深さは 3 で、ノード K の深さは 2 です。

C# データ構造とアルゴリズムツリー表現

C# のデータ構造とアルゴリズムでは、リンク リストを使用してツリーを表すことができます。図に示すように:

図に示すように、A はリンク リストの最初の要素であり、G は最後の要素です。要素に子ノードがある場合、この要素はこのツリーのリンク リストになります。

矢印が示すように、ABCDEFG はリンク リストであり、ノード DEFG は子ノードを持つツリーであるため、DEFG 要素には別のリンク リストが格納されます。たとえば、E には EIJ リンク リストが格納され、J には JPQ リンク リストが格納されます。したがって、ツリーがどれだけ大きくて深くても、リンク リストで表すことができますが、このリンク リストには他のリンク リストが含まれます。