3

次のような階層データ構造があります。

var tree = [ {foo: 1, children:[
    {foo: 2, children:[
        {foo: 13, children:[]},
        {foo: 14, children:[]}
    ]}, 
    {foo: 3, children:[]}, 
    {foo: 4, children:[]}
]}, 

{foo: 5, children:[
    {foo: 6, children:[]}, 
    {foo: 8, children:[]}
]}, 

{foo: 9, children:[
    {foo: 10, children:[]}, 
    {foo: 11, children:[]}, 
    {foo: 12, children:[]}
]} ];

ツリーの深さは任意です。

ツリー内の特定のオブジェクト (その子を含む) を再配置するには、次のように簡単に記述できます。

// Move object from [0, 0, 1] to [2, 1]
var obj = tree[0]['children'][0]['children'][1];
tree[0]['children'][0]['children'].splice(1, 1);
tree[2]['children'].splice(1, 0, obj);

しかし、一般的なケースをプログラムすることはできません:

2 組の座標を指定して、オブジェクトを [i1, i2, ..., im] から [j1, j2, ..., jn] に再配置します。

この再帰アルゴリズムを構築する方法についてのヒントが欲しいです。これは純粋な Javascript の質問ですが、私のアプリケーションは AngularJS と jQuery を使用していることに注意してください。おそらくこれらのライブラリは、私が使用できる配列操作関数を提供していますか?

4

2 に答える 2

3

主な問題は、プロパティに任意の深さまでアクセスする必要があることです。これに使用できるのは、ある意味で再帰的なループです。

// a is the input set

var arr = tree;  // start at the root
for(var i = 0; i < a.length - 1; i++) {  // stop one too early
  arr = arr[ a[i] ].children;
}
// now, arr is the array you want to splice, so
// you can splice the object and store it in a temporary
// place

同じロジックを使用して、出力配列にトラバースし、そこに値を追加できます。

于 2013-01-02T10:50:40.347 に答える
3

このツリー トラバーサルを行う 1 つの方法は、変数を使用して、一度にレイヤーをナビゲートしながら、ナビゲートしたツリーの部分への参照を格納することです。次のようにトラバーサル関数を書くことができます。

var traverseTree = function(tree, coord) {

  var current = tree;

  // Loop through the coordinates moving one at a time, no error handling
  // what happens if the node doesn't exist?
  for(var i = 0; i < coord.length; ++i) {
    current = current[coord[i]].children;
  }      

  // Return the node
  return current;
}

次に、ノードを抽出するメソッドとノードを挿入するメソッドの 2 つの関数として記述された機能を記述できます。

var extractNodeFromTree = function(tree, coord) {

  // We don't want to traverse the whole way
  var last = coord.pop();

  // Traverse to the parent
  var parent = traverseTree(tree, coord);

  // Extract the element using the last coordinate
  return parent.splice(last, 1)[0];
}

var insertNodeIntoTree = function(tree, coord, node) {

  // Same as last method
  var last = coord.pop();
  var parent = traverseTree(tree, coord);

  // Insert node to the specified position
  current.splice(last, 0, node);

}

次のように関数を使用できます。

var node = extractNodeFromTree(tree, [0, 0, 1]);
insertNodeIntoTree(tree, [2, 1], node);

実際にそれを示すためのフィドル

于 2013-01-02T10:51:13.607 に答える