JavaScript和树（二叉树）

二叉树的概念：https://segmentfault.com/a/1190000000740261
java二叉树算法：http://www.cnblogs.com/-new/p/6730458.html

二叉树的遍历

二叉树的遍历(traversing binary tree)是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

二叉树的遍历有三种方式，如下：

（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树。简记根-左-右。

（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树。简记左-根-右。

（3）后序遍历（LRD），首先遍历左子树，然后遍历右子树，最后访问根结点。简记左-右-根。 

（4）层次遍历(广度优先遍历)：一层一层地遍历

树的结构

254733939-544b398b1bae2_articlex.jpg

模拟数据

 const tree = {
    value: 'A',
    left: {
      value: 'B',
      left: {
        value: 'D',
        left: {
          value: null
        },
        right: {
          value: null
        }
      },
      right: {
        value: 'E',
        left: {
          value: null
        },
        right: {
          value: null
        }
      }
    },
    right: {
      value: 'C',
      left: {
        value: 'F',
        left: {
          value: null
        },
        right: {
          value: null
        }
      },
      right: {
        value: 'G',
        left: {
          value: null
        },
        right: {
          value: null
        }
      }
    }
  }

  // 前序遍历（递归）
  function beforEach() {
    const list = []

    function recursive(tree) {
      if (tree.value) {
        list.push(tree.value)
        recursive(tree.left)
        recursive(tree.right)
      }

    }

    recursive(tree)
    return list
  }
  console.log(beforEach()) // ["A", "B", "D", "E", "C", "F", "G"]

  // 中序遍历（递归）
  function centerEach() {
    const list = []

    function recursive(tree) {
      if (tree.value) {
        recursive(tree.left)
        list.push(tree.value)
        recursive(tree.right)
      }

    }

    recursive(tree)
    return list
  }

  console.log(centerEach()) // ["D", "B", "E", "A", "F", "C", "G"]

  // 后序遍历（递归）
  function afterEach() {
    const list = []

    function recursive(tree) {
      if (tree.value) {
        recursive(tree.left)
        recursive(tree.right)
        list.push(tree.value)

      }

    }

    recursive(tree)
    return list
  }

  console.log(afterEach()) // ["D", "E", "B", "F", "G", "C", "A"]

层级遍历
  function levelOrderTraversal(tree) {
    var list = []
    var que = []
    que.push(tree)
    while (que.length !== 0) {
      var node = que.shift()
      if (node.value) list.push(node.value)  // 如果存在值，插入数组
      if (node.left) que.push(node.left)     // 如果存在对象，继续放入循环里面的数组
      if (node.right) que.push(node.right)  // 如果存在对象，继续放入循环里面的数组
    }
    return list

  }

  console.log(levelOrderTraversal(tree)) //["A", "B", "C", "D", "E", "F", "G"]

// 数组变成一个二叉树
  // 先把数组里面的变成想要的对象
  var ary = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
  var list = []
  for (var i = 0; i < ary.length; i++) {
    list.push({
      a: ary[i],
      left: null,
      right: null
    })
  }


  for (var i = 0; i < Math.floor(list.length / 2) - 1; i++) {       // i表示的是根节点的索引，从0开始
    if (list[2 * i + 1] !== null) {
      // 左结点
      list[i].left = list[2 * i + 1];
    }
    if (list[2 * i + 2] !== null) {
      // 右结点
      list[i].right = list[2 * i + 2];
    }
  }
  // 判断最后一个根结点：因为最后一个根结点可能没有右结点，所以单独拿出来处理
  var lastIndex = Math.floor(list.length / 2) - 1;
  // 左结点
  list[lastIndex].left = list[lastIndex * 2 + 1]
  // 右结点，如果数组的长度为奇数才有右结点
  if (list.length % 2 === 1) {
    list[lastIndex].right = list[lastIndex * 2 + 2];
  }