5

次のような深い JSON オブジェクトの配列があります。

var hierarchy = [
  {
    "title": "category 1",
    "children": [
      {"title": "subcategory 1",
        "children": [
          {"id": 1, "title": "name 1"},
          {"id": 2, "title": "name 2"},
          {"id": 3, "title": "name 3"}
        ]
      },
      {"title": "subcategory 2",
        "children": [
          {"id": 1, "title": "name 4"}
        ]
      }
    ]
  },
  {
    "title": "category 2",
    "children": [etc. - shortened for brevity]
  }
];

したがって、基本的には階層です。いくつかの ID と名前を持つオブジェクトを含むサブカテゴリを持つことができるカテゴリがあります。また、最も深い階層レベル (子を持たないオブジェクト) に関連する ID の配列もあり、定義されたオブジェクトを含む (サブ) カテゴリのみが残るように、このオブジェクトのセットをフィルター処理する必要があります。

たとえば、2 つの ID を含む配列があるとします。

var IDs = [2, 3];

結果は次のようになります。

var hierarchy = [
  {
    "title": "category 1",
    "children": [
      {"title": "subcategory 1",
        "children": [
          {"id": 2, "title": "name 2"},
          {"id": 3, "title": "name 3"}
        ]
      }
    ]
  }
];

つまり、「カテゴリ 2」オブジェクト全体が削除され、「サブカテゴリ 2」全体が削除され、ID「1」のオブジェクトが削除されます。

問題は、これらのオブジェクトの深さが可変で不明であることです。一部のオブジェクトには子がなく、一部のオブジェクトには子もあり、サブカテゴリ自体がサブカテゴリを持つことができ、基本的には子を持たないオブジェクトを見つける必要があります。 ID を定義し、それぞれへのパス全体を保持します。

ありがとうございました。

4

4 に答える 4

6

基本的に、各ノードでコールバック関数を呼び出して、ツリーの深さ優先トラバーサルを実行します。そのノードがリーフ ノードであり、その ID がリストに表示される場合は、そのリーフにつながるブランチを複製しますが、既に複製されたブランチのどの部分も再複製しないでください。

ツリーの部分コピーとフィルター コピーを作成したら、オリジナルをクリーンアップする必要があります。どのブランチがすでに複製されているかを追跡するために、簿記の目的で元のツリーを変更しました。

編集：単一のツリーではなく、ツリーのリストをフィルタリングするようにコードを修正

var currentPath = [];

function depthFirstTraversal(o, fn) {
    currentPath.push(o);
    if(o.children) {
        for(var i = 0, len = o.children.length; i < len; i++) {
            depthFirstTraversal(o.children[i], fn);
        }
    }
    fn.call(null, o, currentPath);
    currentPath.pop();
}

function shallowCopy(o) {
    var result = {};
    for(var k in o) {
        if(o.hasOwnProperty(k)) {
            result[k] = o[k];
        }
    }
    return result;
}

function copyNode(node) {
    var n = shallowCopy(node);
    if(n.children) { n.children = []; }
    return n;
}

function filterTree(root, ids) {
    root.copied = copyNode(root); // create a copy of root
    var filteredResult = root.copied;

    depthFirstTraversal(root, function(node, branch) {
        // if this is a leaf node _and_ we are looking for its ID
        if( !node.children && ids.indexOf(node.id) !== -1 ) {
            // use the path that the depthFirstTraversal hands us that
            // leads to this leaf.  copy any part of this branch that
            // hasn't been copied, at minimum that will be this leaf
            for(var i = 0, len = branch.length; i < len; i++) {
                if(branch[i].copied) { continue; } // already copied

                branch[i].copied = copyNode(branch[i]);
                // now attach the copy to the new 'parellel' tree we are building
                branch[i-1].copied.children.push(branch[i].copied);
            }
        }
    });

    depthFirstTraversal(root, function(node, branch) {
        delete node.copied; // cleanup the mutation of the original tree
    });

    return filteredResult;
}

function filterTreeList(list, ids) {
    var filteredList = [];
    for(var i = 0, len = list.length; i < len; i++) {
        filteredList.push( filterTree(list[i], ids) );
    }
    return filteredList;
}

var hierarchy = [ /* your data here */ ];
var ids = [1,3];

var filtered = filterTreeList(hierarchy, ids);
于 2013-10-20T23:07:03.427 に答える
0

これは古い質問ですが、2 セント追加します。このソリューションでは、ループ、サブループなどを単純に反復し、ID を比較して結果のオブジェクトを構築する必要があります。私は純粋なjavascriptとjQueryのソリューションを持っています。上記の例では純粋な JavaScript が機能しますが、jQuery ソリューションをお勧めします。これは、より汎用的であり、オブジェクトの「ディープ コピー」を実行するためです。大きくて複雑なオブジェクトがある場合は、バグに遭遇することはありません。

function jsFilter(idList){
  var rsltHierarchy=[];
  for (var i=0;i<hierarchy.length;i++) {
    var currCatg=hierarchy[i];
    var filtCatg={"title":currCatg.title, "children":[]};
    for (var j=0;j<currCatg.children.length;j++) {
  	var currSub=currCatg.children[j];
  	var filtSub={"title":currSub.title, "children":[]}
  	for(var k=0; k<currSub.children.length;k++){
  		if(idList.indexOf(currSub.children[k].id)!==-1)
  		   filtSub.children.push({"id":currSub.children[k].id, "title":currSub.children[k].title});
  	}
  	if(filtSub.children.length>0)
  		filtCatg.children.push(filtSub);
    }
    if(filtCatg.children.length>0)
  	rsltHierarchy.push(filtCatg);
  }
  return rsltHierarchy;
}

function jqFilter(idList){
  var rsltHierarchy=[];
  $.each(hierarchy, function(index,currCatg){
      var filtCatg=$.extend(true, {}, currCatg);
      filtCatg.children=[];
  	$.each(currCatg.children, function(index,currSub){
        var filtSub=$.extend(true, {}, currSub);
  	  filtSub.children=[];
  	  $.each(currSub.children, function(index,currSubChild){
  		if(idList.indexOf(currSubChild.id)!==-1)
  		  filtSub.children.push($.extend(true, {}, currSubChild));
        });
  	  if(filtSub.children.length>0)
  		filtCatg.children.push(filtSub);
      });
      if(filtCatg.children.length>0)
  	  rsltHierarchy.push(filtCatg);
  });
  return rsltHierarchy;
}

//Now test the functions...
var hierarchy = eval("("+document.getElementById("inp").value+")");
var IDs = eval("("+document.getElementById("txtBoxIds").value+")");

document.getElementById("oupJS").value=JSON.stringify(jsFilter(IDs));
$(function() {
   $("#oupJQ").text(JSON.stringify(jqFilter(IDs)));
});
#inp,#oupJS,#oupJQ {width:400px;height:100px;display:block;clear:all}
#inp{height:200px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.1/jquery.min.js"></script>

ID List: <Input id="txtBoxIds" type="text" value="[2, 3]">

<p>Input:
<textarea id="inp">[
  {
    "title": "category 1",
    "children": [
      {"title": "subcategory 11",
        "children": [
          {"id": 1, "title": "name 1"},
          {"id": 2, "title": "name 2"},
          {"id": 3, "title": "name 3"}
        ]
      },
      {"title": "subcategory 12",
        "children": [
          {"id": 1, "title": "name 4"}
        ]
      }
    ]
  },
  {
    "title": "category 2",
    "children": [
      {"title": "subcategory 21",
        "children": [
          {"id": 3, "title": "name cat2sub1id3"},
          {"id": 5, "title": "name cat2sub1id5"}
        ]
      },
      {"title": "subcategory 22",
        "children": [
          {"id": 6, "title": "name cat2sub2id6"},
          {"id": 7, "title": "name cat2sub2id7"}
        ]
      }
    ]
  }
]</textarea>

<p>Pure-Javascript solution results:
<textarea id="oupJS"></textarea>

<p>jQuery solution results:
<textarea id="oupJQ"></textarea>

于 2015-11-23T21:34:30.190 に答える