2

我有一个带有孩子的数据树结构：

{  id: 1,
   name: "Dog",
   parent_id: null,
   children: [
         {
             id: 2,
             name: "Food",
             parent_id: 1,
             children: []
         },
         {
             id: 3,
             name: "Water",
             parent_id: 1,
             children: [
                 {
                    id: 4,
                    name: "Bowl",
                    parent_id: 3,
                    children: []
                 },
                 {
                    id: 5,
                    name: "Oxygen",
                    parent_id: 3,
                    children: []
                 },
                 {
                    id: 6,
                    name: "Hydrogen",
                    parent_id: 3,
                    children: []
                 }
             ]
         }
   ]
}

如上数据所示，任何子数据对象都可以有更多子数据。这表示一个 DOM 结构，用户可以从中选择一个项目来添加一个子项。

我有来自 DOM 的所选项目的已知文本标题以及用户想要插入的数据。我无法找到一个递归算法，该算法允许我将新数据添加到树的正确级别。

这是我思考问题并尝试对其进行伪编码的列表：

输入：

  1. 树（上面的数据）
  2. 来自 DOM 中单击项目的 parentTitle

输出：

  1. 插入项目的树

脚步：

  1. 确定最高使用的 id 以了解下一个唯一 id 是什么
  2. 检查当前数据级别是否与父级标题匹配
  3. 如果匹配，则在新数据中设置 id 和 parent_id 并推送到父级的子级
  4. 如果不匹配，则检查当前级别数据是否有子级
  5. 如果当前级别有孩子需要为每个重复步骤 2+，直到找到匹配项

这是我的代码：

function askUserForNewItem(e) {
   const tree = getTree(); // returns above tree data structure
   const name = prompt( 'Enter new item’s name:' ); // user input to match and insert as new item in tree
   const clickedTitle = getClickedTitle(e); // returns string title of clicked on item from DOM - for example "Dog" or "Bowl"
   const parent = determineParent(tree, clickedTitle);
   const parent_id = parent[0].id;
   // TODO - needs to set real unique id (highest unused id)
   const newId = 101; // hard coded for now, needs to be dynamic
   // TODO - needs to insert into correct level of children array in tree
   return tree.children.push({ id: newId, name, emoji, children: [], parent_id: parent_id });
}

function determineParent(tree, clickedTitle) {

    if(tree.children.length === 0) {
        return false;
    }
    let treeLevel = tree;
    let parent = [];
    while(treeLevel.children.length !== 0) {
        parent = treeLevel.children.filter(child => child.name === clickedTitle);
        if(parent.length !== 0) {
            break;
        }
        else {
            // what to do here to make this recursive?
        }
    }

    return parent;
}

因此，如果用户在单击“狗”的添加按钮时键入“猫”，那么一个新对象

{
    id: 7,
    name: "Cat",
    parent_id: 1,
    children: []
}

将插入到数据树中第一级“Dog”对象的子项中。

4

3 回答 3

1

如果您想要一个递归解决方案，您应该修改 determineParent 方法，以便它向下搜索树。不确定这正是您要搜索的内容，但我希望您能大致了解

function determineParent(curNode, clickedTitle) {
    if(curNode.name===clickedTitle)
        return curNode; // found the parent node with the correct clickedTitle

    // not found yet, do a recusive search down the tree.

    for(const node of curNode.children) {
        return determineParent(node,clickedTitle);
    }

    return null; // not found.
}

这个想法是从最顶层的节点（curNode）开始，首先确定它是否是正确的父节点，如果不是，则取第一个子节点，看看它是否匹配，如果不匹配，则向下搜索它的子节点，依此类推。

在处理递归时，可能需要处理可能遇到循环引用的情况，考虑一个节点有一个指向节点父节点或祖父节点的子节点的场景，递归方法将永远运行（在现实生活中它将运行堆栈空间不足并抛出异常）。

一种方法是包含一个安全计数器，该计数器在每次递归调用时都会减少，然后在达到零时退出。

function determineParent(curNode, clickedTitle, safeGuard) {
    if(curNode.name===clickedTitle)
        return curNode; // found the parent node with the correct clickedTitle

    if(safeGuard===0)
        return null; // bail out 

    // not found yet, do a recusive search down the tree.
    for(const node of curNode.children) {
        return determineParent(node,clickedTitle,--safeGuard);
    }

    return null; // not found.
}

然后像这样称呼它

  this.determineParent(tree,"title",100);

将搜索次数限制为 100。

于 2019-03-09T18:09:41.597 回答
0

如果可以使用 Lodash+ Deepdash，那么：

let child = {
    name: "Cat",
    children: []
};
let maxUsedId=-1;
_.eachDeep([data],(val)=>{
  if(val.id>maxUsedId){
    maxUsedId = val.id;
  }

  if(val.name==parentName){
    val.children.push(child);
    child.parent_id = val.id;
  }
},{tree:true});
child.id=maxUsedId+1;

为此编写代码

于 2019-03-11T21:04:34.560 回答
0

不喜欢重新发明轮子，尤其是在算法方面。以下是如何使用对象扫描来解决您的问题。我们将它用于数据处理，因为一旦您将头绕在它周围，它就会非常强大

// const objectScan = require('object-scan');

const insert = (tree, parentName, childName) => objectScan(['**.name'], {
  abort: true,
  rtn: 'bool',
  filterFn: ({ value, parent }) => {
    if (value === parentName) {
      parent.children.push({
        id: Math.max(...objectScan(['**.id'], { rtn: 'value' })(tree)) + 1,
        name: childName,
        parent_id: parent.id,
        children: []
      });
      return true;
    }
    return false;
  }
})(tree);

const data = { id: 1, name: 'Dog', parent_id: null, children: [{ id: 2, name: 'Food', parent_id: 1, children: [] }, { id: 3, name: 'Water', parent_id: 1, children: [{ id: 4, name: 'Bowl', parent_id: 3, children: [] }, { id: 5, name: 'Oxygen', parent_id: 3, children: [] }, { id: 6, name: 'Hydrogen', parent_id: 3, children: [] }] }] };

console.log(insert(data, 'Dog', 'Cat')); // true iff insert was successful
// => true

console.log(data);
// => { id: 1, name: 'Dog', parent_id: null, children: [ { id: 2, name: 'Food', parent_id: 1, children: [] }, { id: 3, name: 'Water', parent_id: 1, children: [ { id: 4, name: 'Bowl', parent_id: 3, children: [] }, { id: 5, name: 'Oxygen', parent_id: 3, children: [] }, { id: 6, name: 'Hydrogen', parent_id: 3, children: [] } ] }, { id: 7, name: 'Cat', parent_id: 1, children: [] } ] }
.as-console-wrapper {max-height: 100% !important; top: 0}
<script src="https://bundle.run/object-scan@13.7.1"></script>

免责声明：我是对象扫描的作者

于 2020-11-18T02:21:29.247 回答