it-swarm-vi.tech

Cấu trúc dữ liệu cây trong C #

Tôi đang tìm kiếm một cấu trúc dữ liệu cây hoặc đồ thị trong C # nhưng tôi đoán không có cái nào được cung cấp. Kiểm tra mở rộng về cấu trúc dữ liệu bằng C # 2. giải thích một chút về lý do. Có một thư viện thuận tiện thường được sử dụng để cung cấp chức năng này? Có lẽ thông qua một mô hình chiến lược để giải quyết các vấn đề được trình bày trong bài viết.

Tôi cảm thấy hơi ngớ ngẩn khi thực hiện cây của riêng mình, giống như tôi sẽ thực hiện ArrayList của riêng mình.

Tôi chỉ muốn một cây chung có thể mất cân bằng. Hãy nghĩ về một cây thư mục. C5 trông tiện lợi, nhưng cấu trúc cây của chúng dường như được triển khai dưới dạng cây đỏ đen cân bằng phù hợp với tìm kiếm hơn là đại diện cho một hệ thống phân cấp của các nút.

228
stimms

Lời khuyên tốt nhất của tôi là không có cấu trúc dữ liệu cây tiêu chuẩn bởi vì có rất nhiều cách bạn có thể thực hiện nó đến mức không thể bao quát tất cả các cơ sở bằng một giải pháp. Một giải pháp càng cụ thể, nó càng ít có khả năng áp dụng cho bất kỳ vấn đề nào. Tôi thậm chí còn thấy khó chịu với LinkedList - nếu tôi muốn một danh sách liên kết tròn thì sao?

Cấu trúc cơ bản bạn sẽ cần triển khai sẽ là một tập hợp các nút và đây là một số tùy chọn để bạn bắt đầu. Giả sử rằng lớp Node là lớp cơ sở của toàn bộ giải pháp.

Nếu bạn chỉ cần điều hướng xuống cây, thì một lớp Node cần có Danh sách trẻ em.

Nếu bạn cần điều hướng lên cây, thì lớp Node cần một liên kết đến nút cha của nó.

Xây dựng một phương thức AddChild chăm sóc tất cả các chi tiết vụn vặt của hai điểm này và bất kỳ logic kinh doanh nào khác phải được thực hiện (giới hạn con, sắp xếp con cái, v.v.)

141
David Boike

Tôi ghét phải thừa nhận nó nhưng cuối cùng tôi đã viết lớp cây của riêng mình bằng cách sử dụng một danh sách được liên kết. Trên một ghi chú không liên quan, tôi mới phát hiện ra điều tròn trịa này, khi được gắn vào một thứ tôi đang gọi là 'trục' cho phép vận chuyển hàng hóa dễ dàng hơn.

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

Thực hiện đệ quy đơn giản ... <40 dòng mã ... Bạn chỉ cần giữ một tham chiếu đến gốc của cây bên ngoài lớp hoặc bọc nó trong một lớp khác, có thể đổi tên thành TreeNode ??

112
Aaron Gage

Đây là của tôi, rất giống với Aaron Gage's , theo tôi thì thông thường hơn một chút. Đối với mục đích của tôi, tôi đã không gặp phải bất kỳ vấn đề về hiệu suất nào với List<T>. Sẽ đủ dễ dàng để chuyển sang LinkedList nếu cần.


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

Một cấu trúc cây khác:

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
}

Sử dụng mẫu:

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

PHẦN THƯỞNG
[.__.] Xem cây đầy đủ với:

  • vòng lặp
  • đang tìm kiếm
  • Java/C #

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

40
Grzegorz Dev

Nhìn chung xuất sắc Thư viện bộ sưu tập chung chung C5 có một số cấu trúc dữ liệu dựa trên cây khác nhau, bao gồm bộ, túi và từ điển. Mã nguồn có sẵn nếu bạn muốn nghiên cứu chi tiết thực hiện của họ. (Tôi đã sử dụng các bộ sưu tập C5 trong mã sản xuất với kết quả tốt, mặc dù tôi chưa sử dụng bất kỳ cấu trúc cây nào cụ thể.)

22
McKenzieG1

Xem http://quickgraph.codeplex.com/

QuickGraph cung cấp các thuật toán và cơ sở dữ liệu đồ thị có hướng/không định hướng chung cho .Net 2.0 trở lên. QuickGraph đi kèm với các thuật toán như tìm kiếm độ sâu đầu tiên, tìm kiếm hơi thở đầu tiên, tìm kiếm A *, đường dẫn ngắn nhất, đường dẫn ngắn nhất, lưu lượng tối đa, cây bao trùm tối thiểu, tổ tiên ít phổ biến nhất, v.v ... QuickGraph hỗ trợ MSAGL, GLEE và Graphviz kết xuất đồ thị, tuần tự hóa thành GraphML, v.v ...

10
nietras

Nếu bạn muốn tự viết, bạn có thể bắt đầu với tài liệu sáu phần này chi tiết cách sử dụng hiệu quả cấu trúc dữ liệu C # 2.0 và cách phân tích việc triển khai cấu trúc dữ liệu của bạn trong C #. Mỗi bài viết có các ví dụ và trình cài đặt với các mẫu bạn có thể làm theo cùng.

Một cuộc kiểm tra mở rộng về cấu trúc dữ liệu bằng cách sử dụng C # 2. của Scott Mitchell

7
user7116

Tôi có một chút mở rộng cho các giải pháp.

Sử dụng một khai báo chung đệ quy và một lớp con phái sinh, bạn có thể tập trung tốt hơn vào mục tiêu thực tế của mình.

Lưu ý, nó khác với cách triển khai không chung chung, bạn không cần truyền 'nút' trong 'NodeWorker'.

Đây là ví dụ của tôi:

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

Hãy thử mẫu đơn giản này.

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

Tôi tạo một lớp Node có thể hữu ích cho người khác. Lớp này có các thuộc tính như:

  • Bọn trẻ
  • Tổ tiên
  • Hậu duệ
  • Anh chị em ruột
  • Cấp độ của nút
  • Cha mẹ
  • Root
  • V.v.

Ngoài ra còn có khả năng chuyển đổi một danh sách phẳng các mặt hàng có Id và ParentId thành cây. Các nút giữ một tham chiếu đến cả con cái và cha mẹ, do đó làm cho các nút lặp khá nhanh.

2
Alex Siepman

Vì nó không được đề cập nên tôi muốn bạn chú ý đến cơ sở mã .net hiện được phát hành: cụ thể là mã cho SortedSet thực hiện Red-Black-Tree:

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

Đây là, tuy nhiên, một cấu trúc cây cân bằng. Vì vậy, câu trả lời của tôi là tham chiếu nhiều hơn đến những gì tôi tin là cấu trúc cây bản địa duy nhất trong thư viện lõi .net.

2
Meirion Hughes

Đây là một cái cây

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

Bạn thậm chí có thể sử dụng khởi tạo:

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

Đây là của riêng tôi:

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

Đầu ra:

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

Tôi đã hoàn thành mã mà @Berezh đã chia 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;
        }

        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

Hầu hết các cây được hình thành bởi dữ liệu bạn đang xử lý.

Giả sử bạn có một lớp person bao gồm các chi tiết về ai đó LÊN parents, bạn có muốn cấu trúc cây như một phần của lớp miền miền của bạn hay sử dụng một lớp cây riêng biệt có chứa các liên kết đến các đối tượng cá nhân của bạn không? Hãy suy nghĩ về một hoạt động đơn giản như nhận tất cả grandchildren của một person, mã này có nên thuộc lớp person hay người dùng của lớp person phải biết về một lớp cây riêng biệt?

Một ví dụ khác là cây phân tích cú pháp trong trình biên dịch

Điều mà cả hai ví dụ này cho thấy là khái niệm về cây là một phần của tên miền của dữ liệu và sử dụng cây mục đích chung riêng ít nhất làm tăng gấp đôi số lượng đối tượng được tạo cũng như tạo ra API khó hơn để lập trình lại.

Những gì chúng ta muốn là một cách để sử dụng lại các hoạt động của cây tiêu chuẩn, mà không phải thực hiện lại chúng cho tất cả các cây, đồng thời, không phải sử dụng một lớp cây tiêu chuẩn. Boost đã cố gắng giải quyết loại vấn đề này cho C++, nhưng tôi chưa thấy hiệu ứng nào cho .NET được điều chỉnh.

1
Ian Ringrose

Tôi đã thêm giải pháp hoàn chỉnh và ví dụ sử dụng lớp NTree ở trên, cũng đã thêm phương thức "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;
        }
    }

sử dụng

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

Nếu bạn định hiển thị cây này trên GUI, bạn có thể sử dụng TreeViewTreeNode . (Tôi cho rằng về mặt kỹ thuật, bạn có thể tạo TreeNode mà không cần đặt nó trên GUI, nhưng nó có nhiều chi phí hơn so với triển khai TreeNode đơn giản tại nhà.)

0
Denise Skidmore