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

问题描述

我用 JavaScript 编写了允许生成任何二叉树的代码（每个父母都有 2 个孩子）。

用户可以通过称为“级别”的变量指定他想要的树的多少级别。

代码：

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 - 第二个字段，它包含有关对象级别的信息，

- 属性- 没关系，

-儿童。

它工作正常，但我真的想更改对象索引。树应如下所示：

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

标签： javascriptjsonrecursionbinary-tree

我相信你正在寻找Breadth First而不是Depth First你已经实施。检查下面的链接以获取有关树中广度优先算法的更多信息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, {})));

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

问题描述

解决方案

推荐阅读