親/子のフラットリストから階層オブジェクトを構築する
https://stackoverflow.com/questions/319108
-
11-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
階層内のアイテムのリストがあり、このリストをオブジェクトの実際の階層に解析しようとしています。 変更された先行予約ツリートラバーサルを使用して保存/反復しますこのリストを通して、私が持っているのは、すべての子を含むツリーのサブセットです。値。
たとえば、ツリーが与えられた場合：
- アイテムA
- アイテムA.1
- アイテムA.2
- アイテムA.2.2
- アイテムB
- アイテムB.1
- アイテムC
リストを取得します：
- アイテムA、アイテムA.1、アイテムA.2、アイテムA.2.2、アイテムB、アイテムB.1、アイテムC
（これは、変更された先行予約ツリー設定の「左」値の順になります）。
やりたいのは、これをツリーの実際の構造を含むオブジェクトに解析することです。例：
Class TreeObject {
String Name;
Guid ID;
Guid ParentID;
List<TreeObject> Children;
}
フラットリストはTreeObjectsのリストとして返されます。各TreeObjectには、ID、ParentID、Left、Rightのプロパティがあります。私が探しているのは関数です：
List<TreeObject> FlatToHeirarchy(List<TreeObject> list);
フラットリストを受け取り、ネストされたリストを返します。
言い換えれば：
List<TreeObject> flatSet = LoadTreeObjectsFromDatabase();
// flatSet.count == 7; flatSet(0).Children == null
List<TreeObject> nestedSet = FlatToHeirarchy(flatSet);
// nestedSet.count == 3; nestedSet(0).Children.count == 2
これを行う方法に迷っています-両親を追跡し、より大きなジャンプに対処することができます（たとえば、アイテムA.2.2-＆gt;アイテムB）。
編集：私はここで非暴力のソリューションを探しています（例えば、トップレベルの親のみが残るまで、数回ループせず、アイテムを子ノードに移動しません）。一度ループし、必要に応じてアイテムを配置するだけのエレガントなメソッドがあると思います。
これらは常に階層順であることに注意してください（私はMPTTを使用しているため）。特定のアイテムは常に前のアイテムの子または兄弟になるか、少なくとも前のアイテムと親を共有します。ツリーのどこか他の場所に来ることはありません。
解決
これは、私が書いた関数です。私はMPTTを使用してオブジェクトを保存しているので、リストは「左」の値の順になります。つまり、基本的にはリスト内の特定の項目の前に常に親が来ることを意味します。つまり、item.ParentIDによって参照されるアイテムは常に追加されています（最上位ノードまたはルートノードの場合を除く）。
public class TreeObject
{
public int Id { get; set; }
public int ParentId { get; set; }
public string Name { get; set; }
public IList<TreeObject> Children { get; set; } = new List<TreeObject>();
}
public IEnumerable<TreeObject> FlatToHierarchy(List<TreeObject> list)
{
// hashtable lookup that allows us to grab references to containers based on id
var lookup = new Dictionary<int, TreeObject>();
// actual nested collection to return
var nested = new List<TreeObject>();
foreach (TreeObject item in list)
{
if (lookup.ContainsKey(item.ParentId))
{
// add to the parent's child list
lookup[item.ParentId].Children.Add(item);
}
else
{
// no parent added yet (or this is the first time)
nested.Add(item);
}
lookup.Add(item.Id, item);
}
return nested;
}
および簡単なテスト（LinqPadで動作します）：
void Main()
{
var list = new List<TreeObject>() {
new TreeObject() { Id = 1, ParentId = 0, Name = "A" },
new TreeObject() { Id = 2, ParentId = 1, Name = "A.1" },
new TreeObject() { Id = 3, ParentId = 1, Name = "A.2" },
new TreeObject() { Id = 4, ParentId = 3, Name = "A.2.i" },
new TreeObject() { Id = 5, ParentId = 3, Name = "A.2.ii" }
};
FlatToHierarchy(list).Dump();
}
結果：
これは5年後に更新するため、再帰的なLINQバージョンを次に示します。
public IList<TreeObject> FlatToHierarchy(IEnumerable<TreeObject> list, int parentId = 0) {
return (from i in list
where i.ParentId == parentId
select new TreeObject {
Id = i.Id,
ParentId = i.ParentId,
Name = i.Name,
Children = FlatToHierarchy(list, i.Id)
}).ToList();
}
他のヒント
すべてのアイテムの親を既に知っていると仮定します。
必要なことは、リストのすべてのアイテムを1回繰り返し、現在のアイテムをその親の子リストに追加することです。ターゲットのネストされたリストに、親のないアイテムのみを保持します。
擬似コードを次に示します。
foreach Item item in flatlist
if item.Parent != null
Add item to item.Parent.ChildrenList
Remove item from flatlist
end if
end for
親を取得することに関しては、あなたの例で私が見ることができるものから、あなたは名前を解析し、リストを進めるにつれてスタックを構築する必要があるかもしれません。
この問題は一見難しく見えますが、実際はそうではありません。多くの人がこの問題を間違った角度から見ています。すべての子リストに入力するのではなく、フラットリストから子アイテムを削除する必要があります。そうすれば簡単になります。
通常のコンパイルを行う代替バージョン。上記のコードに問題があるかどうかはわかりませんでした。
private List<Page> FlatToHierarchy(List<Page> list) {
// hashtable lookup that allows us to grab references to the parent containers, based on id
Dictionary<int, Page> lookup = new Dictionary<int, Page>();
// actual nested collection to return
List<Page> nested = new List<Page>();
foreach(Page item in list) {
if (lookup.ContainsKey(item.parentId)) {
// add to the parent's child list
lookup[item.parentId].children.Add(item); //add item to parent's childs list
lookup.Add(item.pageId, item); //add reference to page in lookup table
} else {
// no parent added yet (or this is the first time)
nested.Add(item); //add item directly to nested list
lookup.Add(item.pageId, item); //add reference to page in lookup table
}
}
return nested;
}
例を示します。これが役立つことを願っています
class Program
{
static void Main(string[] args)
{
TreeObject a = new TreeObject() { Name = "Item A" };
a.Children.Add( new TreeObject() { Name = "Item A.1" });
a.Children.Add( new TreeObject() { Name = "Item A.2" });
TreeObject b = new TreeObject() { Name = "Item B" };
b.Children.Add(new TreeObject() { Name = "Item B.1" });
b.Children.Add(new TreeObject() { Name = "Item B.2" });
TreeObject c = new TreeObject() { Name = "Item C" };
List<TreeObject> nodes = new List<TreeObject>(new[] { a, b, c });
string list = BuildList(nodes);
Console.WriteLine(list); // Item A,Item A.1,Item A.2,Item B,Item B.1,Item B.2,Item C
List<TreeObject> newlist = new List<TreeObject>();
TreeObject temp = null;
foreach (string s in list.Split(','))
{
if (temp == null || !s.Contains(temp.Name) || temp.Name.Length != s.Length)
{
temp = new TreeObject() { Name = s };
newlist.Add(temp);
}
else
{
temp.Children.Add(new TreeObject() { Name = s });
}
}
Console.WriteLine(BuildList(newlist)); // Item A,Item A.1,Item A.2,Item B,Item B.1,Item B.2,Item C
}
static string BuildList(List<TreeObject> nodes)
{
StringBuilder output = new StringBuilder();
BuildList(output, nodes);
return output.Remove(output.Length - 1, 1).ToString();
}
static void BuildList(StringBuilder output, List<TreeObject> nodes)
{
foreach (var node in nodes)
{
output.AppendFormat("{0},", node.Name);
BuildList(output, node.Children);
}
}
}
public class TreeObject
{
private List<TreeObject> _children = new List<TreeObject>();
public string Name { get; set; }
public Guid Id { get; set; }
public List<TreeObject> Children { get { return _children; } }
}
}
gregmac
で指定された例を修正するIList<TreeObject> FlatToHierarchy(IQueryable<lcc_classe> list, int? parentId)
{
var q = (from i in list
where i.parent_id == parentId
select new
{
id = i.id,
parent_id = i.parent_id,
kks = i.kks,
nome = i.nome
}).ToList();
return q.Select(x => new TreeObject
{
children = FlatToHierarchy(list, x.id)
}).ToList();
}
