javascript - 如何在不递归的情况下将列表转换为二叉树

Question

作为练习，我尝试在不使用递归的情况下将列表转换为二叉树。

这基本上就是我卡住的地方。

var items = [
  { a: 1 }, { a: 10 }, { a: 100 }, { a: 20 }, { a: 2 },
  { a: 3 }, { a: 30 }, { a: 300 }, { a: 40 }, { a: 4 }
]

var top = {}

for (var i = 0, n = items.length; i < n; i+=2) {
  var a = items[i]
  var b = items[i + 1]

  top.left = { data: a }
  top.right = { data: b }

  top = top.right
}

top = top.right 显然是不正确的，它使得只有一个扩展树的分支被创建，所以它基本上只是一个链表和一个叶子的小芽在每个级别。

    /\
     /\
      /\
       /\
        /\
          \

我很难理解如何向下所有树的分支和将节点按顺序放入二叉树中，以便它们可以迭代/以它们在列表中的原始顺序遍历。我不确定这叫什么，如果我应该做一些版本的 DFS/BFS inorder/preorder/postorder，我不太确定。想知道是否有人可以在 JS 中演示如何做到这一点。

我什至不确定输出应该是什么，但如果我不得不猜测它会是这样的:

             top
       1             10
  100     20      2      3
30  300  40 4

Answer 1

您可以使用两个索引，一个用于节点 列表，另一个用于目标 列表。然后，将接下来的两个节点放在 target 节点的左右两侧。

继续，直到没有更多节点可用。

这棵树没有空的起始节点。

var items = [{ a: 1 }, { a: 10 }, { a: 100 }, { a: 20 }, { a: 2 }, { a: 3 }, { a: 30 }, { a: 300 }, { a: 40 }, { a: 4 }],
    tree = items[0],
    i = 1,
    j = 0;

while (i < items.length) {
    items[j].left = items[i++];
    if (i >= items.length) break;
    items[j].right = items[i++];
    j++;
}

console.log(tree);

.as-console-wrapper { max-height: 100% !important; top: 0; } 

稍微短一点的方法。

var items = [{ a: 1 }, { a: 10 }, { a: 100 }, { a: 20 }, { a: 2 }, { a: 3 }, { a: 30 }, { a: 300 }, { a: 40 }, { a: 4 }],
    tree = items[0],
    i = 1,
    side = 'right';

while (i < items.length) {
    side = { left: 'right', right: 'left' }[side];
    items[(i - 1) >> 1][side] = items[i++];
}

console.log(tree);

.as-console-wrapper { max-height: 100% !important; top: 0; }