Category: algorithm

库存列表：skuList，规格列表：skuNameList，属性：skuNameList-skuValues数组下的单个元素，规格：skuNameList下的单个元素

// 库存列表
const skuList = [
  {
    skuId: '0',
    skuGroup: ['红色', '大'],
    remainStock: 7,
    price: 2,
    picUrl: 'https://dummyimage.com/100x100/ff00b4/ffffff&text=大'
  },
  {
    skuId: '1',
    skuGroup: ['红色', '小'],
    remainStock: 3,
    price: 4,
    picUrl: 'https://dummyimage.com/100x100/ff00b4/ffffff&text=小'
  },
  {
    skuId: '2',
    skuGroup: ['蓝色', '大'],
    remainStock: 0,
    price: 0.01,
    picUrl: 'https://dummyimage.com/100x100/0084ff/ffffff&text=大'
  },
  {
    skuId: '3',
    skuGroup: ['蓝色', '小'],
    remainStock: 1,
    price: 1,
    picUrl: 'https://dummyimage.com/100x100/0084ff/ffffff&text=小'
  }
];

// 规格列表
const skuNameList = [
  {
    skuName: "颜色",
    skuValues: ["红色", "蓝色"]
  },
  {
    skuName: "尺寸",
    skuValues: ["大", "小"]
  }
];

将规格列表下的已选属性集合作为入参 selected，如果在当前规格未选择相关属性则传入空字符串，即最开始时 selected === [”, ”]

/**
 * 获取sku信息
 * @param {Array} selected 已选属性数组
 * @return {Object} skuInfo
 */
function getSkuinfo (selected){
  // 用以记录每个按钮状态的，例如 itemState['红色'] = true 表示高亮
  const attrState = {};
  let picUrl = '';
  let minPrice = Number.MAX_VALUE;
  let maxPrice = 0;
  let remainStock = 0;

  // in array not in others 
  const difference = (array, others) => {
    return array.filter((item) => others.indexOf(item) === -1);
  };
  // every in array in others return true or false
  const isSubset = (array, others) => {
    return array.every((item) => others.indexOf(item) > -1);
  };
  
  skuNameList.foreach(spec => {
    //selected 中有 在 spec.skuValues 里的先删除
    var temp = difference(selected, spec.skuValues)
    
    skuValues.foreach(name => { // 遍历规格 
      // 再加上 这一行的一个规格， 其他行已选和本行规格的组合就出来了
      // 如果组合属于 库存中某个skuGroup的子集 说明这个 规格可选
      var combinedTemp = [...temp, name]; 
      attrState[name] = false; // 先设为false
      for(var i = 0; i < skuList.length; i++){
         var skuGroup = skuList[i].skuGroup
         if(isSubset(combinedTemp, skuGroup)&& skuList[i].remainStock) 
         { 
            attrState[name] = true; 
            break;  //  如果其中有一个库存， 这个属性就可以选，然后退出循环 
         }
      }
    })
  })

  // 实际已选属性，过滤空字符串
  const realSelected = selected.filter((item) => item);
  const defaultSelected = selected.map(
    (name, idx) => name || skuNameList[idx].skuValues[0]
  );
  
  skuList.forEach(sku => {
    if(isSubset(selected,sku.skuGroup)){
     remainStock += sku.remainStock;
      minPrice = Math.min(minPrice, sku.price);
      maxPrice = Math.max(maxPrice, sku.price);
     // 取当前图片
      if (isSubset(defaultSelected, sku.skuGroup)) {
        picUrl = sku.picUrl;
      }
    }
  })


  return {
    attrState,
    picUrl,
    minPrice,
    maxPrice,
    remainStock,
  };
}

从dom节点的遍历来理解这个问题

/*深度优先遍历三种方式*/
let deepTraversal1 = (node, nodeList = []) => {
  if (node !== null) {
    nodeList.push(node)
    let children = node.children
    for (let i = 0; i < children.length; i++) {
      deepTraversal1(children[i], nodeList)
    }
  }
  return nodeList
}
[1,1-1,1-1-1, 1-1-2, 1-2, 1-2-1]

let deepTraversal2 = (node) => {
    let nodes = []
    if (node !== null) {
      nodes.push(node)
      let children = node.children
      for (let i = 0; i < children.length; i++) {
        nodes = nodes.concat(deepTraversal2(children[i]))
      }
    }
    return nodes
  }
// 非递归
let deepTraversal3 = (node) => {
  let stack = []
  let nodes = []
  if (node) {
    // 推入当前处理的node
    stack.push(node)
    while (stack.length) {
      let item = stack.pop()
      let children = item.children
      nodes.push(item)
      // node = [] stack = [parent]
      // node = [parent] stack = [child3,child2,child1]
      // node = [parent, child1] stack = [child3,child2,child1- 
          2,child1-1]
      // node = [parent, child1-1] stack = [child3,child2,child1-2]
      for (let i = children.length - 1; i >= 0; i--) {
        stack.push(children[i])
      }
    }
  }
  return nodes
}

// A B D G H I C E J F 深度遍历

广度优先遍历

let widthTraversal2 = (node) => {
  let nodes = []
  let stack = []
  if (node) {
    stack.push(node)
    while (stack.length) {
      let item = stack.shift()
      let children = item.children
      nodes.push(item)
        // 队列，先进先出
        // nodes = [] stack = [parent]
        // nodes = [parent] stack = [child1,child2,child3]
        // nodes = [parent, child1] stack = [child2,child3,child1- 
          1,child1-2]
        // nodes = [parent,child1,child2]
      for (let i = 0; i < children.length; i++) {
        stack.push(children[i])
      }
    }
  }
  return nodes
}

对于母串X=x1,x2,⋯,xm , Y=y1,y2,⋯,yn，求LCS与最长公共子串。

暴力解法

假设 m<n， 对于母串X，我们可以暴力找出2的m次方个子序列，然后依次在母串Y中匹配，算法的时间复杂度会达到指数级O(n∗2的m次)。显然，暴力求解不太适用于此类问题。

动态规划

假设Z=z1,z2,⋯, zk是X与Y的LCS， 我们观察到

如果Xm=Yn，则Zk=Xm=Yn，有Zk−1是Xm−1与Yn−1的LCS；
如果Xm≠Yn，则Zk是Xm与Yn−1的LCS，或者是Xm−1与Yn的LCS。

所以如果用一个二维数组c表示字符串X和Y中对应的前 i，前 j个字符的LCS的长度话，可以得到以下公式：

DP求解LCS

因此，我们只需要从c[0][0]开始填表，填到c[m-1][n-1]，所得到的c[m-1][n-1]就是LCS的长度

用二维数组c[i][j] 记录串x1x2⋯xi与y1y2⋯yj的LCS长度，则可得到状态转移方程

例如，设所给的两个序列为X=”A，B，C，B，D，A，B”和Y=”B，D，C，A，B，A”。由算法LCS_LENGTH和LCS计算出的结果如下图所示：

如上图 ，两层循环 ， 先循环 X ， 里层循环 Y， 遇到相等那子序长度就会加1，那前一个子序长度是 c[i -1][j-1], 如果比较不想等, 子序长度就不增加， 当前子序长度 就是c[i-1][j] 或c[i][j-1] 其中大的值. 如上图不相等时，当前的数子会取 上边或左边 最大数子。 遍历完就能得到 子序长度 c[6][7]

若想得到LCS，则再遍历一次b数组就好了，从最后一个位置开始往前遍历：

• 如果箭头是↖，则代表这个字符是LCS的一员，存下来后 i– , j–
• 如果箭头是←，则代表这个字符不是LCS的一员，j–
• 如果箭头是↑ ，也代表这个字符不是LCS的一员，i–
• 如此直到i = 0或者j = 0时停止，最后存下来的字符就是所有的LCS字符

function lcs( str1, str2) {
   var len1 = str1.length;
   var len2 = str2.length;
   
   var c = [...new Array(len1 + 1).keys()].map(v => []); 
   // or v => new Array(len2 +1)
   /* [
      [...],
      [...]
      ...
    ] */
   var z;
    for (var i = 0; i <= len1; i++) { 
      for( var j = 0; j <= len2; j++) { 
         if(i == 0 || j == 0) { 
            c[i][j] = 0; 
         } else if (str1.charAt(i-1) == str2.charAt(j-1)) { 
            c[i][j] = c[i-1][j-1] + 1; 
         } else { 
            c[i][j] = Math.max(c[i - 1][j], c[i][j - 1]); 
         } 
       } 
    } 

   console.log(c[len1][len2]); // 最长子序长度 
   return c;// 二维数组表,数组最后一位 c[n-1][m-1] 就是长度m n是二维数组长度
} 

//最长子序 是什么 

function llcs(dp, len1, len2){ 
  var i, j, z = 0; 
  var c = []; 
  i = len1, j = len2; 
  while(i!=0 && j!=0) { 
    if(a[i-1] == b[j-1]) {  // 相等代表这个字符是LCS的一员
       c[z++] = a[--i]; 
       j--; 
     } else if(dp[i-1][j] < dp[i][j-1]) {
        //如果 j-1 数字大， 这个子序长 ，从这条检索，然后j - 1 
        j--;
     }else if(dp[i][j-1] <= dp[i-1][j]) {
        // 如果 i -1 大 , 从 i-1 检索
        i--; 
     }
  } 
  console.log(c); 
} 

var a = 'abdejfsapfaasg3sadfp3f'; 
var b = 'asf3fahfpjasdfjiuegiada'; 
llcs(lcs(a,b),a.length,b.length );

该方法的基本思想是：设待排序元素序列有n个元素，首先取一个整数increment（小于n）作为间隔将全部元素分为increment个子序列，所有距离为increment的元素放在同一个子序列中，在每一个子序列中分别实行直接插入排序。然后缩小间隔increment，重复上述子序列划分和排序工作。直到最后取increment=1，将所有元素放在同一个子序列中排序为止。
由于开始时，increment的取值较大，每个子序列中的元素较少，排序速度较快，到排序后期increment取值逐渐变小，子序列中元素个数逐渐增多，但由于前面工作的基础，大多数元素已经基本有序，所以排序速度仍然很快。

关于希尔排序increment（增量）的取法。
增量increment的取法有各种方案。最初shell提出取increment=n/2向下取整，increment=increment/2向下取整，直到increment=1。但由于直到最后一步，在奇数位置的元素才会与偶数位置的元素进行比较，这样使用这个序列的效率会很低。后来Knuth提出取increment=n/3向下取整+1.还有人提出都取奇数为好，也有人提出increment互质为好。应用不同的序列会使希尔排序算法的性能有很大的差异。

[cc lang=”javascript”]
function shellSort(arr) {
var len = arr.length,
temp,
gap = 1;
console.time(‘希尔排序耗时:’);
while(gap < len/5) { //动态定义间隔序列 gap =gap*5+1; } for (gap; gap > 0; gap = Math.floor(gap/5)) {
for (var i = gap; i < len; i++) { temp = arr[i]; for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
arr[j+gap] = arr[j];
}
arr[j+gap] = temp;
}
}
console.timeEnd(‘希尔排序耗时:’);
return arr;
}[/cc]

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向 前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要 反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
[cc lang=”javascript”]function(array){
for (var i = 1; i < array.length; i++) { var key = array[i]; //取出下一个元素，在已经排序的元素序列中从后向前扫描； var j = i - 1; while (j >= 0 && array[j] > key) { //如果已排序元素大于新元素；
array[j + 1] = array[j]; // 已排元素向右移一位，相当于让出j位留给新元素
j–;
}
array[j + 1] = key; // 如果已排元素array[j]= left; j–) { // left 右边依次向右移一位，包括left 也向右移
array[j + 1] = array[j];
}
array[left] = key; // 然后left 的位置留给新元素
}

return array;[/cc]

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
javascript代码实现:

[cc lang=”javascript”]function selectionSort(arr) {
var len = arr.length;
var minIndex, temp;
console.time(‘选择排序耗时’);
for (var i = 0; i < len - 1; i++) { minIndex = i; for (var j = i + 1; j < len; j++) { if (arr[j] < arr[minIndex]) { //寻找最小的数 minIndex = j; //将最小数的索引保存 } } temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } console.timeEnd('选择排序耗时'); return arr; }[/cc]

1.冒泡排序（Bubble Sort）
描述：冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
[cc lang=”javascript”]function bubbleSort(arr) {
var len = arr.length;
for (var i = 0; i < len; i++) { // 每循环一次，第二层循环完就把最大的数排在最后， //下次循环时，通过i变大，就把找出的最大数就不参与比较 for (var j = 0; j < len - 1 - i; j++) { 两两比大小，这一层循环完最大数就在最后 if (arr[j] > arr[j+1]) { //相邻元素两两对比
var temp = arr[j+1]; //元素交换
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}[/cc]
改进冒泡排序： 设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。
改进后算法如下:
[cc lang=”javascript”]
function bubbleSort2(arr) {
console.time(‘改进后冒泡排序耗时’);
var i = arr.length-1; //初始时,最后位置保持不变
while ( i> 0) {
var pos= 0; //每趟开始时,无记录交换
for (var j= 0; j< i; j++) if (arr[j]> arr[j+1]) {
pos= j; //记录交换的位置
var tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp;
}
i= pos; //为下一趟排序作准备
}
console.timeEnd(‘改进后冒泡排序耗时’);
return arr;
}
// [3,2,1,4,5,6] 外层第一次循环结束后 [2,1,3,4,5,6] 并记录 i= pos =1
// 外层第二层循环 结束后 [1,2,3,4,5,6] 并记录 i=pos=0 ； 所以循环结束
[/cc]

传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。

改进后的算法实现为:
function bubbleSort3(arr3) {
var low = 0;
var high= arr.length-1; //设置变量的初始值
var tmp,j;
console.time(‘2.改进后冒泡排序耗时’);
while (low < high) { for (j= low; j< high; ++j) //正向冒泡,找到最大者 if (arr[j]> arr[j+1]) {
tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp;
}
–high; //修改high值, 前移一位
for (j=high; j>low; –j) //反向冒泡,找到最小者
if (arr[j]< arr[j-1]){ tmp = arr[j]; arr[j]= arr[j-1]; arr[j-1]=tmp; } ++low; }

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面； 不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；

内排序：所有排序操作都在内存中完成；
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
时间频度 一个算法执行所耗费的时间， 通常一个算法中的语句执行次数称为语句频度或时间频度，T(n)

时间复杂度: 在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化. 若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
按数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),…， k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

最坏时间复杂度和平均时间复杂度 　最坏情况下的时间复杂度称最坏时间复杂度。

求时间复杂度
如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

时间复杂度评价性能
有两个算法A1和A2求解同一问题，时间复杂度分别是T1(n)=100n2，T2(n)=5n3。（1）当输入量n＜20时，有T1(n)＞T2(n)，后者花费的时间较少。（2）随着问题规模n的增大，两个算法的时间开销之比5n3/100n2=n/20亦随着增大。即当问题规模较大时，算法A1比算法A2要有效地多。它们的渐近时间复杂度O(n2)和O(n3)从宏观上评价了这两个算法在时间方面的质量。在算法分析时，往往对算法的时间复杂度和渐近时间复杂度不予区分，而经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。
空间复杂度

一个程序的空间复杂度是指运行完一个程序所需内存的大小

树
度：一个节点有几个分支就是几度
层：根为第一层，根的孩子为第二层，以此类推
深度：最大层次数为树的深度

二叉树
二叉树特点
由二叉树定义以及图示分析得出二叉树有以下特点：
1）每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。
2）左子树和右子树是有顺序的，次序不能任意颠倒。
3）即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

二叉树性质
1）在二叉树的第i层上最多有2^(i-1) 个节点 。（i>=1）
2）二叉树中如果深度为k,那么最多有2^k-1个节点。(k>=1）
3）n0=n2+1 n0表示度数为0的节点数，n2表示度数为2的节点数。
4）在完全二叉树中，具有n个节点的完全二叉树的深度为[log2^n]+1，其中[log2n]是向下取整。
5）若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点有如下特性：
(1) 若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 [i/2] 的结点为其双亲结点;
(2) 若 2i>n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点；
(3) 若 2i+1>n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。

3.5 满二叉树
满二叉树：在一棵二叉树中。如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
满二叉树的特点有：
1）叶子只能出现在最下一层。出现在其它层就不可能达成平衡。
2）非叶子结点的度一定是2。
3）在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

3.6 完全二叉树
完全二叉树：对一颗具有n个结点的二叉树按层编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。

特点：
1）叶子结点只能出现在最下层和次下层。
2）最下层的叶子结点集中在树的左部。
3）倒数第二层若存在叶子结点，一定在右部连续位置。
4）如果结点度为1，则该结点只有左孩子，即没有右子树。
5）同样结点数目的二叉树，完全二叉树深度最小。
注：满二叉树一定是完全二叉树，但反过来不一定成立。

3.7 二叉树的存储结构

二叉树的顺序存储结构就是使用一维数组存储二叉树中的结点，并且结点的存储位置，就是数组的下标索引。

3.7.2 二叉链表

既然顺序存储不能满足二叉树的存储需求，那么考虑采用链式存储。由二叉树定义可知，二叉树的每个结点最多有两个孩子。因此，可以将结点数据结构定义为一个数据和两个指针域。表示方式如图3.11所示：

3.8 二叉树遍历

二叉树的遍历是指从二叉树的根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次，且仅被访问一次。
二叉树的访问次序可以分为四种

前序遍历
中序遍历
后序遍历
层序遍历

前序遍历通俗的说就是从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左在向右的方向访问。

从根结点出发，则第一次到达结点A，故输出A;
继续向左访问，第一次访问结点B，故输出B；
按照同样规则，输出D，输出H；
当到达叶子结点H，返回到D，此时已经是第二次到达D，故不在输出D，进而向D右子树访问，D右子树不为空，则访问至I，第一次到达I，则输出I；
I为叶子结点，则返回到D，D左右子树已经访问完毕，则返回到B，进而到B右子树，第一次到达E，故输出E；向E左子树，故输出J；按照同样的访问规则，继续输出C、F、G； 则3.13所示二叉树的前序遍历输出为： ABDHIEJCFG

3.8.3 中序遍历

中序遍历就是从二叉树的根结点出发，当第二次到达结点时就输出结点数据，按照先向左在向右的方向访问。

二叉树中序访问如下： 从根结点出发，则第一次到达结点A，不输出A，继续向左访问，第一次访问结点B，不输出B；继续到达D，H；到达H，H左子树为空，则返回到H，此时第二次访问H，故输出H；
H右子树为空，则返回至D，此时第二次到达D，故输出D；
由D返回至B，第二次到达B，故输出B；
按照同样规则继续访问，输出J、E、A、F、C、G；

则3.13所示二叉树的中序遍历输出为：
HDIBJEAFCG

3.8.4 后序遍历

后序遍历就是从二叉树的根结点出发，当第三次到达结点时就输出结点数据，按照先向左在向右的方向访问。

二叉树后序访问如下：

从根结点出发，则第一次到达结点A，不输出A，继续向左访问，第一次访问结点B，不输出B；继续到达D，H；
到达H，H左子树为空，则返回到H，此时第二次访问H，不输出H；
H右子树为空，则返回至H，此时第三次到达H，故输出H；
由H返回至D，第二次到达D，不输出D；
继续访问至I，I左右子树均为空，故第三次访问I时，输出I；
返回至D，此时第三次到达D，故输出D；
按照同样规则继续访问，输出J、E、B、F、G、C，A；

则图3.13所示二叉树的后序遍历输出为：
HIDJEBFGCA

function TreeCode() {
    let BiTree = function (ele) {
        this.data = ele;
        this.lChild = null;
        this.rChild = null;
    }

    this.createTree = function () {
        let biTree = new BiTree('A');
        biTree.lChild = new BiTree('B');
        biTree.rChild = new BiTree('C');
        biTree.lChild.lChild = new BiTree('D');
        biTree.lChild.lChild.lChild = new BiTree('G');
        biTree.lChild.lChild.rChild = new BiTree('H');
        biTree.rChild.lChild = new BiTree('E');
        biTree.rChild.rChild = new BiTree('F');
        biTree.rChild.lChild.rChild = new BiTree('I');
        return biTree;
    }
}

//前序遍历
function ProOrderTraverse(biTree) {
    if (biTree == null) return;
    console.log(biTree.data);
    ProOrderTraverse(biTree.lChild);
    ProOrderTraverse(biTree.rChild);
}

//中序遍历
function InOrderTraverse(biTree) {
    if (biTree == null) return;
    InOrderTraverse(biTree.lChild);
    console.log(biTree.data);
    InOrderTraverse(biTree.rChild);
}

//后续遍历
function PostOrderTraverse(biTree) {
    if (biTree == null) return;
    PostOrderTraverse(biTree.lChild);
    PostOrderTraverse(biTree.rChild);
    console.log(biTree.data);
}

let myTree = new TreeCode();
console.log(myTree.createTree());
console.log('前序遍历')
ProOrderTraverse(myTree.createTree());
console.log('中序遍历')
InOrderTraverse(myTree.createTree());
console.log('后续遍历')
PostOrderTraverse(myTree.createTree());

二叉树的按层遍历法

二叉树分好多层，因为要按层遍历，所以如果直接采用函数递归的话，一下子就深入层底了，达不到按层的目的。

所以要换一个角度，按照队列顺序输出！算法步骤如下：

1、把根节点A放入队列，此时队列为：A，队列头指针指向A，也就是队列第一个元素

2、把当前队列头指针所指元素的左右儿子放入队列，即将B C放入队列，此时队列为A B C ，队列头指针向下移一格，此时指向B

3、不断重复2步骤。此时把B的左右儿子取出来放入队尾，队列变为A B C D E，队列头指针后移，指向c，c没有子节点，队列不再延长；

4、结束条件，队列头指针和为指针重合时，输出最后一个元素，算法结束！

也就是说，把这个队列从头到尾输出一遍，就是按层遍历，这个队列是动态的，只要有子节点，子节点就会不停的加入队尾，但总有子节点没有的时候，所以，队列尾指针肯定有不再移动的时候，而头指针一直在一步一步向下移，总会有首尾指针重合的时候，即标志着算法结束。

void Layer_order(BiTree * TNode,BiTree ** F,BiTree ** R)
{

    *F=TNode;            //将当前节点放入队列首指针所指位置
    printf("%c    ",(*F)->data);
    if((*F)->lchild!=NULL) {
      R=R+1;
      *R=(*F)->lchild;    //节点的左儿子放入队尾
    }
    if((*F)->rchild!=NULL){
       R=R+1;                //首指针向后移动一格
       *R=(*F)->rchild;    //节点的右儿子放入队尾
    }
    if(F!=R){
     F=F+1;
     Layer_order(*F,F,R);//递归
    }
}

4、写main函数，建立一个队列，长度1024，存放节点指针（其实就是一个存放指针的数组），这一部分放在main函数中，这个队列是唯一的，不参与递归
    BiTree ** F;             //队首指针       指向指针的指针，因为队列数组里的元素全是指针
    BiTree ** R;            //队尾指针
    BiTree * Queue[1024];//队列数组
    F=Queue;
    R=Queue;            //开始时队首队尾指针重合

BiTree * root;      //在main函数中建立一个二叉树根的指针

root=CreatBiTree();      //创建树

Layer_order(root,F,R); //按层遍历树