it-swarm-id.com

Struktur data pohon dalam C #

Saya sedang mencari struktur data pohon atau grafik di C # tapi saya kira tidak ada yang disediakan. Pemeriksaan Ekstensif Struktur Data Menggunakan C # 2. menjelaskan sedikit tentang alasannya. Apakah ada perpustakaan yang nyaman yang biasanya digunakan untuk menyediakan fungsionalitas ini? Mungkin melalui pola strategi untuk menyelesaikan masalah yang disajikan dalam artikel.

Saya merasa agak konyol menerapkan pohon saya sendiri, sama seperti saya akan mengimplementasikan ArrayList saya sendiri.

Saya hanya ingin pohon generik yang tidak seimbang. Pikirkan pohon direktori. C5 terlihat bagus, tetapi struktur pohon mereka tampaknya diimplementasikan sebagai pohon merah-hitam seimbang yang lebih cocok untuk dicari daripada mewakili hierarki node.

233
stimms

Saran terbaik saya adalah bahwa tidak ada struktur data pohon standar karena ada banyak cara Anda dapat mengimplementasikannya sehingga tidak mungkin untuk menutup semua pangkalan dengan satu solusi. Semakin spesifik suatu solusi, semakin kecil kemungkinannya untuk diterapkan pada masalah apa pun. Saya bahkan merasa terganggu dengan LinkedList - bagaimana jika saya ingin daftar tertaut melingkar?

Struktur dasar yang harus Anda implementasikan adalah kumpulan node, dan berikut ini beberapa opsi untuk Anda mulai. Mari kita asumsikan bahwa kelas Node adalah kelas dasar dari seluruh solusi.

Jika Anda hanya perlu menavigasi turun pohon, maka kelas Node membutuhkan Daftar anak-anak.

Jika Anda perlu menavigasi ke atas pohon, maka kelas Node membutuhkan tautan ke simpul induknya.

Bangun metode AddChild yang menangani semua hal kecil dari dua poin ini dan logika bisnis lainnya yang harus diterapkan (batasan anak, pemilahan anak-anak, dll.)

145
David Boike

Saya benci mengakuinya tetapi saya akhirnya menulis kelas pohon saya sendiri menggunakan daftar tertaut. Pada catatan yang tidak berhubungan, saya baru saja menemukan benda bundar ini yang, ketika dikaitkan dengan benda yang saya sebut 'gandar' memungkinkan pengangkutan barang yang lebih mudah.

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

Implementasi rekursif sederhana ... <40 baris kode ... Anda hanya perlu menyimpan referensi ke akar pohon di luar kelas, atau membungkusnya di kelas lain, mungkin mengubah nama menjadi TreeNode ??

116
Aaron Gage

Ini milik saya, yang sangat mirip dengan Aaron Gage , hanya sedikit lebih konvensional, menurut saya. Untuk tujuan saya, saya belum mengalami masalah kinerja dengan List<T>. Akan cukup mudah untuk beralih ke LinkedList jika diperlukan.


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

Namun struktur pohon lain:

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
}

Penggunaan sampel:

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
Lihat pohon sepenuhnya dengan:

  • iterator
  • mencari
  • Java/C #

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

44
Grzegorz Dev

Biasanya sangat baik C5 Generic Collection Library memiliki beberapa struktur data berbasis pohon yang berbeda, termasuk set, tas dan kamus. Kode sumber tersedia jika Anda ingin mempelajari detail implementasi mereka. (Saya telah menggunakan koleksi C5 dalam kode produksi dengan hasil yang baik, meskipun saya belum menggunakan struktur pohon secara khusus.)

22
McKenzieG1

Lihat http://quickgraph.codeplex.com/

QuickGraph menyediakan datastructures dan algoritma grafik yang diarahkan/tidak terarah untuk .Net 2.0 dan yang lebih tinggi. QuickGraph hadir dengan algoritme seperti pencarian kedalaman pertama, pencarian pertama nafas, pencarian A *, jalur terpendek, jalur terpendek k, aliran maksimum, pohon rentang minimum, leluhur paling tidak umum, dll. QuickGraph mendukung MSAGL, GLEE, dan Graphviz untuk render grafik, serialisasi ke GraphML, dll ...

10
nietras

Jika Anda ingin menulis sendiri, Anda dapat mulai dengan dokumen enam bagian ini yang merinci penggunaan efektif struktur data C # 2.0 dan cara menganalisis implementasi struktur data Anda dalam C #. Setiap artikel memiliki contoh dan installer dengan sampel yang dapat Anda ikuti.

"Pemeriksaan Ekstensif Struktur Data Menggunakan C # 2.0" oleh Scott Mitchell

8
user7116

Saya punya sedikit ekstensi untuk solusi.

Dengan menggunakan deklarasi generik rekursif dan subclass turunan, Anda dapat lebih berkonsentrasi pada target Anda yang sebenarnya.

Perhatikan, ini berbeda dari implementasi non generik, Anda tidak perlu menggunakan 'node' di 'NodeWorker'.

Inilah contoh saya:

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

Coba contoh sederhana ini.

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

Saya membuat kelas Node yang bisa bermanfaat bagi orang lain. Kelas memiliki properti seperti:

  • Anak-anak
  • Leluhur
  • Keturunan
  • Saudara kandung
  • Tingkat simpul
  • Induk
  • Root
  • Dll.

Ada juga kemungkinan untuk mengonversi daftar datar item dengan Id dan ParentId ke pohon. Node memegang referensi untuk anak-anak dan orang tua, sehingga membuat node pengulangan cukup cepat.

2
Alex Siepman

Karena tidak disebutkan, saya ingin Anda memperhatikan .net code-base yang sekarang dirilis: khusus kode untuk SortedSet yang mengimplementasikan Red-Black-Tree:

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

Namun ini adalah struktur pohon yang seimbang. Jadi jawaban saya lebih merujuk pada apa yang saya yakini sebagai satu-satunya struktur pohon asli di perpustakaan inti .net.

2
Meirion Hughes

Ini Pohon

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

Anda bahkan dapat menggunakan inisialisasi:

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

Ini milik saya:

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

Keluaran:

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

Saya telah menyelesaikan kode yang dibagikan @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;
        }
    }
2
Ashkan Sirous

Sebagian besar pohon dibentuk oleh data yang Anda proses.

Katakanlah Anda memiliki kelas person yang mencakup detail seseorang parents seseorang, apakah Anda lebih suka memiliki struktur pohon sebagai bagian dari "kelas domain" Anda, atau menggunakan kelas pohon terpisah yang berisi tautan ke objek orang Anda? Pikirkan tentang operasi sederhana seperti mendapatkan semua grandchildren dari person, haruskah kode ini berada di kelas person, atau haruskah pengguna kelas person harus tahu tentang kelas pohon terpisah?

Contoh lain adalah pohon parse di kompiler ...

Apa yang ditunjukkan kedua contoh ini adalah bahwa konsep pohon adalah bagian dari domain data dan menggunakan pohon tujuan umum yang terpisah setidaknya menggandakan jumlah objek yang dibuat serta membuat API lebih sulit diprogram lagi.

Apa yang kita inginkan adalah cara untuk menggunakan kembali operasi pohon standar, tanpa harus mengimplementasikannya kembali untuk semua pohon, sementara pada saat yang sama, tidak harus menggunakan kelas pohon standar. Boost telah mencoba menyelesaikan masalah jenis ini untuk C++, tetapi saya belum melihat efek apa pun untuk .NET diadaptasi.

1
Ian Ringrose

Saya telah menambahkan solusi lengkap dan contoh menggunakan kelas NTree di atas, juga menambahkan metode "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;
        }
    }

menggunakan

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

Jika Anda akan menampilkan pohon ini pada GUI, Anda dapat menggunakan TreeView dan TreeNode . (Saya kira secara teknis Anda dapat membuat TreeNode tanpa meletakkannya di GUI, tetapi ia memiliki lebih banyak overhead daripada implementasi TreeNode sederhana buatan sendiri.)

0
Denise Skidmore