原始数组

1
const originArr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];

将数组转为二叉树


如上图的二叉树所示，是一个按照层序遍历生成的二叉树。
最终的数据格式应该是这样的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
const BTree = {
	nodeName: 1,
  left: {
  	nodeName: 2,
    left: {
    	nodeName: 4,
      left: {
    		nodeName: 8,
      },
      right: {
        nodeName: 9,
      }
    },
    right: {
    	nodeName: 5,
      left: {
    		nodeName: 10,
      },
      right: {
        nodeName: 11,
      }
    }
  },
  right: {
  	nodeName: 3,
    left: {
    	nodeName: 6,
      left: {
    		nodeName: 12,
      },
      right: {
        nodeName: 13,
      }
    },
    right: {
    	nodeName: 7,
      left: {
    		nodeName: 14,
      },
      right: {
        nodeName: 15,
      }
    }
  }
}

思路

  1. 创建一个空对象，先确定二叉树的根节点
  2. 创建一个数组将根节点存进去
  3. 遍历这个数组，每次给遍历到的节点添加 left 和 right 节点
  4. 然后把 left 和 right 节点 push 到 nodes 这个数组里，继续遍历
  5. 最终的 BTree 就是需要的二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];
function arr2BTree() {
  const rootNode = {
    nodeName: arr[0]
  };
  const BTree = rootNode;
  // 按顺序存储所有的节点
  const treeNodes = [BTree];
  let index = 0;
  // 桉顺序遍历所有的节点
  for (const node of treeNodes) {
    index++;
    if (index > arr.length - 1) {
      break;
    }
    node.left = {
      nodeName: arr[index]
    };
    treeNodes.push(node.left);
    index++;
    if (index > arr.length - 1) {
      break;
    }
    node.right = {
      nodeName: arr[index]
    };
    treeNodes.push(node.right);
  }
  return BTree;
}
const BTree = arr2BTree();
console.log("BTree:", BTree);

将二叉树还原为数组(广度优先遍历)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function BTree2arr() {
  const arr = [];
  const treeNodes = [BTree];
  // 按照广度优先遍历
  // 1. 将树中所有的节点按照广度优先遍历，存到一个数组中
  // 2. 遍历数组，将所有的节点存下来
  for (const node of treeNodes) {
    arr.push(node.nodeName);
    if (node.left) {
      treeNodes.push(node.left);
    }
    if (node.right) {
      treeNodes.push(node.right);
    }
  }
  return arr;
}
const originArr = BTree2arr();
console.log("originArr:", originArr);