如何实现非二叉树

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

}

- Karim O.

---

这是为另一个项目做准备的练习。我可以使用节点的链表吗？ - Karim O.

当然，你可以使用自己编写的链表来作为节点。 - lurker

“_我只能使用System_”的限制需要解释。另外，需要哪些操作？需要在任意位置插入、删除吗？ - H H

听起来你可能正在寻找一种B+树…… - Roger Lipscombe

提示：二叉树有两个指向其他树节点的引用，称为左侧和右侧。任意树有两个指向其他树节点的引用，称为FirstChild和NextSibling。 任意树是二叉树；只需为节点分配不同的含义即可。 - Eric Lippert

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度”的结果，其中根节点永远没有“右”子节点。 二叉树和任意树是一样的；你只需要给这两个子节点分配不同的含义。

- Eric Lippert

---

看起来我会考虑这种方法。由于似乎有无数种表示任意树的方式，我认为更直接地看待它是有意义的。感谢您的帮助！只有一个问题，要写出树中的所有节点，我应该将所有节点添加到链表中吗？还是不必要的？ - Karim O.

@KarimOumghar：这是不必要的；你可以轻松地编写这棵树的递归遍历，就像你可以编写二叉树的递归遍历一样。 - Eric Lippert

我一直在寻找类似的解决方案，这真的很好，我一定会使用它。不过我有一个疑虑: 在你的实现中，你是自下而上地添加节点的，我不认为你的方法允许添加新节点，因为TreeNodes有一个私有集合，所以你不能从类外修改现有节点来容纳新的子节点或兄弟节点。你如何建议使用这个实现来添加一个新节点？ - Lou

@LucaCremonesi：我认为你误解了这里的数据结构。从这个角度考虑它：每个节点都有一个其子节点的链表。“向下”的引用指向最老的孩子。“向右”的引用是下一个最老的兄弟，它是链接中的下一个元素。我们可以类似地实现“每个节点都有一个子节点列表<Node>”或“每个节点都有一个子节点数组Node[]”，我的例子只是选择了链接列表来说明n叉树和二叉树只是同一数据结构上的两个不同语义。 - Eric Lippert

@LucaCremonesi：在我的例子中，P2、P4和P6都是P1的子节点。P2是最老的孩子，P4是中间的孩子，而P6是他们最年幼的兄弟姐妹。 - Eric Lippert

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

然后，您需要实现不同的功能（getter、remover等）。但这是您的工作。

- Jerska

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

- Ilya Ivanov

---

但是你如何进行深度优先搜索呢？ - Jerska

@Jerska 你需要它吗？这是明确的要求吗？为什么你没有提到广度优先搜索呢？ - Ilya Ivanov

我不是这篇文章的作者，我在想是否可能。然而，我对广度优先搜索也有同样的疑问。 - Jerska

@Jerska，你根本做不到。你仍然需要存储所有子元素的链接，并且处理这种类型的树非常麻烦。但是，我认为"嘿，我不能使用任何集合工具"这样的要求非常不合理。 - Ilya Ivanov

Answer 4

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

}

- Femaref

Answer 5

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

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

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

以下是演示如何组合这些内容的示例代码。它不包含任何错误处理，并且不打算成为完整的解决方案，但您应该能够编译它并在必要时在调试器下运行它以充分理解其工作原理。

我还添加了一个可枚举的示例，以展示如何迭代树节点。您可能需要尝试不同的操作以按不同顺序生成结果。如果使用可枚举对象过于复杂，则需要编写自己的简单递归方法来访问所有节点。

请注意，此示例中的节点类型是通用的，我仅使用它来保存字符串数据。如果您不想要通用类型，则可以将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上面的答案相似，如果在写这篇文章之前我读了那个答案，我可能就不会费心写这篇了 - 但我已经写好了，不想把它扔掉。

- Matthew Watson

Answer 6

一些随机的想法：

• 节点将需要某种子节点列表，请考虑使用并发安全的实现，最有可能的是IEnumerable<NodeType>。
• 您可能希望有一个指向父级的后指针-考虑一个快速（即不太糟糕）的遍历
• 我建议您创建一个NodeType<T>，以使在使用树时更加方便

- Eugen Rieck