19

次の親子オブジェクトのリストを変換するのを手伝ってくれる人はいますか:

[
   {
      "名前":"ルート",
      "_id":"root_id",
   }、
   {
      "名前":"a1",
      "parentAreaRef":{
         "id":"root_id",
      }、
      "_id":"a1_id",
   }、
   {
      "名前":"a2",
      "parentAreaRef":{
         "id":"a1_id",
      }、
      "_id":"a2_id",
   }、
   {
      "名前":"a3",
      "parentAreaRef":{
         "id":"a2_id",
      }、
      "_id":"a3_id",
   }、
   {
      "名前":"b1",
      "parentAreaRef":{
         "id":"root_id",
      }、
      "_id":"b1_id",
   }、
   {
      "名前":"b2",
      "parentAreaRef":{
         "id":"b1_id",
      }、
      "_id":"b2_id",
   }、
   {
      "名前":"b3",
      "parentAreaRef":{
         "id":"b1_id",
      }、
      "_id":"b3_id",
   }
]

親子関係を示すツリー構造に:

[
    {
        "名前": "ルート",
        "_id":"root_id",
        "子供"： [
            {
                "名前": "a1",
                "_id":"a1_id",
                "子供" ： [
                    {
                        「名前」：「a2」、
                        "_id":"a2_id",
                        "子供" ： [
                            {
                                「名前」：「a3」
                                "_id":"a3_id"
                            }
                        ]
                    }
                ]
            }、
            {
                "名前": "b1",
                "_id":"b1_id",
                "子供" ： [
                    {
                        「名前」：「b2」
                        "_id":"b2_id"
                    }、
                    {
                        「名前」：「b3」
                        "_id":"b3_id"
                    }
                ]
            }
        ]
    }
]

(出力構造は、複数のルートを許可する配列ですが、単一のルートを処理するソリューションを取得できれば、それも素晴らしいことです。)

出力ツリーは次のようになります。

根
  | |
  -- a1
  | | | |
  | | -- a2
  | | | |
  | | -- a3
  | |
  -- b1
      | |
      -- b2
      -- b3

ありがとう！

4

7 に答える 7

28

私はうまくいく解決策を持っています。解決までのヒントを教えます。良いことは、データにノードへの前方参照が含まれていないことです。したがって、配列を 1 回通過するだけでツリーを作成できます。注意が必要な場合は、ノードへの ID のマップを構築するために、最初に配列全体を通過させる必要があります。

アルゴリズムは次のようになります。

  1. ID をノードにマップするマップを作成します。これにより、ノードの検索が容易になります。
  2. ノードの配列をループします。
  3. 各要素について。
    1. マップにエントリを追加します。
    2. childrenこのノードにプロパティ (配列) を追加します。
    3. 要素には親がありますか? そうでない場合はルートでなければならないので、この要素をツリーのルートに割り当てます。
    4. この要素には親があるため、親ノードを検索し、この現在のノードを親ノードの子として追加します (children配列に追加します)。

これは問題の解決に役立ちます。このアルゴリズムに特定の問題がある場合は、問題の場所と解決方法を指摘するか、解決策を投稿して、どのように解決したかを説明できます。

アップデート

私はあなたが持っている解決策を見ました。これには実際には再帰は必要なく、上で説明したアルゴリズムを使用して繰り返し行うことができます。また、構造をインプレースで変更しているため、アルゴリズムがより複雑になります。しかし、あなたはある程度正しい軌道に乗っています。これが私がそれを解決した方法です：

var idToNodeMap = {}; //Keeps track of nodes using id as key, for fast lookup
var root = null; //Initially set our loop to null

//loop over data
data.forEach(function(datum) {

    //each node will have children, so let's give it a "children" poperty
    datum.children = [];

    //add an entry for this node to the map so that any future children can
    //lookup the parent
    idToNodeMap[datum._id] = datum;

    //Does this node have a parent?
    if(typeof datum.parentAreaRef === "undefined") {
        //Doesn't look like it, so this node is the root of the tree
        root = datum;        
    } else {        
        //This node has a parent, so let's look it up using the id
        parentNode = idToNodeMap[datum.parentAreaRef.id];

        //We don't need this property, so let's delete it.
        delete datum.parentAreaRef;

        //Let's add the current node as a child of the parent node.
        parentNode.children.push(datum);        
    }
});

rootツリー全体を指すようになりました。

フィドル。

要素の配列が任意の順序になっている場合は、idToNodeMap最初に初期化する必要があります。アルゴリズムの残りの部分は、多かれ少なかれ同じままです (マップにノードを格納する行を除きます。最初のパスで既に行っているため、これは必要ありません)。

var idToNodeMap = data.reduce(function(map, node) {
    map[node._id] = node;
    return map;
}, {});
于 2013-04-03T17:11:39.890 に答える
3

遅すぎることはわかっていますが、これを行う方法のサンプル実装への貢献を終えたばかりなので、それを共有したいと思いました.

実装はここにあります: http://jsfiddle.net/sw_lasse/9wpHa/

実装の主なアイデアは、次の再帰関数を中心にしています。

// Get parent of node (recursive)
var getParent = function (rootNode, rootId) {

    if (rootNode._id === rootId)
        return rootNode;

    for (var i = 0; i < rootNode.children.length; i++) {
        var child = rootNode.children[i];
        if (child._id === rootId)
            return child;

        if (child.children.length > 0)
            var childResult = getParent(child, rootId);

        if (childResult != null) return childResult;
    }
    return null;
};

... ツリーの構築に使用されます。

于 2013-04-03T17:42:14.103 に答える
1

Vivin Paliath の回答からキャッシング ロジックを借りて、親子関係を持つデータのリストをツリーに変換する再利用可能な関数を作成しました。

var data = [
  { "id" : "root"                     },
  { "id" : "a1",   "parentId" : "root", },
  { "id" : "a2",   "parentId" : "a1",   },
  { "id" : "a3",   "parentId" : "a2",   },
  { "id" : "b1",   "parentId" : "root", },
  { "id" : "b2",   "parentId" : "b1",   },
  { "id" : "b3",   "parentId" : "b1",   }
];
var options = {
  childKey  : 'id',
  parentKey : 'parentId'
};
var tree = walkTree(listToTree(data, options), pruneChildren);

document.body.innerHTML = '<pre>' + JSON.stringify(tree, null, 4) + '</pre>';

function listToTree(list, options) {
  options = options || {};
  var childKey    = options.childKey    || 'child';
  var parentKey   = options.parentKey   || 'parent';
  var childrenKey = options.childrenKey || 'children';
  var nodeFn      = options.nodeFn      || function(node, name, children) {
    return { name : name, children : children };
  };
  var nodeCache = {};
  return list.reduce(function(tree, node) {
    node[childrenKey] = [];
    nodeCache[node[childKey]] = node;
    if (typeof node[parentKey] === 'undefined' || node[parentKey] === '') {
      tree = nodeFn(node, node[childKey], node[childrenKey]);
    } else {
      parentNode = nodeCache[node[parentKey]];
      parentNode[childrenKey].push(nodeFn(node, node[childKey], node[childrenKey]));
    }
    return tree;
  }, {});
}

function walkTree(tree, visitorFn, parent) {
  if (visitorFn == null || typeof visitorFn !== 'function') {
    return tree;
  }
  visitorFn.call(tree, tree, parent);
  if (tree.children && tree.children.length > 0) {
    tree.children.forEach(function(child) {
      walkTree(child, visitorFn, tree);
    });
  }
  return tree;
}

function pruneChildren(node, parent) {
  if (node.children.length < 1) {
    delete node.children;
  }
}

于 2016-03-31T11:51:24.253 に答える
0

試してみる：

   var obj = {};
   obj.rootElements = [];
   var currentRoot;
   var currentParent;
   for (s in a) {
       var t = a[s];
       var id = t._id;
       if (t.parentAreaRef) {
           var parentId = t.parentAreaRef.id;
           if (parentId == currentParent._id) {
               //add children
               if (!currentParent.children) {
                   currentParent.children = [];
               }
               currentParent.children.push(t);
           }
           else {
               addChildToParent(t, parentId);
           }

       }
       else // is root
       {
           currentRoot = t;
           currentParent = t;
           obj.rootElements.push(currentRoot);
       }
   }

   var t = currentRoot

   function addChildToParent(child, parentId, root) {
       for (p in a) {
           if (a[p]._id.toString() == parentId.toString()) {
               if (!a[p].children) {
                   a[p].children = [];
               }
               a[p].children.push(t);
           }
       }
   }
于 2013-04-03T17:11:59.723 に答える
0

文字列にエラーがあります

a[p].children.push(t);

そのはず

a[p].children.push(child);

また、私はそれをほとんど最適化していません:

var data = [{"id":1,"name":"X","parentId":null},{"id":2,"name":"Y","parentId":1},{"id":3,"name":"D","parentId":2},{"id":2,"name":"S","parentId":1},{"id":5,"name":"K","parentId":4}]
    var obj = {};
    obj.rootElements = [];
    for (i in data) {
        var _elem = data[i];
        if (_elem.parentId) {
            var _parentId = _elem.parentId;
            if (_parentId == _elem.id) {
                // check children, if false - add
                if (!_elem.children) {
                    _elem.children = [];
                }
                _elem.children.push(_elem);
            }
            else {
                addChildToParent(_elem, _parentId);
            }
        }
        else // is root
        {
            obj.rootElements.push(_elem);
        }
    }
    function addChildToParent(child, parentId, root) {
        for (j in data) {
            if (data[j].id.toString() == parentId.toString()) {
                if (!data[j].children) {
                    data[j].children = [];
                }
                data[j].children.push(child);
            }
        }
    }
    res.send(obj.rootElements);
于 2015-06-17T16:04:32.670 に答える