如何實現非二叉樹

Question

我在實現非二叉樹時遇到問題，其中根節點可以有任意數量的子節點。基本上，我想知道如何去做這件事，因爲我確實寫了一些代碼，但我仍然堅持下一步要做的事情。順便說一句，我根本不能使用任何集合類。我只能使用System。

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

到目前爲止Jerska的解決方案是最好的，但它是不必要的複雜。 。

因爲我認爲這是一個課外練習讓我給你，你應該前往的方向你想要的數據結構是：

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

現在讓我們重新繪製的圖表 - 垂直線是「第一個孩子「，水平線是」下一個兄弟「

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

有意義嗎？

現在，您可以編寫使用此數據結構生成此樹的代碼嗎？從最右邊的葉子開始，向根你的工作方式：

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

注意，任意樹只是一個二叉樹「旋轉45度」，根源在哪裏從來沒有一個「正確」的孩子。二叉樹和任意樹都是同樣的東西;你只需給兩個孩子分配不同的含義。

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

如果您不能使用任何集合，存儲鏈接的所有子元素的父。您可以通過使用一個數據結構中的圖模型：

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

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

現在，您可以有許多孩子的每個節點，只要你喜歡：

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

一些隨機的想法：

• 一個節點需要某種子節點的列表，考慮使用併發性實現，最有可能的是IEnumerable<NodeType>將適合賬單
• 你可能會或可能不會想要一個反向指針父 - conisder一個用於快速（閱讀：不是太瘸）穿越
• 我建議你創建一個NodeType<T>消耗樹

Answer 5

時，既然你可以」讓生活更輕鬆不要使用集合，爲什麼不創建自己的列表？

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

而且使用這樣的：

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

現在您有：

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

然後，你將需要實現不同的功能（干將，去除等）。但那是你的工作。

Answer 6

您可以使用僅具有下一個指針和子指針的節點類型來表示多路樹。

該節點的next指針用於指向下一個兄弟孩子，實現爲一個簡單的鏈接列表。

節點的child指針用於指向節點的第一個子節點。

下面是一些演示如何將它們放在一起的示例代碼。它不包含任何錯誤處理，它不是一個完整的解決方案，但是你應該能夠編譯它並且 - 如果需要的話 - 在調試器下運行它，以便完全理解它是如何工作的。

我還添加了一個枚舉示例來展示如何遍歷樹節點。你可能想要玩這個來產生不同順序的結果。如果使用枚舉對於你所需要的來說太複雜，你將需要編寫自己的簡單recusive方法來訪問所有節點。

請注意，在本例中節點類型是通用的，我只用它來保存字符串數據。如果您的不需要想要一個通用類型，您可以用您想要的類型替換T。

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

（我知道這是類似於Eric的回答以上，而如果我寫這一個我可能不會打擾你之前讀到的答案 - 但我已經寫了這一點，我沒有想要扔掉它。）