平らな構造のオブジェクトがたくさんあります。これらのオブジェクトにはIDとParentIDプロパティがあるため、ツリーに配置できます。それらは特定の順序ではありません。各ParentIDプロパティは、必ずしもID構造内のと一致するとは限りません。したがって、それらはこれらのオブジェクトから出現するいくつかの木である可能性があります。
これらのオブジェクトをどのように処理して、結果のツリーを作成しますか？
私は解決策からそれほど遠くはありませんが、それは最適とはほど遠いことを確信しています...
これらのツリーを作成して、データを適切な順序でデータベースに挿入する必要があります。
循環参照はありません。ParentID == nullの場合、またはParentIDが他のオブジェクトで見つからない場合、ノードはRootNodeです。
オブジェクトのIDを、特定のオブジェクトにマッピングするハッシュテーブルに格納します。すべてのオブジェクトを列挙し、存在する場合はそれらの親を見つけ、それに応じてその親ポインターを更新します。
class MyObject
{ // The actual object
public int ParentID { get; set; }
public int ID { get; set; }
}
class Node
{
public List<Node> Children = new List<Node>();
public Node Parent { get; set; }
public MyObject AssociatedObject { get; set; }
}
IEnumerable<Node> BuildTreeAndGetRoots(List<MyObject> actualObjects)
{
Dictionary<int, Node> lookup = new Dictionary<int, Node>();
actualObjects.ForEach(x => lookup.Add(x.ID, new Node { AssociatedObject = x }));
foreach (var item in lookup.Values) {
Node proposedParent;
if (lookup.TryGetValue(item.AssociatedObject.ParentID, out proposedParent)) {
item.Parent = proposedParent;
proposedParent.Children.Add(item);
}
}
return lookup.Values.Where(x => x.Parent == null);
}
以下は、N 時間で実行される、フラット テーブルを親/子ツリー構造に解析する単純な JavaScript アルゴリズムです。
var table = [
{parent_id: 0, id: 1, children: []},
{parent_id: 0, id: 2, children: []},
{parent_id: 0, id: 3, children: []},
{parent_id: 1, id: 4, children: []},
{parent_id: 1, id: 5, children: []},
{parent_id: 1, id: 6, children: []},
{parent_id: 2, id: 7, children: []},
{parent_id: 7, id: 8, children: []},
{parent_id: 8, id: 9, children: []},
{parent_id: 3, id: 10, children: []}
];
var root = {id:0, parent_id: null, children: []};
var node_list = { 0 : root};
for (var i = 0; i < table.length; i++) {
node_list[table[i].id] = table[i];
node_list[table[i].parent_id].children.push(node_list[table[i].id]);
}
console.log(root);
Mehrdad Afshari の回答とスピードアップに関する Andrew Hanlon のコメントに基づいて、これが私の見解です。
元のタスクとの重要な違い: ルート ノードには ID==parentID があります。
class MyObject
{ // The actual object
public int ParentID { get; set; }
public int ID { get; set; }
}
class Node
{
public List<Node> Children = new List<Node>();
public Node Parent { get; set; }
public MyObject Source { get; set; }
}
List<Node> BuildTreeAndGetRoots(List<MyObject> actualObjects)
{
var lookup = new Dictionary<int, Node>();
var rootNodes = new List<Node>();
foreach (var item in actualObjects)
{
// add us to lookup
Node ourNode;
if (lookup.TryGetValue(item.ID, out ourNode))
{ // was already found as a parent - register the actual object
ourNode.Source = item;
}
else
{
ourNode = new Node() { Source = item };
lookup.Add(item.ID, ourNode);
}
// hook into parent
if (item.ParentID == item.ID)
{ // is a root node
rootNodes.Add(ourNode);
}
else
{ // is a child row - so we have a parent
Node parentNode;
if (!lookup.TryGetValue(item.ParentID, out parentNode))
{ // unknown parent, construct preliminary parent
parentNode = new Node();
lookup.Add(item.ParentID, parentNode);
}
parentNode.Children.Add(ourNode);
ourNode.Parent = parentNode;
}
}
return rootNodes;
}
@Mehrdad Afshariの回答に基づいて、C＃で一般的なソリューションを大まかに作成しました。
void Example(List<MyObject> actualObjects)
{
List<TreeNode<MyObject>> treeRoots = actualObjects.BuildTree(obj => obj.ID, obj => obj.ParentID, -1);
}
public class TreeNode<T>
{
public TreeNode(T value)
{
Value = value;
Children = new List<TreeNode<T>>();
}
public T Value { get; private set; }
public List<TreeNode<T>> Children { get; private set; }
}
public static class TreeExtensions
{
public static List<TreeNode<TValue>> BuildTree<TKey, TValue>(this IEnumerable<TValue> objects, Func<TValue, TKey> keySelector, Func<TValue, TKey> parentKeySelector, TKey defaultKey = default(TKey))
{
var roots = new List<TreeNode<TValue>>();
var allNodes = objects.Select(overrideValue => new TreeNode<TValue>(overrideValue)).ToArray();
var nodesByRowId = allNodes.ToDictionary(node => keySelector(node.Value));
foreach (var currentNode in allNodes)
{
TKey parentKey = parentKeySelector(currentNode.Value);
if (Equals(parentKey, defaultKey))
{
roots.Add(currentNode);
}
else
{
nodesByRowId[parentKey].Children.Add(currentNode);
}
}
return roots;
}
}
質問が曖昧に思えますが、おそらくIDから実際のオブジェクトへのマップを作成します。疑似Java（動作/コンパイルされているかどうかは確認していません）では、次のようになります。
Map<ID, FlatObject> flatObjectMap = new HashMap<ID, FlatObject>();
for (FlatObject object: flatStructure) {
flatObjectMap.put(object.ID, object);
}
そして、各親を検索するには：
private FlatObject getParent(FlatObject object) {
getRealObject(object.ParentID);
}
private FlatObject getRealObject(ID objectID) {
flatObjectMap.get(objectID);
}
getRealObject(ID)オブジェクトからオブジェクトのコレクション（またはそれらのID）へのマップを再利用して実行することにより、親->子のマップも取得します。
Dictionary が TreeMap のようなものであると仮定すると、4 行のコードと O(n log n) 時間でこれを実行できます。
dict := Dictionary new.
ary do: [:each | dict at: each id put: each].
ary do: [:each | (dict at: each parent) addChild: each].
root := dict at: nil.
編集:わかりました、そして今、いくつかのparentIDが偽物であることを読んだので、上記を忘れて、これを行います:
dict := Dictionary new.
dict at: nil put: OrderedCollection new.
ary do: [:each | dict at: each id put: each].
ary do: [:each |
(dict at: each parent ifAbsent: [dict at: nil])
add: each].
roots := dict at: nil.
質問者が探していたものとまったく同じではありませんが、ここで提供されているあいまいな表現の回答に頭を悩ませていましたが、この回答はタイトルの下に収まると思います.
私の答えは、フラットな構造を直接オブジェクト ツリーにマッピングすることです。このツリーでは、ParentID各オブジェクトに があるだけです。またはそれがルートである場合ParentID。質問者とは反対に、すべての有効なものがリスト内の何かを指していると仮定します。null0ParentID
var rootNodes = new List<DTIntranetMenuItem>();
var dictIntranetMenuItems = new Dictionary<long, DTIntranetMenuItem>();
//Convert the flat database items to the DTO's,
//that has a list of children instead of a ParentID.
foreach (var efIntranetMenuItem in flatIntranetMenuItems) //List<tblIntranetMenuItem>
{
//Automapper (nuget)
DTIntranetMenuItem intranetMenuItem =
Mapper.Map<DTIntranetMenuItem>(efIntranetMenuItem);
intranetMenuItem.Children = new List<DTIntranetMenuItem>();
dictIntranetMenuItems.Add(efIntranetMenuItem.ID, intranetMenuItem);
}
foreach (var efIntranetMenuItem in flatIntranetMenuItems)
{
//Getting the equivalent object of the converted ones
DTIntranetMenuItem intranetMenuItem = dictIntranetMenuItems[efIntranetMenuItem.ID];
if (efIntranetMenuItem.ParentID == null || efIntranetMenuItem.ParentID <= 0)
{
rootNodes.Add(intranetMenuItem);
}
else
{
var parent = dictIntranetMenuItems[efIntranetMenuItem.ParentID.Value];
parent.Children.Add(intranetMenuItem);
//intranetMenuItem.Parent = parent;
}
}
return rootNodes;
ほとんどの回答は、データベースの外部でこれを行うことを想定しています。ツリーが本質的に比較的静的であり、何らかの方法でツリーをデータベースにマップする必要があるだけの場合は、データベース側でネストされたセット表現の使用を検討することをお勧めします。Joe Celko の書籍をチェックしてください (Celkoによる概要については、こちら
を参照してください)。
とにかくOracleデータベースに結び付けられている場合は、直接的なSQLアプローチについてCONNECT BYをチェックしてください。
どちらのアプローチでも、データベースにデータをロードする前に、ツリーのマッピングを完全にスキップできます。これを代替手段として提供すると思っただけですが、特定のニーズには完全に不適切かもしれません. 元の質問の「適切な順序」の部分全体は、何らかの理由でデータベースで「正しい」順序にする必要があることを多少意味しますか? これは、私がそこの木を扱うことにも駆り立てられるかもしれません。
それらの属性だけを使用して立ち往生していますか? そうでない場合は、子ノードの配列を作成して、これらすべてのオブジェクトを 1 回循環させてそのような属性を作成するとよいでしょう。そこから、子を持つが親を持たないノードを選択し、ツリーを上から下に繰り返し構築します。
// node
@Data
public class Node {
private Long id;
private Long parentId;
private String name;
private List<Node> children = new ArrayList<>();
}
// flat list to tree
List<Node> nodes = new ArrayList();// load nodes from db or network
Map<Long, Node> nodeMap = new HashMap();
nodes.forEach(node -> {
if (!nodeMap.containsKey(node.getId)) nodeMap.put(node.getId, node);
if (nodeMap.containsKey(node.getParentId)) {
Node parent = nodeMap.get(node.getParentId);
node.setParentId(parent.getId());
parent.getChildren().add(node);
}
});
// tree node
List<Node> treeNode = nodeMap .values().stream().filter(n -> n.getParentId() == null).collect(Collectors.toList());