我在实现非二叉树时遇到问题，其中根节点可以有任意数量的子节点。基本上，我想要一些关于如何使用它的想法，因为我确实编写了一些代码，但我仍然坚持下一步该做什么。顺便说一句，我根本不能使用任何 Collections 类。我只能使用系统。
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;
}
}
}
到目前为止，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 度”的二叉树，其中根永远不会有“正确的”孩子。二叉树和任意树是一回事；你只是给这两个孩子赋予不同的含义。
既然不能使用集合，为什么不创建自己的列表呢？
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")
然后您将需要实现不同的功能（getter、removers 等）。但那是你的工作。
如果您不能使用任何集合，请将所有子元素中的链接存储到父元素。您可以使用下一个数据结构对图形进行建模：
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);
您可以使用仅具有下一个指针和子指针的节点类型来表示多路树。
节点的next指针用于指向下一个兄弟孩子，实现为一个简单的链表。
节点的child指针用于指向节点的第一个子节点。
这是一些示例代码，演示了如何将它们组合在一起。它不包含任何错误处理，也不打算成为一个完整的解决方案，但您应该能够编译它，并在必要时在调试器下运行它以完全理解它是如何工作的。
我还添加了一个可枚举示例来展示如何迭代树节点。您可能希望使用它来产生不同顺序的结果。如果使用 enumerable 对您的需要来说过于复杂，您将需要编写自己的简单递归方法来访问所有节点。
请注意，此示例中的节点类型是通用的，我仅使用它来保存字符串数据。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 的答案相似，如果我在写这个答案之前读过那个答案，我可能不会打扰 - 但我已经写了这个，我不想把它扔掉。 )
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;
}
}
一些随机的想法：
IEnumerable<NodeType>符合要求NodeType<T>在使用树时创建一个让生活更轻松