如何实现非二叉树

Question

我在实现非二叉树时遇到问题,其中根节点可以具有任意数量的子节点.基本上,我想了解一下如何使用它的一些想法,因为我确实编写了一些代码,但我仍然坚持下一步该做什么.顺便说一句,我根本不能使用任何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;
    }

}

}

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

然后您将需要实现不同的功能（获取器、移除器等）。但这是你的工作。