بنية بيانات الشجرة في C#

Question

كنت أبحث عن بنية بيانات شجرة أو رسم بياني في C# ولكن أعتقد أنه لم يتم توفيرها. فحص موسع لهياكل البيانات باستخدام C# 2.0 يشرح قليلا عن السبب.هل هناك مكتبة مناسبة تُستخدم عادةً لتوفير هذه الوظيفة؟ربما من خلال نمط استراتيجي لحل القضايا المطروحة في المقال.

أشعر بالسخافة بعض الشيء في تنفيذ شجرتي الخاصة، تمامًا كما أفعل مع تطبيق ArrayList الخاص بي.

أريد فقط شجرة عامة يمكن أن تكون غير متوازنة.فكر في شجرة الدليل.تبدو C5 أنيقة، ولكن يبدو أن هياكلها الشجرية قد تم تنفيذها كأشجار متوازنة ذات لون أحمر وأسود أكثر ملاءمة للبحث من تمثيل التسلسل الهرمي للعقد.

Answer 1

أفضل نصيحتي هي عدم وجود بنية بيانات شجرة قياسية نظرًا لوجود العديد من الطرق التي يمكنك من خلالها تنفيذها بحيث يكون من المستحيل تغطية جميع القواعد بحل واحد.كلما كان الحل أكثر تحديدًا، قل احتمال تطبيقه على أي مشكلة معينة.حتى أنني أشعر بالانزعاج من LinkedList - ماذا لو كنت أريد قائمة مرتبطة دائرية؟

سيكون الهيكل الأساسي الذي ستحتاج إلى تنفيذه عبارة عن مجموعة من العقد، وإليك بعض الخيارات للبدء.لنفترض أن عقدة الفئة هي الفئة الأساسية للحل بأكمله.

إذا كنت بحاجة إلى التنقل أسفل الشجرة فقط، فستحتاج فئة العقدة إلى قائمة الأطفال.

إذا كنت بحاجة إلى التنقل لأعلى الشجرة، فإن فئة العقدة تحتاج إلى رابط للعقدة الأصلية الخاصة بها.

أنشئ طريقة AddChild التي تهتم بكل تفاصيل هاتين النقطتين وأي منطق عمل آخر يجب تنفيذه (حدود الأطفال، وفرز الأطفال، وما إلى ذلك)

Answer 2

أكره أن أعترف بذلك ولكن انتهى بي الأمر إلى كتابة فصل الشجرة الخاص بي باستخدام قائمة مرتبطة.في ملاحظة غير ذات صلة، اكتشفت للتو هذا الشيء المستدير الذي، عند ربطه بشيء أسميه "المحور"، يسمح بنقل البضائع بشكل أسهل.

Answer 3

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

Answer 4

وهنا الألغام، والتي تشبه إلى حد كبير آرون غيج, ، أكثر تقليدية قليلاً، في رأيي.لأغراضي، لم أواجه أي مشاكل في الأداء مع 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()));
        }
    }
}

Answer 5

هيكل شجرة آخر:

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

علاوة
شاهد الشجرة الكاملة مع:

• مكرر
• يبحث
• جافا/سي #

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

Answer 6

الممتاز بشكل عام مكتبة المجموعة العامة C5 يحتوي على العديد من هياكل البيانات المختلفة المستندة إلى الأشجار، بما في ذلك المجموعات والحقائب والقواميس.كود المصدر متاح إذا كنت ترغب في دراسة تفاصيل التنفيذ.(لقد استخدمت مجموعات C5 في كود الإنتاج وحققت نتائج جيدة، على الرغم من أنني لم أستخدم أيًا من الهياكل الشجرية على وجه التحديد.)

Answer 7

يرى http://quickgraph.codeplex.com/

يوفر QuickGraph هياكل بيانات وخوارزميات رسم بياني عامة موجهة/غير موجهة لـ .Net 2.0 والإصدارات الأحدث.يأتي QuickGraph مزودًا بخوارزميات مثل البحث العميق أولاً، والبحث الأول للتنفس، وبحث A*، وأقصر مسار، ومسار k-أقصر، والحد الأقصى للتدفق، والحد الأدنى من الشجرة الممتدة، والأسلاف الأقل شيوعًا، وما إلى ذلك...يدعم QuickGraph MSAGL وGLEE وGraphviz لعرض الرسوم البيانية والتسلسل إلى GraphML وما إلى ذلك...

Answer 8

إذا كنت ترغب في كتابة مستند خاص بك، فيمكنك البدء بهذه الوثيقة المكونة من ستة أجزاء والتي توضح بالتفصيل الاستخدام الفعال لهياكل بيانات C# 2.0 وكيفية البدء في تحليل تنفيذ هياكل البيانات في C#.تحتوي كل مقالة على أمثلة ومثبت يحتوي على نماذج يمكنك متابعتها.

"فحص موسع لهياكل البيانات باستخدام C# 2.0" بواسطة سكوت ميتشل

Answer 9

لدي القليل من التمديد للحلول.

باستخدام إعلان عام متكرر وفئة فرعية مشتقة، يمكنك التركيز بشكل أفضل على هدفك الفعلي.

لاحظ أن الأمر يختلف عن التنفيذ غير العام، فأنت لا تحتاج إلى إرسال "عقدة" في "NodeWorker".

هذا هو المثال الخاص بي:

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

Answer 10

جرب هذه العينة البسيطة.

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
}

Answer 11

أقوم بإنشاء فئة العقدة يمكن أن يكون ذلك مفيدًا لأشخاص آخرين.الطبقة لها خصائص مثل:

• أطفال
• أسلاف
• أحفاد
• إخوة
• مستوى العقدة
• الأبوين
• جذر
• إلخ.

هناك أيضًا إمكانية تحويل قائمة مسطحة من العناصر ذات المعرف ومعرف الوالدين إلى شجرة.تحتوي العقد على إشارة إلى كل من العقد الأبناء والأصل، مما يجعل العقد التكرارية سريعة جدًا.

Answer 12

نظرًا لأنه لم يتم ذكر ذلك، أود أن ألفت انتباهك إلى قاعدة التعليمات البرمجية .net التي تم إصدارها الآن:على وجه التحديد رمز ل SortedSet التي تنفذ شجرة حمراء وسوداء:

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

ومع ذلك، فهذا هيكل شجرة متوازن.لذا فإن إجابتي هي إشارة إلى ما أعتقد أنه البنية الشجرية الأصلية الوحيدة في مكتبة .net الأساسية.

Answer 13

لقد أكملت الكود الذي شاركه @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;
        }
    }

Answer 14

هنا شجرة

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

Answer 15

وهنا بلدي:

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

Answer 16

تتكون معظم الأشجار من البيانات التي تقوم بمعالجتها.

قل أن لديك person فئة تتضمن تفاصيل عن شخص ما parents, ، هل تفضل أن يكون لديك بنية الشجرة كجزء من "فئة المجال" ، أو استخدام فئة شجرة منفصلة تحتوي على روابط لكائنات شخصك؟فكر في عملية بسيطة مثل الحصول على كل grandchildren من أ person, ، هل يجب أن يكون هذا الرمز في personفئة، أو ينبغي للمستخدم person يجب أن تعرف الفصل عن فئة شجرة منفصلة؟

مثال آخر هو شجرة التحليل في المترجم ...

ما يظهره كلا المثالين هو أن مفهوم الشجرة جزء من اِختِصاص من البيانات واستخدام شجرة منفصلة للأغراض العامة على الأقل يضاعف عدد الكائنات التي تم إنشاؤها بالإضافة إلى جعل برمجة واجهة برمجة التطبيقات (API) أكثر صعوبة مرة أخرى.

ما نريده هو طريقة لإعادة استخدام عمليات الشجرة القياسية، دون الحاجة إلى إعادة تنفيذها لجميع الأشجار، وفي الوقت نفسه، عدم الحاجة إلى استخدام فئة شجرة قياسية.لقد حاول Boost حل هذا النوع من المشاكل لـ C++، لكنني لم أر أي تأثير على .NET ليتم تكييفه.

Answer 17

لقد أضفت الحل الكامل والمثال باستخدام فئة 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);

Answer 18

إذا كنت ستعرض هذه الشجرة على واجهة المستخدم الرسومية، فيمكنك استخدامها عرض الشجرة و TreeNode.(أفترض من الناحية الفنية أنه يمكنك إنشاء TreeNode دون وضعه على واجهة المستخدم الرسومية، ولكن لديه حمل أكبر من تطبيق TreeNode البسيط محليًا.)

Answer 19

هذا هو تطبيقي لـ 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();
    }
}

Answer 20

في حال كنت بحاجة إلى تنفيذ بنية بيانات شجرة ذات جذر يستخدم ذاكرة أقل، يمكنك كتابة فئة العقدة الخاصة بك على النحو التالي (تنفيذ 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
}