如何在所有可能的子树上拆分一棵树？

Question

我正在尝试在 JS 上构建一个迭代器，它将采用一棵树并在每次迭代时 return 下一个可能的子树。

这里是一个源码树的例子：

{
  name: 'A',
  children: [
    {
      name: 'B',
      children: [
        {
          name: 'E'
        },
        {
          name: 'F'
        },
      ]
    },
    {
      name: 'C',
    }
  ]
}

结果应该是三次迭代

1. {
  name: 'A',
  children: [ 
    { 
      name: 'B', 
      children: [ 
        {
          name: 'E'
        } 
      ]
    }
  ]
}

2. {
  name: 'A',
  children: [ 
    { 
      name: 'B', 
      children: [ 
        {
          name: 'F'
        } 
      ]
    }
  ]
}

3. {
  name: 'A',
  children: [ 
    { 
      name: 'C', 
    }
  ]
}

有人可以给我提示或指出解决此问题的正确方向吗？

谢谢！

Answer 1

这对你有帮助。

var arry=[];
var obj={
  name: 'A',
  children: [
    {
      name: 'B',
      children: [
        {
          name: 'E'
        },
        {
          name: 'F'
        },
      ]
    },
    {
      name: 'C',
    }
  ]
};
    for(i=0;i<obj.children.length;i++)
    {
    var newObj={name:obj.name,children:[{name:obj.children[i].name}]};
    if(obj.children[i].children){
       for(j=0;j<obj.children[i].children.length;j++)
       {
         var newObj={name:obj.name,children:[{name:obj.children[i].name,children:          []}]};
         newObj.children[i].children[0]= {name: obj.children[i].children[j].name};
         arry.push(newObj);
      }
}
     else{
        arry.push(newObj);
     }
}
for(k=0;k<arry.length;k++){
    console.log(arry[k]);
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>

Answer 2

我认为递归函数就是你的答案。

是这样的吗？

（使用您的示例有效）

var newtrees = [];

var getTreeFromPath = function(path) {
   var newtree = {};
   var next = newtree;
   for (var i = 0 ; i < path.length;i++) {
       next.name = path[i].name;
       if (path[i].children) {
          var nextIteration = {};
          next.children = [nextIteration];
       }
       next = nextIteration;
   }
   return newtree;

}
var iterateNode = function(node, pathToNode) {
   if (!node.children) { 
       pathToNode.push(node);
       newtrees.push(getTreeFromPath(pathToNode));
   } else {
       pathToNode.push(node);
       for (var i = 0;i < node.children.length;i++) {

          iterateNode(node.children[i], pathToNode);
       }
   }
};
iterateNode(tree, []);

如何在所有可能的子树上拆分一棵树？

How to split a tree on all possible subtrees?

javascript

tree

traversal

graph