Cách triển khai cây không nhị phân

Question

Tôi đang gặp sự cố khi triển khai cây không phải nhị phân, trong đó nút gốc có thể có số lượng nút con tùy ý. Về cơ bản, tôi muốn một số ý tưởng về cách đi với điều này, kể từ khi tôi có một số mã bằng văn bản, nhưng tôi đang bị mắc kẹt vào thời điểm này về những gì để làm tiếp theo. BTW Tôi không thể sử dụng bất kỳ lớp sưu tập nào cả. Tôi chỉ có thể sử dụng Hệ thống.

using System; 

namespace alternate_solution 
{ 
//   [root] 
//  //  \ \ 
// text text text text 

class Node//not of type TreeNode (since Node is different from TreeNode) 
{ 
    public string data; 
    public Node child; 

    public Node(string data) 
    { 
     this.data = data; 
     this.child = null; 
    } 

} 

}

Answer 1

Cho đến nay giải pháp của Jerska là tốt nhất nhưng không cần thiết phức tạp. .

Kể từ khi tôi giả định này là một bài tập bài tập về nhà cho tôi cung cấp cho bạn hướng bạn nên đầu trong Cấu trúc dữ liệu bạn muốn là:

class TreeNode 
{ 
    public string Data { get; private set; } 
    public TreeNode FirstChild { get; private set; } 
    public TreeNode NextSibling { get; private set; } 
    public TreeNode (string data, TreeNode firstChild, TreeNode nextSibling) 
    { 
    this.Data = data; 
    this.FirstChild = firstChild; 
    this.NextSibling = nextSibling; 
    } 
} 

Bây giờ hãy vẽ lại sơ đồ của bạn - đường dọc là "đứa con đầu lòng ", đường ngang là" anh chị em tiếp theo "

Root 
| 
p1 ----- p2 ----- p4 ----- p6 
|  |   |  | 
c1  p3  c4  p7 
      |     | 
      c2 - c3   c5 

Có ý nghĩa?

Bây giờ, bạn có thể viết mã tạo ra cây này bằng cấu trúc dữ liệu này không? Bắt đầu từ những chiếc lá ngoài cùng bên phải và làm việc theo cách của bạn về phía gốc:

TreeNode c5 = new TreeNode("c5", null, null); 
TreeNode p7 = new TreeNode("p7", c5, null); 
TreeNode p6 = new TreeNode("p6", p6, null); 
... you do the rest ... 

Chú ý rằng một cây tùy ý chỉ là một cây nhị phân "xoay 45 độ", nơi gốc không bao giờ có một "quyền" đứa trẻ.Cây nhị phân và cây tùy ý là cùng một điều; bạn chỉ cần gán ý nghĩa khác nhau cho hai đứa trẻ.

Answer 2

class Node 
{ 
    public string data; 
    public Node parent; 
    public IEnumerable<Node> children; 

    public Node(string data, Node parent, IEnumerable<Node> children) 
    { 
     this.data = data; 
     this.parent = parent; 
     this.children = children; 
    } 

} 

Answer 3

Nếu bạn không thể sử dụng bất kỳ bộ sưu tập, lưu trữ liên kết trong tất cả các phần tử con đến cha mẹ. Bạn có thể mô hình đồ thị của bạn bằng cách sử dụng tiếp theo cấu trúc dữ liệu:

class Node 
{ 
    public string Data { get; set; } 
    public Node Parent { get; set; } 

    public Node(string data, Node parent) 
    { 
     Data = data; 
     Parent = parent; 
    } 
} 

Bây giờ bạn có thể có nhiều Childs cho mỗi nút, như bạn thích:

var root = new Node("root", null); 

var parent = new Node("parent", root); 
var anotherParent = new Node("yetAnotherParent", root); 

var child = new Node("Child", parent); 
var anotherchild = new Node("anotherchild", parent); 

Answer 4

Một số ý tưởng ngẫu nhiên:

• Một nút sẽ cần một số loại danh sách các nút con, cân nhắc sử dụng triển khai đồng thời, có khả năng nhất là IEnumerable<NodeType> sẽ khớp với hóa đơn
• Bạn có thể hoặc không muốn có một backpointer cho phụ huynh - conisder một cho nhanh chóng (đọc: không quá khập khiễng) traversal
• tôi khuyên bạn nên tạo một NodeType<T> để làm cho cuộc sống dễ dàng hơn khi tiêu thụ cây

Answer 5

Vì bạn có thể' Tôi sử dụng bộ sưu tập, tại sao bạn không tạo danh sách của riêng mình?

class Child { 
    Node node; 
    Child next = null; 

    public Child (Node node) { 
     this.node = node; 
    } 

    public void addChild (Node node) { 
     if (this.next == null) 
      this.next = new Child (node); 
     else 
      this.next.addChild (node); 
    } 
} 

class Node { 
    public string data; 
    public Child children = null; 

    public Node (string data) { 
     this.data = data; 
    } 

    public void addChild (Node node) { 
     if (this.children == null) 
      this.children = new Child (node); 
     else 
      this.children.addChild (node); 
    } 
} 

Và sử dụng nó như thế này:

Node root = new Node ("Hey"); 
root.addChild (new Node ("you")); 
root.addChild (new Node ("me")); 

Bây giờ bạn sẽ có:

  Node ("Hey") 
     /   \ 
    Node ("you")  Node ("me") 

Sau đó, bạn sẽ cần phải thực hiện các chức năng khác nhau (thu khí, chất tẩy, vv). Nhưng đó là công việc của bạn.

Answer 6

Bạn có thể đại diện cho cây đa chiều bằng cách sử dụng loại nút chỉ có con trỏ tiếp theo và con trỏ con.

Nút của con trỏ next được sử dụng để trỏ đến đứa con anh chị em tiếp theo, được triển khai dưới dạng danh sách được liên kết đơn giản.

Nút của con trỏ child được sử dụng để trỏ đến con đầu tiên của nút.

Dưới đây là một số mã mẫu minh họa cách đặt cùng nhau. Nó không chứa bất kỳ xử lý lỗi nào và nó không phải là một giải pháp hoàn chỉnh, nhưng bạn có thể biên dịch nó và - nếu cần - hãy chạy nó dưới trình gỡ rối để hiểu đầy đủ cách nó hoạt động.

Tôi cũng đã thêm một ví dụ liệt kê để cho biết cách bạn có thể lặp qua các nút cây. Bạn có thể sẽ muốn chơi xung quanh với điều này để tạo ra kết quả theo các đơn đặt hàng khác nhau. NẾU sử dụng một số đếm là quá phức tạp cho những gì bạn cần, bạn sẽ cần phải viết phương pháp recusive đơn giản của riêng bạn để truy cập tất cả các nút.

Lưu ý rằng loại nút là chung trong ví dụ này và tôi chỉ sử dụng nó để giữ dữ liệu chuỗi. Bạn chỉ có thể thay thế T bằng loại bạn muốn nếu bạn không muốn loại chung.

using System; 
using System.Collections; 
using System.Collections.Generic; 

namespace Demo 
{ 
    sealed class Node<T> 
    { 
     public T Data; // Payload. 

     public Node<T> Next; // This will point to the next sibling node (if any), forming a linked-list. 
     public Node<T> Child; // This will point to the first child node (if any). 
    } 

    sealed class Tree<T>: IEnumerable<T> 
    { 
     public Node<T> Root; 

     public Node<T> AddChild(Node<T> parent, T data) 
     { 
      parent.Child = new Node<T> 
      { 
       Data = data, 
       Next = parent.Child // Prepare to place the new node at the head of the linked-list of children. 
      }; 

      return parent.Child; 
     } 

     public IEnumerator<T> GetEnumerator() 
     { 
      return enumerate(Root).GetEnumerator(); 
     } 

     private IEnumerable<T> enumerate(Node<T> root) 
     { 
      for (var node = root; node != null; node = node.Next) 
      { 
       yield return node.Data; 

       foreach (var data in enumerate(node.Child)) 
        yield return data; 
      } 
     } 

     IEnumerator IEnumerable.GetEnumerator() 
     { 
      return GetEnumerator(); 
     } 
    } 

    class Program 
    { 
     void run() 
     { 
      var tree = new Tree<string>(); 

      tree.Root = new Node<string>{Data = "Root"}; 

      var l1n3 = tree.AddChild(tree.Root, "L1 N3"); 
      var l1n2 = tree.AddChild(tree.Root, "L1 N2"); 
      var l1n1 = tree.AddChild(tree.Root, "L1 N1"); 

      tree.AddChild(l1n1, "L2 N1 C3"); 
      tree.AddChild(l1n1, "L2 N1 C2"); 
      var l2n1 = tree.AddChild(l1n1, "L2 N1 C1"); 

      tree.AddChild(l1n2, "L2 N2 C3"); 
      tree.AddChild(l1n2, "L2 N2 C2"); 
      tree.AddChild(l1n2, "L2 N2 C1"); 

      tree.AddChild(l1n3, "L2 N3 C3"); 
      tree.AddChild(l1n3, "L2 N3 C2"); 
      tree.AddChild(l1n3, "L2 N3 C1"); 

      tree.AddChild(l2n1, "L3 N1 C3"); 
      tree.AddChild(l2n1, "L3 N1 C2"); 
      tree.AddChild(l2n1, "L3 N1 C1"); 

      tree.Print(); 
     } 

     static void Main() 
     { 
      new Program().run(); 
     } 
    } 

    static class DemoUtil 
    { 
     public static void Print(this object self) 
     { 
      Console.WriteLine(self); 
     } 

     public static void Print(this string self) 
     { 
      Console.WriteLine(self); 
     } 

     public static void Print<T>(this IEnumerable<T> self) 
     { 
      foreach (var item in self) 
       Console.WriteLine(item); 
     } 
    } 
} 

(Tôi biết điều này cũng tương tự như câu trả lời của Eric trên, và nếu tôi muốn đọc câu trả lời trước khi viết này tôi có lẽ sẽ không làm phiền - nhưng tôi muốn đã viết này và tôi đã không chỉ muốn vứt bỏ nó đi.)