树是计算机科学中经常用到的一种数据结构。
树是一种非线性的数据结构，以分层的方式存储数据。
树被用来存储具有层级关系的数据，比如文件系统中的文件；页面的DOM结构；
树还被用来存储有序列表。

二叉树

二叉树是一种特殊的树结构，它表示子节点不超过2个。二叉树具有诸多优点。相对于链表来说，二叉树在进行查找时速度非常快，而相对于数组来说，为二叉树添加或删除元素也非常快。
二叉树的子树有左右之分，其次序不能任意颠倒。
在实现二叉树时，采用的存储结构为链式存储结构，链式结构的意思是采用一个链表来存储一颗二叉树，二叉树中每一个节点用链表的一个节点来存储，在二叉树中，节点结构至少有三个域：数据域data，左指针域left，右指针域right，如下图所示：
二叉树 - 图1

二叉树的Node节点结构

  1. class Node{
  2.     constructor(data, left, right){
  3.         this.data = data;
  4.         this.left = left;
  5.         this.right = right;
  6.         this.count = 1; // 比上图结构多了个属性，用于统计重复节点的数量
  7.     }
  8. }

二叉排序树

二叉排序树或者是一棵空树，或者是具有下列性质

  • 如果存在左子节点，则左子节点值小于根节点的值
  • 如果存在右子树，则右子树的所有节点大于根节点的值
  • 左右子树也是二叉排序树

  • 没有键值相等的节点

    代码框架

    1. class BSTree {
    2.   constructor() {
    3.       this.root = null;
    4.   }
    6.   // 删除一个节点
    7.   _removeNode(node, data) {}
    9.   // 删除给定的数据节点
    10.   remove(data) {
    11.       this.root = this._removeNode(this.root, data);
    12.   }
    14.   // 向二叉树中插入节点
    15.   insert(data) {}
    17.   // 寻找给定数据的节点
    18.   find(data) {}
    20.   // 获得最小值的节点
    21.   getMinNode(node = this.root) {   }
    23.   // 获得最大值的节点
    24.   getMaxNode(node = this.root) {    }
    25. }

    二叉树排序树基本操作

    插入节点

    插入操作可以分为两步：1.新建node节点。 2.找出合适位置插入
    以data为值创建node节点

    1. let newNode = new Node(data, null, null);

    接下来进行插入操作。使用parentNode记录当前节点的父节点，初始值为null。当前节点为currNode，初始时为该二叉树的根节点。

  • 插入时，root为null，直接将currNode赋值给root即可。

  • 如果newNode的值小于currNode的值，将newNode插入到currNode的左子树上。否则，插入到右子树上。
  • 更新当前节点currNode所指的节点，直到当前节点不存在，说明找到了插入的位置。
    1. insert(data) {
    2. let newNode = new Node(data, null, null);
    3. if (!this.root) {
    4.   // 不存在根节点时，将新节点设置为根节点
    5.   this.root = newNode;
    6. } else {
    7.   let currNode = this.root;
    8.   let parentNode = null;
    9.   while (true) {
    10.     // 做为暂时保存变量
    11.     parentNode = currNode;
    12.     // 插入的值，小于父节点的值，插入到左侧
    13.     if (newNode.data < currNode.data) {
    14.       // 更新currNode为左侧的子节点
    15.       currNode = currNode.left;
    16.       // 一直查找直到没有左节点时，将新节点newNode设置为parentNode的左节点
    17.       if (!currNode) {
    18.         parentNode.left = newNode;
    19.         break;
    20.       }
    21.     } else if (newNode.data > currNode.data) {
    22.       currNode = currNode.right;
    23.       if (!currNode) {
    24.         parentNode.right = newNode;
    25.         break;
    26.       }
    27.     } else if (newNode.data == currNode.data) {
    28.       this.count++;
    29.       break;
    30.     }
    31.   }
    32. }
    33. }

    获取最值

    获取最小值

    不断搜索排序二叉树的左子节点，直到左节点不存在，说明当前的节点就是最小节点
    1. getMinNode(node = this.root) {
    2. let curNode = node;
    3. while (curNode.left) {
    4.   curNode = curNode.left;
    5. }
    6. return curNode;
    7. }

    获取最大值

    不断搜索排序二叉树的右子节点，直到右节点不存在，说明当前的节点就是最大节点
    1. getMaxNode(node = this.root) {
    2. let curNode = node;
    3. while (curNode.right) {
    4.   curNode = curNode.right;
    5. }
    6. return curNode;
    7. }

    查询节点

    二叉树排序树中寻找给定的数据
    1. find(data) {
    2. let currNode = this.root;
    3. // 从根开始查找
    4. while (currNode) {
    5.   if ((currNode.data = data)) {
    6.     return currNode;
    7.   } else if (currNode.data > data) {
    8.     currNode = currNode.left;
    9.   } else if (currNode.data < data) {
    10.     currNode = currNode.right;
    11.   }
    12. }
    13. return null;
    14. }

    移除节点

    删除节点：分为三种情况
  1. 待删除的节点是叶子节点。直接将节点删除。
  2. 待删除的节点有子节点，没有左子节点，或者没有右子节点。
    1. 待删除的节点没有左子节点时，返回该节点的右孩子节点，并删除该节点
    2. 待删除的节点没有右子节点时，返回该节点的左孩子节点，并删除该节点
  3. 待删除的节点的左右子节点均存在。
    1. 或者查找待删除节点左子树上的最大值
    2. 或者查找待删除节点右子树上的最小值

代码使用：查找其右子树上的最小值的方法。在找到待删除节点的右子树上的最小值后，创建临时节点，将临时节点上的值复制到待删除节点，然后再删除临时节点。

  1. _removeNode(node, data) {
  2.   // 根节点都为空，不能删除任何值
  3.   if (node === null) {
  4.     return null;
  5.   }
  6.   // 删除的节点是根节点
  7.   if (data === node.data) {
  8.     // {1}:删除的是叶子节点，没有子节点
  9.     // 当待删除的节点时叶子节点时, 直接将待删除的节点置空返回
  10.     if (node.left === null && node.right === null) {
  11.       return null;
  12.     }
  13.     // 当待删除的节点没有左子节点时，返回该节点的右孩子节点,并删除该节点
  14.     if (node.left === null) {
  15.       return node.right;
  16.     }
  17.     if (node.right === null) {
  18.       return node.left;
  19.     }
  20.     /* 最后一种情况
  21.       待删除的节点的左右子节点均存在,有两种做法：
  22.       要么查找待删除节点左子树上的最大值，要么查找其右子树上的最小值
  23.       */
  24.     // 查找右节点的最小值
  25.     let tempNode = this.getMinNode(node.right);
  26.     node.data = tempNode.data; //右子树的最小值，替换要删除的值
  27.     node.right = this._removeNode(node.right, tempNode.data);
  28.     return node;
  29.   }
  30.   // 删除的节点在左节点
  31.   else if (data < node.data) {
  32.     node.left = this._removeNode(node.left, data);
  33.     return node;
  34.   } else {
  35.     node.right = this._removeNode(node.right, data);
  36.     return node;
  37.   }
  38. }
  39. remove(data) {
  40.   this._removeNode(this.root, data);
  41. }

测试代码

  1. let myTree = new BSTree();
  3. myTree.insert(20);
  4. myTree.insert(13);
  5. myTree.insert(7);
  6. myTree.insert(9);
  7. myTree.insert(15);
  8. myTree.insert(14);
  9. myTree.insert(42);
  10. myTree.insert(22);
  11. myTree.insert(21);
  12. myTree.insert(24);
  13. myTree.insert(57);
  15. console.log(myTree.getMaxNode());//Node { data: 57, left: null, right: null, count: 1 }
  16. console.log(myTree.getMinNode()); //Node { data: 7, left: null, right: Node { data: 9, left: null, right: null, count: 1 },count: 1}
  17. myTree.remove(7);
  18. console.log(myTree.getMinNode()); //Node { data: 9, left: null, right: null, count: 1 }

二叉树 - 图2

二叉树排序树遍历操作

二叉树的遍历操作可以使用递归来完成。递归遍历会非常简单。
递归的方法往往表现的非常简洁，但是理解起来需要费一番功夫，所以本篇对二叉树的遍历还提供了非递归的方法。应当要注意的是，遍历操作适合所有的二叉树，而不仅仅是上一篇中实现的二叉排序树。

  1. class BSTree {
  2.     constructor() {
  3.         this.root = null;
  4.     }
  6.     // 中序递归遍历
  7.     inOrderRec(node = this.root) {}
  9.     // 中序非递归遍历
  10.     inOrderNonRec(node = this.root){}
  12.     // 前序递归遍历
  13.     preOrderRec(node = this.root) {}
  15.     // 前序遍历非递归方法
  16.     preOrderNonRec(node = this.root) {}
  18.     // 后序遍历递归方法
  19.     postOrderRec(node = this.root) {}
  21.     // 后序遍历非递归的方法
  22.     postOrderNonRec(node = this.root) {}
  24.     // 层次遍历
  25.     levelOrder(node = this.root) {}
  27.     // 知道二叉树的先序和中序排列，重建二叉树
  28.     preInCreate(preArr, inArr, pBeg, pEnd, iBeg, iEnd) {}
  29. }

层序遍历

首先实现最重要的一个变量方法，二叉树的很多操作都依赖该遍历实现。如：统计二叉树中叶子节点个数；获取二叉树的宽度；判断两颗二叉树是否相等；求二叉树的深度；
二叉树的层次遍历，即按照箭头所指的方向，按照20、13、42、7、15、22、57、9、14、21、24的层次顺序，对二叉树的各个节点进行访问
二叉树 - 图3
首先将二叉树的根节点入队列，然后出队，访问该节点，如果它的左子树不空，则将左子树的根节点入队。如果它的右子树不为空，则将右子树的根节点入队。然后出队，对出队节点进行访问，如此反复，直到队列为空。

  1. levelOrder(node = this.root) {
  2.     //   进行层次遍历，需要借助队列
  3.     // 首先将二叉树的根节点入队列，然后出队，访问该节点，如果它的左子树不空，则将左子树的根节点入队。如果它的右子树不为空，则将右子树的根节点入队。
  4.     let queue = [];
  5.     let result = "";
  6.     // 根节点入队列
  7.     queue.push(node);
  8.     while (queue.length > 0) {
  9.       // 获取队列的开头
  10.       node = queue.shift();
  11.       // 记录二叉树节点的值
  12.       result += `->${node.data} `;
  13.       if (node.left) {
  14.         // 左子节点入队
  15.         queue.push(node.left);
  16.       }
  17.       if (node.right) {
  18.         // 右子节点入队
  19.         queue.push(node.right);
  20.       }
  21.     }
  22.     return result.substring(2);
  23.   }

测试

  1. let myTree = new BSTree();
  3. myTree.insert(20);
  4. myTree.insert(13);
  5. myTree.insert(7);
  6. myTree.insert(9);
  7. myTree.insert(15);
  8. myTree.insert(14);
  9. myTree.insert(42);
  10. myTree.insert(22);
  11. myTree.insert(21);
  12. myTree.insert(24);
  13. myTree.insert(57);
  15. console.log(myTree.levelOrder());  // 20 13 42 7 15 22 57 9 14 21 24

前序遍历

遍历顺序：

  1. 访问根节点。
  2. 前序遍历左子树。
  3. 前序遍历右子树。

    前序递归法

    1. // 前序递归遍历, 1:访问根节点。2:前序遍历左子树。3:前序遍历右子树。
    2. preOrderRec(node = this.root) {
    3. // 先根，后左，再右
    4. let result = "";
    5. if (node !== null) {
    6.  // 先显示根
    7.  result += node === this.root ? `${node.data}` : `->${node.data}`;
    8.  // 显示左子树
    9.  result += this.preOrderRec(node.left);
    10.  // 显示右子树
    11.  result += this.preOrderRec(node.right);
    12. }
    13. return result;
    14. }

    前序非递归法

    非递归的遍历时，需要借助一个栈。stack
    首先访问根节点，然后将其入栈，如果此节点的左子树不为空，则再次访问此节点左子树的根节点，然后将其入栈……直到节点的左子树为空时，从堆栈中弹出一个节点，再按照相同的方法访问出栈节点的右子树。
    1. preOrderNonRec(node = this.root) {
    2. //非递归的遍历时，算法需要借助一个栈
    3. let stack = [];
    4. let result = "";
    5. // 当节点存在或者栈不空时
    6. while (node || stack.length > 0) {
    7.  if (node) {
    8.    // 访问根节点
    9.    result += `->${node.data} `;
    10.    // 根节点入栈
    11.    stack.push(node);
    12.    // 根之后先遍历左子树
    13.    node = node.left;
    14.  } else {
    15.    // 从栈中取出根节点
    16.    node = stack.pop();
    17.    // 遍历根节点的右子树
    18.    node = node.right;
    19.  }
    20. }
    21. return result;
    22. }
    非递归算法的效率要高于递归算法。

    中序遍历

    中序遍历，先左再根后右。

    中序递归法

    1. inOrderRec(node = this.root) {
    2. // 先左，后根，再右
    3. let result = "";
    4. if (node !== null) {
    5.  result += this.inOrderRec(node.left);
    6.  result += `->${node.data}`;
    7.  result += this.inOrderRec(node.right);
    8. }
    9. return result;
    10. }

中序非递归法

非递归遍历需要借助栈数据结构实现。
首先访问根节点 的所有左子节点，并将它们依次进栈，然后出栈顶层节点【左子节点】，打印该节点【左子节点或者暂时的根】。然后扫描该节点的右子节点，将其进栈，再扫描该右子节点的所有左节点并依次进栈，如此反复，直到栈为空时结束。

  1. inOrderNonRec(node = this.root) {
  2.   // 非递归遍历借助栈结构
  3.   let stack = [];
  4.   let result = "";
  5.   while (node || stack.length) {
  6.     if (node) {
  7.       // 节点存在，先将节点入栈
  8.       stack.push(node);
  9.       // 如果node存在，使用节点的左子节点 更新节点，然后继续入栈
  10.       node = node.left;
  11.     } else {
  12.       // 左子节点不存在了。执行出栈，后进先出
  13.       node = stack.pop();
  14.       result += `->${node.data} `;
  15.       // 使用节点的右子节点 更新节点，然后入栈
  16.       node = node.right;
  17.     }
  18.   }
  19.   return result;
  20. }

测试

  1. console.log(myTree.inOrderRec());  // 7 9 13 14 15 20 21 22 24 42 57 
  3. console.log(myTree.inOrderNonRec());  // 7 9 13 14 15 20 21 22 24 42 57

后序遍历

后序遍历：先左，再右，最后根

后续递归法

把打印操作放到最后

  1. postOrderRec(node = this.root) {
  2.   // 先左，后右，再根
  3.   let result = "";
  4.   if (node !== null) {
  5.     result += this.postOrderRec(node.left);
  6.     result += this.postOrderRec(node.right);
  7.     result += `->${node.data}`;
  8.   }
  9.   return result;
  10. }

后序非递归法

后序遍历的非递归算法比较复杂。
非递归遍历二叉树的顺序是 先访问左子树， 再访问右子树， 最后访问根节点。
用栈来存储节点，必须分清楚返回根节点时，是从左子树返回的，还是从右子树返回的。所以变量指针ret，其指向最近访问过的节点。

  1. postOrderNonRec(node = this.root) {
  2.   // 左右根
  3.   let stack = [];
  4.   let ret = node;
  5.   let result = "";
  6.   while (node || stack.length) {
  7.     // 第一步现将根节点以及左节点依次入栈
  8.     if (node) {
  9.       // 根节点存在，将节点入栈
  10.       stack.push(node);
  11.       // 更新node节点，为左子节点，存在的话继续入栈，不存在就走else操作
  12.       node = node.left;
  13.     } else {
  14.       // 获取栈顶节点，首次获取的值为7节点
  15.       node = stack[stack.length - 1];
  16.       // 如果node有右节点且未访问过
  17.       if (node.right && node.right != ret) { 
  18.         // node.right != ret说明是从左子节点返回的根，不同才进入右子节点入栈操作，
  19.         // 如果相同，已经处理过，说明是右子节点返回到的根，就不能进入，否则会死循环
  20.         node = node.right;
  21.         // 将右节点入栈
  22.         stack.push(node);
  23.         node = node.left; // 再次查找此时右节点上是否有左节点
  24.       } else {
  25.         // 首先会进入这里开始遍历左子节点
  26.         // 取出栈结构中的节点
  27.         node = stack.pop();
  28.         result += `->${node.data} `;
  29.         // 记录下节点，防止进入无限循环
  30.         ret = node;
  31.         node = null;
  32.       }
  33.     }
  34.   }
  35.   return result;
  36. }

测试

  1. console.log(myTree.postOrderRec());  // 9 7 14 15 13 21 24 22 57 42 20 
  3. console.log(myTree.postOrderNonRec());  // 9 7 14 15 13 21 24 22 57 42 20

重建一颗二叉树

给出前序和中序的值，求出整个树的结构？重建出该二叉树
分析思路：

  1. 前序遍历中，第一个值一定是树的根。
  2. 中序遍历中，根节点一定在树的左子树和右子树中间，通过第一步找到的根，将中序的值可以划分三份，左子树，根，右子树。同时计算出左子树和右子树的个数
  3. 用第二步的左右子节点个数，对前序遍历的值进行分割，划分成左右子树。
  4. 通过节点数量对前序遍历分割处理的左右子树，它们【前序分割出的左右子树】第一节点还是根节点。
  5. 用根节点的值重复执行第一步。

如此递归地进行下去，便能唯一地确定这棵二叉树
二叉树 - 图4

  1. /**
  2.  * @param {Array} preArr 先序序列
  3.  * @param {Array} midArr 中序序列
  4.  * @param {Number} pBeg 先序序列的第一个下标
  5.  * @param {Number} pEnd 先序序列的最后一个下标
  6.  * @param {Number} mBeg 中序序列的第一个下标
  7.  * @param {Number} mEnd 中序序列的最后一个下标
  8.  */
  9. preInCreate(preArr, midArr, pBeg, pEnd, mBeg, mEnd) {
  10.   let lLen = 0,
  11.     rLen = 0;
  12.   let splitIdx = -1;
  13.   // 建立根节点，先序的开头就是根
  14.   let node = new Node(preArr[pBeg], null, null);
  15.   if (!this.root) {
  16.     this.root = node;
  17.   }
  18.   // 利用根节点即【20】 在中序序列中进行划分
  19.   // 先序序列 20 ->13 ->7 ->9 ->15 ->14 ->42 ->22 ->21 ->24 ->57
  20.   // 中序序列 7 ->9 ->13 ->14 ->15 ->20 ->21 ->22 ->24 ->42 ->57
  21.   for (let i = mBeg; i <= mEnd; i++) {
  22.     // 用先序的根【20】，在中序列查找，查出索引位置，即20所处的位置
  23.     if (midArr[i] == preArr[pBeg]) {
  24.       splitIdx = i;
  25.       break;
  26.     }
  27.   }
  28.   // 根据20所处的索引位置，求出左右子树的长度
  29.   if (splitIdx > -1) {
  30.     lLen = splitIdx - mBeg; // 左子树的长度 5， 【7 ->9 ->13 ->14 ->15】
  31.     rLen = mEnd - splitIdx; // 右子树的长度 5， 【21 ->22 ->24 ->42 ->57】
  32.   }
  34.   // 递归建立左子树
  35.   if (lLen) {
  36.     node.left = this.preInCreate(
  37.       preArr,
  38.       midArr,
  39.       pBeg + 1,
  40.       pBeg + lLen,
  41.       mBeg,
  42.       mBeg + lLen - 1
  43.     );
  44.   } else {
  45.     node.left = null;
  46.   }
  48.   // 递归建立右子树
  49.   if (rLen) {
  50.     node.right = this.preInCreate(
  51.       preArr,
  52.       midArr,
  53.       pEnd - rLen + 1,
  54.       pEnd,
  55.       mEnd - rLen + 1,
  56.       mEnd
  57.     );
  58.   } else {
  59.     node.right = null;
  60.   }
  62.   return node;
  63. }

测试

  1. // 前序序列为：20, 13, 7, 9, 15, 14, 42, 22, 21, 24, 57
  2. // 中序序列为：7, 9, 13, 14, 15, 20, 21, 22, 24, 42, 57
  3. let preOrder = [20, 13, 7, 9, 15, 14, 42, 22, 21, 24, 57];
  4. let inOrder = [7, 9, 13, 14, 15, 20, 21, 22, 24, 42, 57];
  5. let inLstIdx = inOrder.length - 1;
  6. let preLstIdx = preOrder.length - 1;
  8. let myTree = new BSTree();
  10. myTree.preInCreate(preOrder, inOrder, 0, preLstIdx, 0, inLstIdx);
  11. console.log(myTree.inOrderNonRec());  // 7 9 13 14 15 20 21 22 24 42 57
  12. console.log(myTree.preOrderNonRec());  //  20 13 7 9 15 14 42 22 21 24 57 
  13. console.log(myTree.postOrderNonRec());  //  9 7 14 15 13 21 24 22 57 42 20

二叉树排序树其他常用操作

获取节点个数

  1. //非递归计算节点操作，使用层序遍历的队列计数，只要在每次节点出队的时候计数 +1
  2. getNodeNumber(node = this.root) {
  3.   let count = 0;
  4.   if (node) {
  5.     let queue = [];
  6.     queue.push(node); // 根节点入队列
  7.     while (queue.length) {
  8.       node = queue.shift();
  9.       count++;  // 只要一个节点出队，计数就+1
  10.       if (node.left) {
  11.         queue.push(node.left);
  12.       }
  13.       if (node.right) {
  14.         queue.push(node.right);
  15.       }
  16.     }
  17.     return count;
  18.   }
  19. }
  1. getNodeNumber2(node = this.root) {
  2.   let count = 0;
  3.   if (node) {
  4.     count++;
  5.     count += this.getNodeNumber2(node.left);
  6.     count += this.getNodeNumber2(node.right);
  7.   }
  8.   return count;
  9. }
  10. console.log(myTree.getNodeNumber());
  11. myTree.remove(42);
  12. console.log(myTree.getNodeNumber2());

获取叶子节点个数

统计叶子节点的个数也使用层序遍历。
统计叶子节点个数：只统计出队列的节点同时没有左右子树时，计数才+1；

  1. // 非递归操作
  2. getLeafNodeNumber(node = this.root) {
  3.   let count = 0;
  4.   let queue = [];
  5.   queue.push(node);
  6.   while (queue.length) {
  7.     node = queue.pop();
  8.     if (node.left) {
  9.       queue.push(node.left);
  10.     }
  11.     if (node.right) {
  12.       queue.push(node.right);
  13.     }
  14.     if (!node.left && !node.right) {
  15.       count++;
  16.     }
  17.   }
  18.   return count;
  19. }
  21. //递归操作
  22. getLeafNodeNumber2(node = this.root) {
  23.   // 每次递归的结束条件
  24.   if (!node) {
  25.     return 0;
  26.   }
  27.   if (!node.left && !node.right) {
  28.     return 1;
  29.   }
  31.   let leftNum = this.getLeafNodeNumber2(node.left);
  32.   let rightNum = this.getLeafNodeNumber2(node.right);
  34.   return leftNum + rightNum;
  35. }

测试

  1. console.log(myTree.getLeafNodeNumber());  // 5
  2. myTree.remove(57);
  3. console.log(myTree.getLeafNodeNumber());  // 4

获取二叉树深度

二叉树的深度指的是从根节点到叶子节点中最长路径的长度为树的深度。
使用递归的方法实现

  1. 一颗树只有一个节点，它的深度是1；
  2. 二叉树的根节点只有左子树而没有右子树，二叉树的深度应该是其左子树的深度加1；
  3. 二叉树的根节点只有右子树而没有左子树，二叉树的深度应该是其右子树的深度加1；
  4. 二叉树的根节点既有右子树又有左子树，那么二叉树的深度应该是其左右子树的深度较大值加1。
    1. getTreeDepth(node = this.root) {
    2. let depth = 0;
    3. if (node) {
    4.  depth++;
    5.  if (node.left && !node.right) {
    6.    depth = this.getTreeDepth(node.left) + 1;
    7.  }
    8.  if (node.right && !node.left) {
    9.    depth = this.getTreeDepth(node.right) + 1;
    10.  }
    11.  if (node.left && node.right) {
    12.    depth =
    13.      this.getTreeDepth(node.left) > this.getTreeDepth(node.right)
    14.        ? this.getTreeDepth(node.left) + 1
    15.        : this.getTreeDepth(node.right) + 1;
    16.  }
    17. }
    18. return depth;
    19. }

    测试

    1. console.log(myTree.getTreeDepth());  // 4
    2. myTree.remove(9);
    3. myTree.remove(14);
    4. myTree.remove(21);
    5. myTree.remove(24);
    6. console.log(myTree.getTreeDepth());  // 3

    计算指定层的节点数

    使用层次遍历，使用一个变量来保存当前层数节点的个数，用这个变量作为内层循环结束的标识，当内层循环结束时，队列中保存的就是下一层的节点，这时判断是否等于给定层数，如果相等直接返回，不相等再进行下一轮循环
    1. // 计算指定层数节点的个数
    2. //   使用一个变量来保存当前层数节点的个数，用这个变量作为内层循环结束的标识
    3. getLevelNodeNumber(level, node = this.root) {
    4. if (node) {
    5.  // depth保存查找的层级
    6.  let depth = 1;
    7.  let queue = [];
    8.  queue.push(node);
    9.  if (depth === level) {
    10.    return queue.length;
    11.  }
    12.  while (true) {
    13.    //使用size保存当前层级节点的个数
    14.    let size = queue.length;
    15.    if (size === 0) {
    16.      return;
    17.    }
    18.    // size有值，说明还是在当前层级
    19.    while (size) {
    20.      node = queue.shift();
    21.      if (node.left) {
    22.        queue.push(node.left);
    23.      }
    24.      if (node.right) {
    25.        queue.push(node.right);
    26.      }
    27.      size--;
    28.    }
    29.    depth++;
    30.    if (depth === level) return queue.length;
    31.  }
    32. }
    33. }

    测试

    1. console.log(myTree.getLevelNodeNumber(1));  // 1
    2. console.log(myTree.getLevelNodeNumber(2));  // 2
    3. console.log(myTree.getLevelNodeNumber(3));  // 4
    4. console.log(myTree.getLevelNodeNumber(4));  // 4

    判断是不是完全二叉树

    完全二叉树的定义

    若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

完全二叉树指的是除了最后一层可能不是满的，其他层都是满的二叉树

算法1

如果层次遍历时遇到一个空节点后，再向后的遍历的时候依然还有节点，则这个二叉树肯定不是完全二叉树。

  1. //采用层序遍历，如果遇到一个空节点，则后边的节点都是空节点才是完全二叉树，否则就不是完全二叉树
  2. isCompleteTree1(node = this.root) {
  3.   let queue = [];
  4.   let flag = false;
  5.   queue.push(node);
  6.   while (queue.length) {
  7.     node = queue.shift();
  8.     // 如果节点存在
  9.     if (node) {
  10.       if (flag) {
  11.         return false;
  12.       }
  13.       queue.push(node.left);
  14.       queue.push(node.right);
  15.     } else {
  16.       // 节点不存在，说明出现了空节点，空节点就设置flag为true，如果后边没有任何节点，则为完全二叉树
  17.       // 如果后边还有节点，再次进入到if(node)中，则是非完全二叉树
  18.       flag = true;
  19.     }
  20.   }
  21.   return true;
  22. }

算法2

  1. 如果一个节点只有右子节点，则不是完全二叉树。
  2. 当遍历到一个不是叶子节点的节点【说明该节点存在子节点】时，如果其前面的节点没有右孩子节点【前面节点有空的节点】，则不是完全二叉树。
    1. isCompleteTree2(node = this.root) {
    2. let queue = [];
    3. let noRight = false;
    4. queue.push(node);
    5. while (queue.length) {
    6.  node = queue.shift();
    7.  // 对应注释《1》
    8.  if (!node.left && node.right) {
    9.    return false;
    10.  }
    11.  //遇到一个非叶子节点 且其前面的节点没有右孩子节点
    12.  if ((node.left || node.right) && noRight) {
    13.    return false;
    14.  }
    15.  if (node.left) {
    16.    queue.push(node.left);
    17.  }
    18.  if (node.right) {
    19.    queue.push(node.right);
    20.  } else {
    21.    // 没右子节点，但是后续的节点还是有子节点的枪口
    22.    noRight = true;
    23.  }
    24. }
    25. return true;
    26. }

二叉树镜像

二叉树 - 图5
将左右子树交换

  1. invertTree(node = this.root) {
  2.   if (!node) {
  3.     return;
  4.   }
  5.   // 建立一个临时存放节点的变量
  6.   let tempNode = node.left;
  7.   node.left = node.right;
  8.   node.right = tempNode;
  10.   this.invertTree(node.left);
  11.   this.invertTree(node.right);
  12. }

完整代码