javascript - 如何更改二叉树索引中递归的保留？

Question

我用 JavaScript 编写了代码，它允许生成任何二叉树(每个 parent 都有 2 个 child )。

用户可以通过名为“levels”的变量指定他想要的树的层数。

代码:

function TreeNode(name, type, properties, children) {
    this.name = name;
    this.type = type;
    this.properties = properties;
    this.children = children;
}

var levels = 3;


prop = properties("Object_1");

var tree = new TreeNode("Object_1", "level_1", prop, []);

levels--;

var tempIndex = 2;

function generateArbitraryLevels(parent, levelsRemaining) {
    // last level
    if (levelsRemaining === 0) return;

    var currentLevel = parseInt(parent.type.split('_')[1]) + 1;
    var prop1 = properties("Object_" + tempIndex);

    parent.children.push(
        new TreeNode("Object_" + tempIndex++, "level_" + currentLevel, prop1, [])
    );


    generateArbitraryLevels(parent.children[0], levelsRemaining - 1);

    var prop2 = properties("Object_" + tempIndex);

    parent.children.push(
        new TreeNode("Object_" + tempIndex++, "level_" + currentLevel, prop2, [])
    );
    generateArbitraryLevels(parent.children[1], levelsRemaining - 1);

}

generateArbitraryLevels(tree, levels);
tree = JSON.stringify([tree]);

例如，对于“levels”= 3，树看起来像:

树中的每个对象都有:

-name - 模式中的第一个字段，它应该包含对象的 ID，

-type - 第二个字段，它有关于对象级别的信息，

-属性 - 没关系，

- child 。

它工作正常，但我真的想更改对象索引。树应该看起来像:

所以索引应该是从左到右的。我怎样才能做到这一点？也许循环会更好？

Answer 1

我相信您正在寻找广度优先，而不是您已经实现的深度优先。查看下面的链接以获取有关树中广度优先算法的更多信息 https://www.cs.bu.edu/teaching/c/tree/breadth-first/

您可以引用以下代码来实现您的用例示例

    const TreeNode = (name, type, properties, children) => ({
      name,
      type,
      properties,
      children,
    });
    
    const getNode = (index, level, properties) => {
      const name = `Object_${index}`;
      const type = `level_${level}`;
      return TreeNode(name, type, properties[name], []);
    };
    
    const generateTreeChildren = (node, currentLevel, maxLevels, index, properties) => {
      if (currentLevel > maxLevels) {
        return null;
      }
    
      const child1 = getNode(index, currentLevel, properties);
      const child2 = getNode(index + 1, currentLevel, properties);
    
      node.children = [child1, child2];
    
      generateTreeChildren(child1, currentLevel + 1, maxLevels, index + 2, properties);
      generateTreeChildren(child2, currentLevel + 1, maxLevels, index + 4, properties);
    };
    
    const generateTree = (maxLevels, properties) => {
      if (maxLevels === 0) {
        return null;
      }
    
      const node = getNode(1, 1, properties);
    
      generateTreeChildren(node, 2, maxLevels, 2, properties);
    
      return node;
    };

    console.info(JSON.stringify(generateTree(3, {})));