如何实现非二叉树

我在实现非二叉树时遇到问题，其中根节点可以具有任意数量的子节点。 基本上，我想了解一下如何使用它的一些想法，因为我确实编写了一些代码，但我仍然坚持下一步该做什么。 顺便说一句，我根本不能使用任何集合类。 我只能使用系统。

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

然后，您将需要实现不同的function（getter，removers等）。 但那是你的工作。

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

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

Answer 5

您可以使用仅具有下一个指针和子指针的节点类型来表示多路树。

节点的next指针用于指向下一个兄弟子节点，实现为一个简单的链接列表。

节点的child指针用于指向节点的第一个子节点。

这是一些示例代码，演示如何将它们放在一起。 它不包含任何error handling，并不是一个完整的解决方案，但您应该能够编译它 – 如果需要 – 在调试器下运行它以完全理解它是如何工作的。

我还添加了一个可枚举的示例，以展示如何迭代树节点。 你可能想要玩这个以产生不同顺序的结果。 如果使用可枚举对于您需要的太复杂，您将需要编写自己的简单重用方法来访问所有节点。

请注意，在此示例中，节点类型是通用的，我只使用它来保存字符串数据。 如果你不想要generics类型，你可以用你想要的类型替换T

 using System; using System.Collections; using System.Collections.Generic; namespace Demo { sealed class Node { public T Data; // Payload. public Node Next; // This will point to the next sibling node (if any), forming a linked-list. public Node Child; // This will point to the first child node (if any). } sealed class Tree: IEnumerable { public Node Root; public Node AddChild(Node parent, T data) { parent.Child = new Node { 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 GetEnumerator() { return enumerate(Root).GetEnumerator(); } private IEnumerable enumerate(Node 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(); tree.Root = new Node{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(this IEnumerable self) { foreach (var item in self) Console.WriteLine(item); } } } 

（我知道这与上面的Eric的回答类似，如果我在写这篇文章之前读过这个答案，我可能不会感到困扰 – 但我已经写过了这篇文章而且我不想把它扔掉。 ）

Answer 6

一些随意的想法：

• 一个节点需要某种子节点列表，考虑使用并发防范实现，很可能IEnumerable符合要求
• 你可能想也可能不想要一个父指针的后退指针 – 一个快速的指针（读：不太蹩脚）遍历
• 我建议您创建一个NodeType ，以便在使用树时更轻松