javascript - 如何在javascript中从数组制作二叉树？

Question

我有一个数组 var array = [8,10,12,5,3,6];

逻辑

1. 第一个节点将是根节点。
2. 如果新节点值小于或等于=<比父节点，就是父节点的左节点
3. 如果新节点值大于>比父节点，就是父节点的右节点

我正在尝试实现如下对象的输出:

{
   value:8,
   left:{
      value:5,
      left:{ value:3 },
      right:{value:6}
   },
   right:{
      value:10,
      right:{value:12}
   }
}

像这样的图片

我试过下面的代码:

var arr = [8,10,12,5,3,6];
var root = arr[0];
var rv = {};
for (var i = 0; i < arr.length; i++){
    if(arr[i] < root){
    rv.left = arr[i];
  }else{
    rv.right = arr[i];
  }
}
console.log(rv);

请帮我解决这个问题。

Answer 1

您可以为新节点使用 Node 实例，并为插入节点使用函数。

然后迭代这些值并构建一棵新树。

function Node(value) {
    this.value = value;
    // this.left = null;
    // this.right = null;
}

function insertNode(tree, value) {
    var node = tree,
        key;
    while (node.value !== value) {
         key = value < node.value ? 'left' : 'right';
         if (!node[key]) {
             node[key] = new Node(value);
             break;
         }
         node = node[key];
    }
    return tree;
}

var array = [8, 10, 12, 5, 3, 6],
    tree = array.reduce((t, v) => t ? insertNode(t, v) : new Node(v), null);

console.log(tree);

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