it-swarm-tr.com

C # ağaç veri yapısı

C # 'da bir ağaç veya grafik veri yapısı arıyordum ama sağlanan bir tane yok sanırım. C # 2.0 Kullanarak Veri Yapılarının Kapsamlı Bir İncelemesi bunun nedenini açıklar. Bu işlevi sağlamak için yaygın olarak kullanılan uygun bir kütüphane var mı? Belki de makalede sunulan sorunları çözmek için bir strateji deseni aracılığıyla.

Kendi ArrayList'imi uygulayacağım gibi kendi ağacımı kendimi aptalca uygularken hissediyorum.

Sadece dengesiz olabilen genel bir ağaç istiyorum. Dizin ağacını düşünün. C5 şık görünüyor, ancak ağaç yapıları, düğümlerin hiyerarşisini temsil etmekten daha aramak için daha uygun, dengeli kırmızı-siyah ağaçlar olarak uygulanıyor gibi görünüyor.

233
stimms

En iyi tavsiyem, standart bir ağaç veri yapısının olmaması olacaktır, çünkü bunu uygulayabileceğiniz pek çok yöntem vardır, tüm üsleri tek bir çözümle ele almanın imkansız olacağı yönünde. Bir çözüm ne kadar belirgin olursa, verilen herhangi bir soruna uygulanabilirliği o kadar düşüktür. LinkedList'ten rahatsız oluyorum bile - ya dairesel bir link listesi istersem?

Uygulamanız gereken temel yapı, bir düğüm koleksiyonu olacaktır ve işte size başlamak için bazı seçenekler. Diyelim ki Node sınıfı tüm çözümün temel sınıfıdır.

Yalnızca ağaçta gezinmeniz gerekiyorsa, bir Node sınıfının bir Çocuk Listesi'ne ihtiyacı vardır.

Ağaçta gezinmeniz gerekiyorsa, o zaman Node sınıfı ana düğümüne bir bağlantı gerektirir.

Bu iki noktanın tüm önemine ve uygulanması gereken diğer iş mantığına dikkat eden bir AddChild yöntemi oluşturun (çocuk limitleri, çocukları sıralama vb.)

145
David Boike

Kabul etmekten nefret ediyorum ama bağlantılı bir liste kullanarak kendi ağaç sınıfımı yazmaya başladım. İlişkisiz bir notta, bu aksamı daha yeni keşfettim, “dingil” olarak adlandırdığım bir şeye bağlandığınızda malların daha kolay taşınmasını sağlar.

194
stimms
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);
    }
}

Basit özyinelemeli uygulama ... <40 kod satırı ... Sadece ağacın köküne bir sınıf dışına başvurmanız veya başka bir sınıfa sarmanız, belki de TreeNode olarak yeniden adlandırmanız yeterlidir ??

116
Aaron Gage

İşte benimki, bence Aaron Gage's 'e çok benziyor, sadece biraz daha geleneksel. Amaçlarım için, List<T> ile herhangi bir performans sorununa girmedim. Gerekirse LinkedList'e geçmek yeterince kolay olurdu.


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

Yine başka bir ağaç yapısı:

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
}

Örnek kullanım:

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

BONUS
Şununla tam teşekküllü ağacı görün:

  • yineleyici
  • aranıyor
  • Java/C #

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

44
Grzegorz Dev

Genel olarak mükemmel C5 Genel Koleksiyon Kütüphanesi , kümeler, çantalar ve sözlükler dahil olmak üzere birkaç farklı ağaç tabanlı veri yapısına sahiptir. Uygulama ayrıntılarını incelemek istiyorsanız kaynak kodu kullanılabilir. (Özellikle ağaç yapıların hiçbirini kullanmadım, ancak üretim kodunda C5 koleksiyonlarını iyi sonuçlarla kullandım.)

22
McKenzieG1

Bakınız http://quickgraph.codeplex.com/

QuickGraph .Net 2.0 ve üstü için genel yönlendirmeli/yönlendirilmemiş grafik veri yapıları ve algoritmalar sağlar. QuickGraph, derinlik ilk arama, ilk arama nefes, A * arama, en kısa yol, en kısa yol, maksimum akış, minimum yayılma ağacı, en az kullanılan atalar vb. Gibi algoritmalarla gelir. QuickGraph, MSAGL, GLEE ve Graphviz'e grafikleri oluşturma, GraphML'e seri hale getirme, vb.

10
nietras

Kendinizinkini yazmak istiyorsanız, C # 2.0 veri yapılarının etkin kullanımını ve C # 'daki veri yapılarının uygulanmasının nasıl analiz edileceğini ayrıntılarıyla anlatan bu altı bölümlük dokümanla başlayabilirsiniz. Her makalede örnekleri ve birlikte izleyebileceğiniz örnekleri olan bir yükleyici vardır.

“C # 2.0 Kullanarak Veri Yapılarının Kapsamlı Bir İncelemesi” Scott Mitchell

8
user7116

Çözümlere biraz uzatma var.

Özyinelemeli genel bir bildirim ve türetme alt sınıfını kullanarak, asıl hedefinize daha iyi konsantre olabilirsiniz.

Dikkat, jenerik olmayan bir uygulamadan farklıdır, 'NodeWorker' içinde 'düğüm' yapmanız gerekmez.

İşte benim örneğim:

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);  
}  
6
Erik Nagel

Bu basit örneği deneyin.

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
}
4
Berezh

Başkaları için yararlı olabilecek bir Node class oluşturuyorum. Sınıfın özellikleri şöyle:

  • Çocuklar
  • Atalar
  • Torunları
  • Kardeşler
  • Düğüm seviyesi
  • Ebeveyn
  • Root
  • Vb.

Ayrıca Id ve ParentId öğelerinin düz bir listesini bir ağaca dönüştürme imkanı da vardır. Düğümler hem çocuklara hem de ebeveynlere referans verir, böylece yinelenen düğümleri oldukça hızlı hale getirir.

2
Alex Siepman

Bahsetmediği için şu anda yayımlanan .net kod-temeline dikkatinizi çekmenizi istiyorum: özellikle bir Red-Black-Tree uygulayan SortedSet kodunu:

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

Bununla birlikte, bu dengeli bir ağaç yapısıdır. Bu yüzden cevabım, .net çekirdek kütüphanesindeki tek doğal ağaç yapısı olduğuna inandığım şeye bir referans.

2
Meirion Hughes

İşte bir ağaç

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

Başlatıcıları bile kullanabilirsiniz:

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

İşte benim:

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

Çıktı:

Fastfood
   Pizza
      Margherita
      Marinara
   Burger
      Cheese burger
      Chili burger
      Rice burger
2
moien

@Berezh'un paylaştığı kodu tamamladım.

  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;
        }
    }
2
Ashkan Sirous

Çoğu ağaç, işlediğiniz verilerden oluşur.

Birinin person'sinin ayrıntılarını içeren bir parents sınıfınız olduğunu söyleyin, ağaç yapısını “etki alanı sınıfınızın” bir parçası olarak mı tercih edersiniz, veya kişi nesnelerinize bağlantılar içeren ayrı bir ağaç sınıfı mı kullanmak istiyorsunuz? ? grandchildren öğesinin tüm person'sini almak gibi basit bir işlem düşünün, bu kod person sınıfındaysa ya da person sınıfının kullanıcısı mı bilmeli? ayrı bir ağaç sınıfı hakkında?

Başka bir örnek, derleyici içindeki bir ayrıştırma ağacı…

Bu örneklerin her ikisinin de gösterdiği şey, bir ağaç kavramının verinin etki alanı 'nin bir parçası olduğu ve ayrı bir genel amaçlı ağaç kullanmanın, yaratılan nesne sayısını en az iki katına çıkarmasıdır. API tekrar programlamak zor.

İstediğimiz şey standart ağaç işlemlerini yeniden kullanmak, onları tüm ağaçlar için tekrar uygulamak zorunda kalmadan, aynı zamanda standart bir ağaç sınıfı kullanmak zorunda kalmamak. Boost, C++ için bu tür bir sorunu çözmeye çalıştı, ancak henüz .NET için uyarlanmış bir etki görmedim.

1
Ian Ringrose

Yukarıdaki NTree sınıfını kullanarak tam çözüm ve örnek ekledim, ayrıca "AddChild" yöntemini de ekledim ...

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

kullanma

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

Bu ağacı GUI'de görüntüleyecekseniz TreeView ve TreeNode kullanabilirsiniz. (Teknik olarak bir GUI'ye koymadan bir TreeNode oluşturabilirsin, ancak basit bir homegrown TreeNode uygulamasından daha fazla ek yükü var.)

0
Denise Skidmore