テーブルからツリーを水和する

Question

私はすべてのノードが入ったDataTableを持っています。それらはデータベースにシリアライズされました。私はデータのオブジェクトグラフ（階層的）表現を作成したい。これを行うにはいくつかの方法があるようです。

This article describes a high order method（ツリーが完全に構築される前に、それはのDataTableの検索の多くを必要とするという意味）

注文-Nのアプローチはありますか？私の場合は、DataTableのツリーのノードをインオーダー形式に事前ソートしました。意味は、最初の行は、ルートであるため、親に対してNULLを示します。後続の各行はin-order notationにソートされます。

私は学校時代からOrder-Nアプローチを思い出しているようです。しかし、私は覚えていない。

私のDataTableのスキーマは、このようになります。

• のNodeID - NULL可能
• データ - - ParentNodeId
• をint型の文字列

Answer 1

は、ここではそれを実行する必要が何をすべきなアルゴリズムです。あなたのデータは順序通りであると仮定し、O（n）で実行します。

class Node { 
    Node Parent; 
    List<Node> Children = new List<Node>(); 
    int NodeId; 
    string Data; 
    public Node(NodeRow row) { ... } 
} 

1. がcurrentとして最初の行をロードします。

   まず、あなたはこのようになりますノードを必要としています。

2. 次の行をロードします。 newRow.ParentNodeId〜current.NodeIdを比較してください。
3. あなたが一致するものを見つけるまで、current.ChildrenにnewRowを追加し、新しい行にcurrentを設定current = current.Parent
4. を設定します。
5. 行くことだ2.

をステップ！データが正しく構造化されていることが保証されている場合は、追加のnullチェックを行う必要はありません。

サンプル：

Node CreateTree(IEnumerable<NodeRow> rows) { 
    Node root = null; 
    Node current = null; 
    foreach (var row in rows) { 
     // Root: 
     if (root == null) { 
      root = current = new Node(row); 
      continue; 
     } 
     // Traverse up the tree until the parent is found: 
     while (row.ParentNodeId != current.NodeId) { 
      current = current.Parent; 
     } 
     // Add the new node as a child of the current one: 
     var rowNode = new Node(row); 
     rowNode.Parent = current; 
     current.Children.Add(rowNode); 
     current = rowNode; 
    } 
    return root; 
}