Вы можете сделать это следующим образом:
var source = XDocument.Parse(xml); // or whatever
var sourceElems = source.Root.Elements("root");
var result = new XDocument(new XElement("result"));
var resultElems = new Dictionary<int, XElement>();
resultElems.Add(0, result.Root);
foreach (var sourceElem in sourceElems)
{
var resultElem = new XElement((string)sourceElem.Attribute("name"));
int parentId = (int)sourceElem.Attribute("parentid");
resultElems[parentId].Add(resultElem);
resultElems.Add((int)sourceElem.Attribute("index"), resultElem);
}
По сути, пройтись по элементам, и для каждого найти родителя в словаре, добавить его в качестве дочернего для этого родителя и, наконец, добавить его всловарь, так что он может быть родителем сам.Это предполагает, что parent всегда объявляется перед всеми его потомками.
С вашими исходными данными он создает следующий результат:
<result>
<level1>
<level2>
<level21 />
<level22 />
</level2>
<level3>
<level31 />
</level3>
</level1>
</result>