Create object hierarchy for test

I building a test-driven application that will sort a flat file into a parent-child-hierarchy. And now I want to create a pretty generic test for my own sorting. For that I want to generate some test data, which I then sort.

The object that will be sorted will look something like this:

public interface IHierarchicalUnitWithChildren
{
    string Id { get; }
    string ParentId { get; }
    IList<IHierarchicalUnitWithChildren> Children { get; set; }
}

But I don't want to create the test-object myself. I want this to be generated by code, as such:

        _items = new List<IHierarchicalUnitWithChildren>();
        Random random = new Random();

        for (int i = 1; i < 1000; i++)
        {
            var item = new HierarchicalUnitMock()
            {
                Oid = i.ToString(),
                Children = new List<IHierarchicalUnit>(),
            };

            // We need a couple of roots.
            if (i%100 != 0)
            {
                item.Poid = random.Next(1, 100).ToString();
            }

            _items.Add(item);
        }

I can easily generate a thousand items, but I also need to give them a valid parent. How can I make sure that I'm creating a valid structure, where I have a couple of roots and all children have parents that are valid.

No item should have a parent that is a child (or grandchild) of itself and thus making it an infinite hierachy.

Or am I thinking about it all wrong? Should a test always have static data?

UPDATE:

Is there any way to do this with a smart loop, that always generate the same data? So that the test-case always will be the same?