初探二叉树

[mamba-1024]

二叉树作为一种很基础但是又很重要的数据结构，在某些场景下还是比较重要的。所以掌握二叉树的重要性就不言而喻了。

二叉树

二叉树是由根节点，左子树，右子树组成，左子树和友子树分别是一个二叉树

举个栗子：

var binaryTree = {
  value: 1,
  left: {
    value: 2,
    left: {
      value: 4
    }
  },
  right: {
    value: 3,
    left: {
      value: 5,
      left: {
        value: 7
      },
      right: {
        value: 8
      }
    },
    right: {
      value: 6
    }
  }
}

遍历二叉树

递归遍历

1. 先序遍历：访问根–>遍历左子树–>遍历右子树;

   var preListRec = []; //定义保存先序遍历结果的数组
   var preOrderRec = function(node) {
   if (node) { //判断二叉树是否为空
       preListRec.push(node.value); //将结点的值存入数组中
       preOrderRec(node.left); //递归遍历左子树
       preOrderRec(node.right); //递归遍历右子树
   }
   }
   preOrderRec(tree);
   console.log(preListRec)

2. 中序遍历：遍历左子树–>访问根–>遍历右子树;

   var inListRec = []; //定义保存中序遍历结果的数组
   var inOrderRec = function(node) {
   if (node) { //判断二叉树是否为空
       inOrderRec(node.left); //递归遍历左子树
       inListRec.push(node.value); //将结点的值存入数组中
       inOrderRec(node.right); //递归遍历右子树
   }
   }
   inOrderRec(tree);
   console.log(inListRec);

3. 后序遍历：遍历左子树–>遍历右子树–>访问根;

   var postListRec = []; //定义保存后序遍历结果的数组
   var postOrderRec = function(node) {
   if (node) { //判断二叉树是否为空
       postOrderRec(node.left); //递归遍历左子树
       postOrderRec(node.right); //递归遍历右子树
       postListRec.push(node.value); //将结点的值存入数组中
   }
   }
   postOrderRec(tree);
   console.log(postListRec);

非递归遍历

1. 广度优先遍历

广度优先遍历是从二叉树的第一层（根结点）开始，自上至下逐层遍历；在同一层中，按照从左到右的顺序对结点逐一访问

实现原理：

使用数组模拟队列，首先将根结点归入队列。当队列不为空时，执行循环：取出队列的一个结点，如果该节点有左子树，则将该节点的左子树存入队列；如果该节点有右子树，则将该节点的右子树存入队列

var breadthList = []; // 定义保存广度遍历结果的数组
var breadthTraversal = function(node) {
    if (node) { // 判断二叉树是否为空
        var que = [node]; // 将二叉树放入队列 var que = []; que.push(node);
        while (que.length !== 0) { // 判断队列是否为空
            node = que.shift(); // 从队列中取出一个结点
            breadthList.push(node.value); // 将取出结点的值保存到数组
            if (node.left) que.push(node.left); // 如果存在左子树，将左子树放入队列
            if (node.right) que.push(node.right); // 如果存在右子树，将右子树放入队列
        }
    }
}
breadthTraversal(tree);
console.log(breadthList);