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

Question

我在 JavaScript 中编写了允许生成任何二叉树的代码（每个 parent 都有 2 个 children）。

用户可以通过名为 "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，树看起来像：

树中的每个 object 都有：

-name - 模式中的第一个字段，它应该包含 object、

的 ID

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

-属性 - 没关系，

-children.

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

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

Answer 1

如果在添加下面的级别之前添加直接子级，那么它将以广度优先而不是深度优先的方式完成。我已将下面对 properties 的调用替换为 undefined，因为它未包含在您问题的代码段中。

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

var levels = 3;


prop = undefined; // 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 = undefined; // properties("Object_" + tempIndex);

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

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

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

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

// Check tree is as expected
console.log(tree);

Answer 2

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

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

How to change preservation of recursion in a binary tree indexing?

javascript

recursion

json

binary-tree