How to implement a Non-Binary tree

Question

I am having trouble implementing a non-binary tree, where the root node can have an arbitrary amount of child nodes. Basically, I would like some ideas on how where to go with this, since I do have some code written, yet I'm stuck at this point on what to do next. BTW I cannot use any of the Collections classes at all. I can only use 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

So far Jerska's solution is the best but it is needlessly complicated.

Since I assume this is a homework exercise let me give you the direction you should head in. The data structure you want is:

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

Let's now redraw your diagram -- vertical lines are "first child", horizontal lines are "next sibling"

Root
 |
 p1 ----- p2 ----- p4 ----- p6  
 |        |         |       |
 c1       p3       c4       p7
          |                 |
          c2 - c3           c5

Make sense?

Now, can you write code that produces this tree using this data structure? Start from the rightmost leaves and work your way towards the root:

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 ...

Notice that an arbitrary tree is just a binary tree "rotated 45 degrees", where the root never has a "right" child. Binary trees and arbitrary trees are the same thing; you just assign different meanings to the two children.