如何实现非二叉树

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的回答以上，而如果我写这一个我可能不会打扰你之前读到的答案 - 但我已经写了这一点，我没有想要扔掉它。）