c# - vb 木 構造




C#のツリーデータ構造 (14)

私はC#でツリーやグラフのデータ構造を探していましたが、提供されていないと思います。 C#2.0を使用したデータ構造の広範囲にわたる検討で 、なぜその理由が説明されます。 この機能を提供するために一般的に使用される便利なライブラリはありますか? おそらく、この記事で提示された問題を解決するための戦略パターンを通して。

私自身のArrayListを実装するのと同じように、自分のツリーを少しばかげて実装する気がします。

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


@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;
        }
    }

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();
    }
}

ここに木があります

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

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

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
}

さらに別のツリー構造:

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-structure


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

誰かのparents詳細を含むpersonクラスがあるとします。あなたの "domain class"の一部としてツリー構造を使用するか、personオブジェクトへのリンクを含む別のツリークラスを使用しますか? このコードがpersonクラスに含まれる場合、Personのすべてのgrandchildrenを取得するような単純な操作について考えるか、Personクラスのユーザーは別のTreeクラスについて知っている必要がありますか?

もう一つの例は、コンパイラの解析木です...

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

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


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


他の人に役立つNodeクラスを作成します。 クラスには次のようなプロパティがあります:

  • 子供
  • 祖先
  • 子孫
  • 兄弟
  • ノードのレベル
  • ルート
  • 等。

また、IdとParentIdを持つアイテムのフラットなリストをツリーに変換する可能性もあります。 ノードは子ノードと親ノードの両方への参照を保持しているため、ノードの反復処理が非常に高速になります。


少ないメモリを使用するルートツリーデータ構造の実装が必要な場合は、次のように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
}

私の最善のアドバイスは、標準的なツリーデータ構造がないということです。なぜなら、それを実装できる方法がたくさんあり、すべての基盤を1つの解決策でカバーすることは不可能であるからです。 より具体的な解決策であれば、任意の問題に適用される可能性は低くなります。 私はLinkedListで迷惑をかけることもあります。

実装する必要がある基本的な構造はノードの集合であり、ここでは始めるためのいくつかのオプションがあります。 Nodeクラスがソリューション全体の基本クラスであるとしましょう。

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

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

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


私はそれを認めたくないのですが、リンクされたリストを使って自分のツリークラスを作成しました。 無関係の注記では、私は 'アクスル'と呼んでいる物に取り付けられたときに商品の輸送を容易にするこの丸いものを発見しました。


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

Scott Mitchell著「C#2.0を使用した広範なデータ構造の検討」


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に名前を変更するだけです。





data-structures