C# のツリーデータ構造

https://stackoverflow.com/questions/66893

09-06-2019
|

質問

C# でツリーまたはグラフのデータ構造を探していましたが、提供されていないようです。 C# 2.0 を使用したデータ構造の徹底的な調査その理由について少し説明します。この機能を提供するために一般的に使用される便利なライブラリはありますか?おそらく、記事で示されている問題を解決するための戦略パターンを通じて。

独自の ArrayList を実装するのと同じように、独自のツリーを実装するのは少し愚かな気がします。

アンバランスな汎用ツリーが欲しいだけです。ディレクトリツリーを考えてみましょう。C5 は気の利いたように見えますが、そのツリー構造は、ノードの階層を表すよりも検索に適したバランスの取れた赤と黒のツリーとして実装されているようです。

解決

私の最善のアドバイスは、標準のツリーデータ構造は存在しないということです。これを実装する方法は非常に多く、1 つのソリューションですべてのベースをカバーするのは不可能だからです。解決策が具体的であればあるほど、特定の問題に適用できる可能性は低くなります。LinkedList にもイライラします。循環リンクリストが必要な場合はどうすればよいでしょうか?

実装する必要がある基本構造はノードのコレクションであり、開始するためのオプションがいくつかあります。Node クラスがソリューション全体の基本クラスであると仮定します。

ツリーの下に移動するだけの場合は、Node クラスに子のリストが必要です。

ツリーを上に移動する必要がある場合、Node クラスにはその親ノードへのリンクが必要です。

これら 2 つのポイントのすべての詳細と、実装する必要があるその他のビジネスロジック (子の制限、子の並べ替えなど) を処理する AddChild メソッドを構築します。

他のヒント

認めたくないのですが、リンクリストを使用して独自のツリークラスを作成することになりました。関係ない話ですが、私が「車軸」と呼ぶものに取り付けると、物品の輸送が容易になるこの丸いものを発見しました。

delegate void TreeVisitor<T>(T nodeData);

class NTree<T>
{
    private T data;
    private LinkedList<NTree<T>> children;

    public NTree(T data)
    {
         this.data = data;
        children = new LinkedList<NTree<T>>();
    }

    public void AddChild(T data)
    {
        children.AddFirst(new NTree<T>(data));
    }

    public NTree<T> GetChild(int i)
    {
        foreach (NTree<T> n in children)
            if (--i == 0)
                return n;
        return null;
    }

    public void Traverse(NTree<T> node, TreeVisitor<T> visitor)
    {
        visitor(node.data);
        foreach (NTree<T> kid in node.children)
            Traverse(kid, visitor);
    }
}

単純な再帰実装...コードが 40 行未満...クラスの外側のツリーのルートへの参照を保持するか、別のクラスで包み、TreeNodeに名前を変更するだけですか？

これが私のものです。これは非常によく似ていますアーロン・ゲイジの, 私の意見では、もう少し従来的です。私の目的では、パフォーマンスの問題に遭遇したことはありません List<T>. 。必要に応じて LinkedList に切り替えるのは簡単です。

namespace Overby.Collections
{
    public class TreeNode<T>
    {
        private readonly T _value;
        private readonly List<TreeNode<T>> _children = new List<TreeNode<T>>();

        public TreeNode(T value)
        {
            _value = value;
        }

        public TreeNode<T> this[int i]
        {
            get { return _children[i]; }
        }

        public TreeNode<T> Parent { get; private set; }

        public T Value { get { return _value; } }

        public ReadOnlyCollection<TreeNode<T>> Children
        {
            get { return _children.AsReadOnly(); }
        }

        public TreeNode<T> AddChild(T value)
        {
            var node = new TreeNode<T>(value) {Parent = this};
            _children.Add(node);
            return node;
        }

        public TreeNode<T>[] AddChildren(params T[] values)
        {
            return values.Select(AddChild).ToArray();
        }

        public bool RemoveChild(TreeNode<T> node)
        {
            return _children.Remove(node);
        }

        public void Traverse(Action<T> action)
        {
            action(Value);
            foreach (var child in _children)
                child.Traverse(action);
        }

        public IEnumerable<T> Flatten()
        {
            return new[] {Value}.Concat(_children.SelectMany(x => x.Flatten()));
        }
    }
}

さらに別のツリー構造:

public class TreeNode<T> : IEnumerable<TreeNode<T>>
{

    public T Data { get; set; }
    public TreeNode<T> Parent { get; set; }
    public ICollection<TreeNode<T>> Children { get; set; }

    public TreeNode(T data)
    {
        this.Data = data;
        this.Children = new LinkedList<TreeNode<T>>();
    }

    public TreeNode<T> AddChild(T child)
    {
        TreeNode<T> childNode = new TreeNode<T>(child) { Parent = this };
        this.Children.Add(childNode);
        return childNode;
    }

    ... // for iterator details see below link
}

使用例:

TreeNode<string> root = new TreeNode<string>("root");
{
    TreeNode<string> node0 = root.AddChild("node0");
    TreeNode<string> node1 = root.AddChild("node1");
    TreeNode<string> node2 = root.AddChild("node2");
    {
        TreeNode<string> node20 = node2.AddChild(null);
        TreeNode<string> node21 = node2.AddChild("node21");
        {
            TreeNode<string> node210 = node21.AddChild("node210");
            TreeNode<string> node211 = node21.AddChild("node211");
        }
    }
    TreeNode<string> node3 = root.AddChild("node3");
    {
        TreeNode<string> node30 = node3.AddChild("node30");
    }
}

ボーナス
以下の完全なツリーを参照してください。

イテレータ
検索中
Java/C#

https://github.com/gt4dev/yet-another-tree-structor

一般的に優れているのは、 C5 汎用コレクションライブラリには、セット、バッグ、辞書など、いくつかの異なるツリーベースのデータ構造があります。実装の詳細を調べたい場合は、ソースコードを利用できます。(特にツリー構造を使用したわけではありませんが、実稼働コードで C5 コレクションを使用して良好な結果が得られました。)

見る http://quickgraph.codeplex.com/

QuickGraph は、.Net 2.0 以降向けの汎用の有向/無向グラフデータ構造とアルゴリズムを提供します。QuickGraph には、深さ優先検索、ブレス優先検索、A* 検索、最短パス、k 最短パス、最大フロー、最小スパニングツリー、最小共通祖先などのアルゴリズムが付属しています。QuickGraph は、グラフのレンダリング、GraphML へのシリアル化などのために MSAGL、GLEE、Graphviz をサポートしています。

独自のデータ構造を作成したい場合は、C# 2.0 データ構造の効果的な使用方法と、C# でのデータ構造の実装の分析方法を詳しく説明した 6 部構成のドキュメントから始めることができます。各記事には例と、サンプルを含むインストーラーが含まれており、それに従って進めることができます。

「C# 2.0によるデータ構造の徹底検証」スコット・ミッチェル著

解決策を少し拡張しました。

再帰的なジェネリック宣言と派生サブクラスを使用すると、実際のターゲットに集中することができます。

非ジェネリック実装とは異なり、「NodeWorker」で「node」をキャストする必要がないことに注意してください。

私の例は次のとおりです。

public class GenericTree<T> where T : GenericTree<T> // recursive constraint  
{
  // no specific data declaration  

  protected List<T> children;

  public GenericTree()
  {
    this.children = new List<T>();
  }

  public virtual void AddChild(T newChild)
  {
    this.children.Add(newChild);
  }

  public void Traverse(Action<int, T> visitor)
  {
    this.traverse(0, visitor);
  }

  protected virtual void traverse(int depth, Action<int, T> visitor)
  {
    visitor(depth, (T)this);
    foreach (T child in this.children)
      child.traverse(depth + 1, visitor);
  }
}

public class GenericTreeNext : GenericTree<GenericTreeNext> // concrete derivation
{
  public string Name {get; set;} // user-data example

  public GenericTreeNext(string name)
  {
    this.Name = name;
  }
}

static void Main(string[] args)  
{  
  GenericTreeNext tree = new GenericTreeNext("Main-Harry");  
  tree.AddChild(new GenericTreeNext("Main-Sub-Willy"));  
  GenericTreeNext inter = new GenericTreeNext("Main-Inter-Willy");  
  inter.AddChild(new GenericTreeNext("Inter-Sub-Tom"));  
  inter.AddChild(new GenericTreeNext("Inter-Sub-Magda"));  
  tree.AddChild(inter);  
  tree.AddChild(new GenericTreeNext("Main-Sub-Chantal"));  
  tree.Traverse(NodeWorker);  
}  

static void NodeWorker(int depth, GenericTreeNext node)  
{                                // a little one-line string-concatenation (n-times)
  Console.WriteLine("{0}{1}: {2}", String.Join("   ", new string[depth + 1]), depth, node.Name);  
}

この簡単なサンプルを試してみてください。

public class TreeNode<TValue>
{
    #region Properties
    public TValue Value { get; set; }
    public List<TreeNode<TValue>> Children { get; private set; }
    public bool HasChild { get { return Children.Any(); } }
    #endregion
    #region Constructor
    public TreeNode()
    {
        this.Children = new List<TreeNode<TValue>>();
    }
    public TreeNode(TValue value)
        : this()
    {
        this.Value = value;
    }
    #endregion
    #region Methods
    public void AddChild(TreeNode<TValue> treeNode)
    {
        Children.Add(treeNode);
    }
    public void AddChild(TValue value)
    {
        var treeNode = new TreeNode<TValue>(value);
        AddChild(treeNode);
    }
    #endregion
}

私はノードクラスそれは他の人にとっても役立つかもしれません。クラスには次のようなプロパティがあります。

子供たち
祖先
子孫
兄弟
ノードのレベル
親
根
等。

ID と ParentId を持つアイテムのフラットリストをツリーに変換することもできます。ノードは子と親の両方への参照を保持するため、ノードの反復が非常に高速になります。

言及されていないため、現在リリースされている .net コードベースに注目していただきたいと思います。具体的には SortedSet Red-Black-Tree を実装するもの:

https://github.com/Microsoft/referencesource/blob/master/System/compmod/system/collections/generic/sortedset.cs

ただし、これはバランスの取れたツリー構造です。したがって、私の答えは、.net core ライブラリの唯一のネイティブツリー構造であると私が信じているものへの参照です。

@Berezh が共有したコードが完成しました。

  public class TreeNode<T> : IEnumerable<TreeNode<T>>
    {

        public T Data { get; set; }
        public TreeNode<T> Parent { get; set; }
        public ICollection<TreeNode<T>> Children { get; set; }

        public TreeNode(T data)
        {
            this.Data = data;
            this.Children = new LinkedList<TreeNode<T>>();
        }

        public TreeNode<T> AddChild(T child)
        {
            TreeNode<T> childNode = new TreeNode<T>(child) { Parent = this };
            this.Children.Add(childNode);
            return childNode;
        }

        public IEnumerator<TreeNode<T>> GetEnumerator()
        {
            throw new NotImplementedException();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return (IEnumerator)GetEnumerator();
        }
    }
    public class TreeNodeEnum<T> : IEnumerator<TreeNode<T>>
    {

        int position = -1;
        public List<TreeNode<T>> Nodes { get; set; }

        public TreeNode<T> Current
        {
            get
            {
                try
                {
                    return Nodes[position];
                }
                catch (IndexOutOfRangeException)
                {
                    throw new InvalidOperationException();
                }
            }
        }


        object IEnumerator.Current
        {
            get
            {
                return Current;
            }
        }


        public TreeNodeEnum(List<TreeNode<T>> nodes)
        {
            Nodes = nodes;
        }

        public void Dispose()
        {
        }

        public bool MoveNext()
        {
            position++;
            return (position < Nodes.Count);
        }

        public void Reset()
        {
            position = -1;
        }
    }

ここに木があります

public class Tree<T> : List<Tree<T>>
{
    public  T Data { get; private set; }

    public Tree(T data)
    {
        this.Data = data;
    }

    public Tree<T> Add(T data)
    {
        var node = new Tree<T>(data);
        this.Add(node);
        return node;
    }
}

イニシャライザを使用することもできます。

    var tree = new Tree<string>("root")
    {
        new Tree<string>("sample")
        {
            "console1"
        }
    };

これが私自身のものです:

class Program
{
    static void Main(string[] args)
    {
        var tree = new Tree<string>()
            .Begin("Fastfood")
                .Begin("Pizza")
                    .Add("Margherita")
                    .Add("Marinara")
                .End()
                .Begin("Burger")
                    .Add("Cheese burger")
                    .Add("Chili burger")
                    .Add("Rice burger")
                .End()
            .End();

        tree.Nodes.ForEach(p => PrintNode(p, 0));
        Console.ReadKey();
    }

    static void PrintNode<T>(TreeNode<T> node, int level)
    {
        Console.WriteLine("{0}{1}", new string(' ', level * 3), node.Value);
        level++;
        node.Children.ForEach(p => PrintNode(p, level));
    }
}

public class Tree<T>
{
    private Stack<TreeNode<T>> m_Stack = new Stack<TreeNode<T>>();

    public List<TreeNode<T>> Nodes { get; } = new List<TreeNode<T>>();

    public Tree<T> Begin(T val)
    {
        if (m_Stack.Count == 0)
        {
            var node = new TreeNode<T>(val, null);
            Nodes.Add(node);
            m_Stack.Push(node);
        }
        else
        {
            var node = m_Stack.Peek().Add(val);
            m_Stack.Push(node);
        }

        return this;
    }

    public Tree<T> Add(T val)
    {
        m_Stack.Peek().Add(val);
        return this;
    }

    public Tree<T> End()
    {
        m_Stack.Pop();
        return this;
    }
}

public class TreeNode<T>
{
    public T Value { get; }
    public TreeNode<T> Parent { get; }
    public List<TreeNode<T>> Children { get; }

    public TreeNode(T val, TreeNode<T> parent)
    {
        Value = val;
        Parent = parent;
        Children = new List<TreeNode<T>>();
    }

    public TreeNode<T> Add(T val)
    {
        var node = new TreeNode<T>(val, this);
        Children.Add(node);
        return node;
    }
}

出力：

Fastfood
   Pizza
      Margherita
      Marinara
   Burger
      Cheese burger
      Chili burger
      Rice burger

ほとんどのツリーは、処理中のデータによって形成されます。

持っていると言ってください person 誰かの詳細を含むクラス parents, 、「ドメインクラス」の一部としてツリー構造を持っていますか、それとも個人のオブジェクトへのリンクを含む別のツリークラスを使用しますか？すべてを取得するような簡単な操作について考えてください grandchildren の person, 、このコードは personクラスを使用するか、ユーザーが person クラスは別のツリークラスについて知っておく必要がありますか？

別の例は、コンパイラの解析ツリーです。

これらの例の両方が示しているのは、木の概念がシステムの一部であるということです。 ドメイン データの量を減らし、別の汎用ツリーを使用すると、作成されるオブジェクトの数が少なくとも 2 倍になるだけでなく、API の再プログラミングが困難になります。

私たちが望んでいるのは、すべてのツリーに対して標準ツリー操作を再実装する必要がなく、同時に標準ツリークラスを使用する必要もなく、標準ツリー操作を再利用する方法です。Boost は C++ のこの種の問題を解決しようとしましたが、.NET への適応にはまだ効果が見られません。

上記のNTreeクラスを使用した完全なソリューションと例を追加し、「AddChild」メソッドも追加しました...

    public class NTree<T>
    {
        public T data;
        public LinkedList<NTree<T>> children;

        public NTree(T data)
        {
            this.data = data;
            children = new LinkedList<NTree<T>>();
        }

        public void AddChild(T data)
        {
            var node = new NTree<T>(data) { Parent = this };
            children.AddFirst(node);
        }

        public NTree<T> Parent { get; private set; }

        public NTree<T> GetChild(int i)
        {
            foreach (NTree<T> n in children)
                if (--i == 0)
                    return n;
            return null;
        }

        public void Traverse(NTree<T> node, TreeVisitor<T> visitor, string t, ref NTree<T> r)
        {
            visitor(node.data, node, t, ref r);
            foreach (NTree<T> kid in node.children)
                Traverse(kid, visitor, t, ref r);
        }
    }
    public static void DelegateMethod(KeyValuePair<string, string> data, NTree<KeyValuePair<string, string>> node, string t, ref NTree<KeyValuePair<string, string>> r)
    {
        string a = string.Empty;
        if (node.data.Key == t)
        {
            r = node;
            return;
        }
    }

を使用して

 NTree<KeyValuePair<string, string>> ret = null;
 tree.Traverse(tree, DelegateMethod, node["categoryId"].InnerText, ref ret);

このツリーを GUI で表示する場合は、次のようにします。ツリー表示そしてツリーノード. 。(技術的には、GUI に配置せずに TreeNode を作成できると思いますが、単純な自家製 TreeNode 実装よりもオーバーヘッドが高くなります。)

これが私のBSTの実装です

class BST
{
    public class Node
    {
        public Node Left { get; set; }
        public object Data { get; set; }
        public Node Right { get; set; }

        public Node()
        {
            Data = null;
        }

        public Node(int Data)
        {
            this.Data = (object)Data;
        }

        public void Insert(int Data)
        {
            if (this.Data == null)
            {
                this.Data = (object)Data;
                return;
            }
            if (Data > (int)this.Data)
            {
                if (this.Right == null)
                {
                    this.Right = new Node(Data);
                }
                else
                {
                    this.Right.Insert(Data);
                }
            }
            if (Data <= (int)this.Data)
            {
                if (this.Left == null)
                {
                    this.Left = new Node(Data);
                }
                else
                {
                    this.Left.Insert(Data);
                }
            }
        }

        public void TraverseInOrder()
        {
            if(this.Left != null)
                this.Left.TraverseInOrder();
            Console.Write("{0} ", this.Data);
            if (this.Right != null)
                this.Right.TraverseInOrder();
        }
    }

    public Node Root { get; set; }
    public BST()
    {
        Root = new Node();
    }
}

メモリ使用量の少ないルートツリーデータ構造の実装が必要な場合は、次のように Node クラスを作成できます (C++ 実装)。

class Node {
       Node* parent;
       int item; // depending on your needs

       Node* firstChild; //pointer to left most child of node
       Node* nextSibling; //pointer to the sibling to the right
}

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow

C# のツリー データ構造

C# のツリーデータ構造