一. 二叉树

二叉树的性质：

1.树是 非线性数据结构

存储 “一对多”的数据结构。

2.度：

image.png
3.层次从1开始。深度是层次的最大值。
image.png

3.完全二叉树

完全二叉树 不是 完美二叉树。
image.png

4.堆是完全二叉树

可以使用 完全二叉树的性质。

5.普通二叉树 性质

image.png

6.完全二叉树的性质：计算 叶子节点的个数

一般二叉树：
n = n0 + n1 + n2;
n - 1 = n1 + 2 n2; // -1 是去掉跟节点
=> n0 = n2 + 1; // n0 和 n2 相差很少
*完全二叉树：
1）n0 = ?
n0 = n2 + 1; // n0 和 n2 相差很少
由 n = n0 + n1 + n2;
=> n = n0 + n1 + (n0 - 1);
=> n0 = ((n + 1) - n1) / 2;
n 为奇数，n0 = (n + 1) / 2;
n 为偶数，n0 = n / 2;
2）n1 为 0， n 为奇数
3）n1 为 1，n 为偶数

n 为 3， n0 为 2
n 为 4， n0 为 2
n 为 5， n0 为 3
n 为 6， n0 为 3
=> n0 = Math.ceil(n / 2);

n 为 3， 非 n0 为 1
n 为 4， 非 n0 为 2
n 为 5， 非 n0 为 2
n 为 6， 非 n0 为 3
=> n1 + n2 = Math.floor(n / 2);

二叉搜索树：http://caibaojian.com/js-bst.html

二. 堆

堆 是 完全二叉树，在构建堆时，应用到了 完全二叉树的性质，比如说 非叶子结点的下标是
[0, Math.floor(n / 2)]。
另外构建堆，分为两步：（参考：https://zhuanlan.zhihu.com/p/89600623）
1）从末尾非叶子几点遍历
2）以每个非叶子节点为根节点递归

1.构建最大堆

  1. function createHeap(arr) {
  2.     let n = arr.length;
  4.     const maxHeapify = function(rootIndex) {
  5.       let leftIndex = 2 * rootIndex + 1;
  6.       let rightIndex = 2 * rootIndex + 2;
  7.       let largest = rootIndex; // 流动红旗
  9.       // 左右子树先后竞争
  10.       if (leftIndex < n && arr[leftIndex] > arr[largest]) {
  11.         largest = leftIndex;
  12.       }
  13.       if (rightIndex < n && arr[rightIndex] > arr[largest]) {
  14.         largest = rightIndex;
  15.       }
  17.       // 检查竞争结果，察觉红旗是否最终改动到子树上
  18.       if (largest !== rootIndex) {
  19.         // 交换
  20.         let tmp = arr[rootIndex];
  21.         arr[rootIndex] = arr[largest];
  22.         arr[largest] = tmp;
  24.         // 递归
  25.         maxHeapify(largest);
  26.       }
  27.     };
  29.     // 遍历 非叶子节点
  30.     for (let i = Math.floor(n / 2); i >= 0; i--) {
  31.         maxHeapify(i);
  32.     }
  33. }

2.最大堆排序

  1. function createHeap(arr, heapSize) { // 添加heapsize参数：在不复制数组的情况下，对原数组精确操作
  2.     let n = heapSize;
  3.     const maxHeapify = function(rootIndex) {
  4.       let leftIndex = 2 * rootIndex + 1;
  5.       let rightIndex = 2 * rootIndex + 2;
  6.       let largest = rootIndex; // 流动红旗
  8.       // 左右子树先后竞争
  9.       if (leftIndex < n && arr[leftIndex] > arr[largest]) {
  10.         largest = leftIndex;
  11.       }
  12.       if (rightIndex < n && arr[rightIndex] > arr[largest]) {
  13.         largest = rightIndex;
  14.       }
  16.       // 检查竞争结果，察觉红旗是否最终改动到子树上
  17.       if (largest !== rootIndex) {
  18.         // 交换
  19.         let tmp = arr[rootIndex];
  20.         arr[rootIndex] = arr[largest];
  21.         arr[largest] = tmp;
  23.         // 递归
  24.         maxHeapify(largest);
  25.       }
  26.     };
  28.     for (let i = Math.floor(n / 2); i >= 0; i--) {
  29.         maxHeapify(i);
  30.     }
  31. }
  32. console.log(createHeap([3, 4, 5, 1, 5, 7, 2]));
  34. function swap(arr, i, j) {
  35.     let tmp = arr[i];
  36.     arr[i] = arr[j];
  37.     arr[j] = tmp;
  38. }
  40. // function heapSort(arr) {
  41. //     let n = arr.length;
  42. //     for (let i = 0; i < n - 1; i++) {
  43. //         createHeap(arr.slice(0, n - i)); // 避免陷入怎么传入数组的困惑，也避免传入起始下标，因为开始下标是固定的，只需要传入堆的长度即可
  44. //         swap(arr, 0, n - 1 - i);
  45. //     }
  47. //     return arr;
  48. // }
  50. function heapSort(arr) {
  51.     let n = arr.length;
  52.     for (let i = 0; i < n - 1; i++) {
  53.         createHeap(arr, n - i); // 避免陷入怎么传入数组的困惑，也避免传入起始下标，因为开始下标是固定的，只需要传入堆的长度即可
  54.         swap(arr, 0, n - i - 1);
  55.     }
  57.     return arr;
  58. }
  60. console.log(heapSort([3, 4, 5, 1, 5, 7, 2]));

3.最大堆 插入/删除 新值

堆 在这里 是以数组存储。
插入：在已经生成的最大堆插入新值，是将 新值 放到数组末尾，然后重复生成最大堆的动作。
删除，是将数组末尾的数 覆盖 root 之后，然后重复生成最大堆的动作。
图例

  1. function deleteHeap(arr) {
  2.     let n = arr.length;
  3.     arr[0] = arr[n - 1];
  4.     arr.length = n - 1; // 缩减数组长度
  5.     createHeap(arr, arr.length);
  6. }
  8. function addHeap(arrm, num) {
  9.     arr.push(num);
  10.     createHeap(arr, arr.length);
  11. }

相关题目：

3.最小堆

很好改：

  1. function createHeap(arr, heapSize) {
  2.     let n = heapSize;
  3.     const minHeapify = function(rootIndex) {
  4.       let leftIndex = 2 * rootIndex + 1;
  5.       let rightIndex = 2 * rootIndex + 2;
  6.       let samllest = rootIndex; // 流动红旗 ---> new
  8.       // 左右子树先后竞争
  9.       if (leftIndex < n && arr[leftIndex] < arr[samllest]) { // ---> new
  10.         samllest = leftIndex;
  11.       }
  12.       if (rightIndex < n && arr[rightIndex] < arr[samllest]) { // ---> new
  13.         samllest = rightIndex;
  14.       }
  16.       // 检查竞争结果，察觉红旗是否最终改动到子树上
  17.       if (samllest !== rootIndex) {
  18.         // 交换
  19.         let tmp = arr[rootIndex];
  20.         arr[rootIndex] = arr[samllest];
  21.         arr[samllest] = tmp;
  23.         // 递归
  24.         minHeapify(samllest);
  25.       }
  26.     };
  28.     for (let i = Math.floor(n / 2); i >= 0; i--) {
  29.         minHeapify(i);
  30.     }
  31. }

这样的排序，最终出来是升序。

4.最大堆在react里的使用

react 算法中的 堆，这个在讲 自己 看多react 源码时，最好 也能手写出来。
以下是 react 的实现：

  1. export function push(heap: Heap, node: Node): void {
  2.   const index = heap.length;
  3.   heap.push(node);
  4.   siftUp(heap, node, index);
  5. }
  7. export function peek(heap: Heap): Node | null {
  8.   const first = heap[0];
  9.   return first === undefined ? null : first;
  10. }
  12. export function pop(heap: Heap): Node | null {
  13.   const first = heap[0];
  14.   if (first !== undefined) {
  15.     const last = heap.pop();
  16.     if (last !== first) {
  17.       heap[0] = last;
  18.       siftDown(heap, last, 0);
  19.     }
  20.     return first;
  21.   } else {
  22.     return null;
  23.   }
  24. }
  26. function siftUp(heap, node, i) {
  27.   let index = i;
  28.   while (true) {
  29.     const parentIndex = (index - 1) >>> 1;
  30.     const parent = heap[parentIndex];
  31.     if (parent !== undefined && compare(parent, node) > 0) {
  32.       // The parent is larger. Swap positions.
  33.       heap[parentIndex] = node;
  34.       heap[index] = parent;
  35.       index = parentIndex;
  36.     } else {
  37.       // The parent is smaller. Exit.
  38.       return;
  39.     }
  40.   }
  41. }
  43. function siftDown(heap, node, i) {
  44.   let index = i;
  45.   const length = heap.length;
  46.   while (index < length) {
  47.     const leftIndex = (index + 1) * 2 - 1;
  48.     const left = heap[leftIndex];
  49.     const rightIndex = leftIndex + 1;
  50.     const right = heap[rightIndex];
  52.     // If the left or right node is smaller, swap with the smaller of those.
  53.     if (left !== undefined && compare(left, node) < 0) {
  54.       if (right !== undefined && compare(right, left) < 0) {
  55.         heap[index] = right;
  56.         heap[rightIndex] = node;
  57.         index = rightIndex;
  58.       } else {
  59.         heap[index] = left;
  60.         heap[leftIndex] = node;
  61.         index = leftIndex;
  62.       }
  63.     } else if (right !== undefined && compare(right, node) < 0) {
  64.       heap[index] = right;
  65.       heap[rightIndex] = node;
  66.       index = rightIndex;
  67.     } else {
  68.       // Neither child is smaller. Exit.
  69.       return;
  70.     }
  71.   }
  72. }
  74. function compare(a, b) {
  75.   // Compare sort index first, then task id.
  76.   const diff = a.sortIndex - b.sortIndex;
  77.   return diff !== 0 ? diff : a.id - b.id;
  78. }

我的实现：（简洁一些，不考虑细枝末节）

  1. // 不用递归，用 while 循环
  2. function push(heap = [], v) {
  3.     heap.push(v);
  4.     shiftUp(heap, v);
  5. }
  6. function shiftUp(heap, v) {
  7.     let index = heap.length;
  9.     while (index >= 0) {
  10.         let parentIndex = index >>> 1;
  11.         let parent = heap[parentIndex];
  12.         if (compare(parent, v) > 0) {
  13.             heap[parentIndex] = v;
  14.             heap[index] = parent;
  15.             index = parentIndex;
  16.         } else {
  17.             return;
  18.         }
  19.     }
  20. }
  21. function siftDown(heap) { // 斩首，用末尾元素替代头颅，然后规整秩序，记住我们不管左右子节点之间的关系
  22.     let index = 0;
  24.     // while (true) { // 不知道规定什么条件好，先来个 true
  25.     while (index < heap.length) {
  26.         let node = heap[index];
  27.         let leftIndex = 2 * index + 1;
  28.         let rightIndex = 2 * leftIndex + 2;
  29.         let left = heap[leftIndex];
  30.         let right = heap[rightIndex];
  32.         if (compare(left, node) < 0) { // 取最小即可
  33.             if (compare(left, right) < 0) { // left 最小，只能和 left 换
  34.                 heap[leftIndex] = node;
  35.                 heap[index] = left;
  36.                 index = leftIndex;
  37.             } else {
  38.                 heap[rightIndex] = node;
  39.                 heap[index] = right;
  40.                 index = rightIndex;                
  41.             }
  42.         } else if (compare(right, node) < 0) {
  43.             heap[rightIndex] = node;
  44.             heap[index] = right;
  45.             index = rightIndex;
  46.         } else {
  47.             // 不动
  48.             return;
  49.         }
  50.     }
  51. }
  53. function compare(a, b) {
  54.     return a - b;
  55. }

react 里最多的数据结构：链表相关（单链表 双向链表）
判断单链表是否有环、翻转链表、插入、删除。
判断单链表是否有环，也可以扩展到 对象里是否有循环结构，lodash 是如何解决的？

参考：https://juejin.im/post/6844903482432962573

includes 是 严格的等！
image.png

从这篇文章我想明白为什么要用栈的结构：因为一个对象可能有并列的多个环，另外还要考虑值类型不能是基本类型，只能是指向地址的对象。
https://www.jianshu.com/p/a2bb29aa4fce

三. 链表

仍然是考察代码能力，而非算法

1. 链表结构

  1. class ListNode {
  2.     constructor(value) {
  3.         this.next = null;
  4.         this.value = value;
  5.     }
  6. }
  7. class List {
  8.     constructor(arr) {
  9.         this.head = this.tail = null;
  10.         this.length = 0;
  12.         if (Array.isArray(arr)) {
  13.             for (let i of arr) {
  14.                 let node = new ListNode(i);
  15.                 this.append(node);
  16.             }          
  17.         }
  18.     }
  19.     append(node) {
  20.         if (this.head) {
  21.             this.tail = this.tail.next = node;
  22.         } else {
  23.             this.head = this.tail = node;
  24.         }
  25.         this.length++;
  26.     }
  27.     deleteByValue(targetValue) {
  28.         let p = this.head;
  29.         let parent = this.head;
  30.         let nodeToDelete = null;
  32.         while (p) {
  33.             let { value } = p;
  34.             if (value === targetValue) {
  35.                 nodeToDelete = p;
  36.                 break;
  37.             } else {
  38.                 parent = p;
  39.                 p = p.next;
  40.             }
  41.         }
  43.         if (nodeToDelete) {
  44.             parent.next = nodeToDelete.next;
  45.             this.length--;
  46.         }
  47.     }
  48. }
  50. let l = new List([1, 2, 3, 4, 5]);
  51. console.log('创建链表：', l);
  53. l.deleteByValue(3);
  54. console.log('删除值为3的节点', l);

2. 合并两个有序链表

  1. // 合并有序数组(最简单情况，数组长度相同)
  2. function mergeList(list1, list2) {
  3.     let p = list1.head;
  4.     let q = list2.head;
  6.     let newListHead = null;
  7.     let current = null;
  8.     while (p && q) {
  9.         // 1) 获取最小节点赋值 给c, 并更新 p q
  10.         let c = null; // 一开始的误区就是少定义了这个变量
  11.         if (p.value < q.value) { // p 和 q 两者取最小
  12.             c = p;
  13.             p = p.next;
  14.         } else {
  15.             c = q;
  16.             q = q.next;
  17.         }
  19.         // 2）构造新链表的节点关系
  20.         if (newListHead) {
  21.             current.next = c;
  22.             current = current.next; // current 要变化才行！
  23.         } else {
  24.             newListHead = c;
  25.             current = c;
  26.         }
  27.     }
  28.     return newListHead;
  29. }
  31. let l1 = new List([1, 2, 9, 10]);
  32. let l2 = new List([3, 4, 11, 12]);
  33. console.log(`合并l1和l2的结果：`, mergeList(l1, l2));
  34. console.log();

3. 逆转单链表

  1. function inverseList(list) {
  2.     let o = null;
  3.     let p = list.head;
  4.     let q = p.next;
  6.     while(q) { // 首先要有三个 o p q 指针，另外要同时保证在 每轮循环 移动 o p q 三个指针的同时，并且修正相互指代的关系
  7.         p.next = o;
  8.         o = p;
  10.         p = q;
  11.         q = p.next;
  12.         p.next = o;
  13.     }
  14.     return p;
  15. }
  16. console.log(inverseList(new List([1, 2, 3, 4])));

逆转单链表，从来都是最绕的，没有之一：（下面是第二次写，给的写法）

  1. class List {
  2.   // ...
  3.   invert() {
  4.         // 定义三个相邻的指针
  5.       let x = null;
  6.       let p = this.head
  7.       let y = this.head.next;
  9.       while (p) { // while循环的条件只要定为，循环体不报错就好
  10.         // 逆转的关键
  11.         p.next = x;
  13.         // 移动三个指针
  14.         x = p;
  15.         p = y;
  16.         y = y && y.next;
  17.       }
  19.       this.head = x;
  20.       return this;
  21.     }
  22.   // ...
  23. }

四、图

1. 拓扑排序

可用来检测 图里是否有环！（判断是否有环，常规的做法也可以借助数据结构，比如说一个数组，来存放已经被访问过的元素）。
参考：https://blog.csdn.net/weixin_42001089/article/details/84327306
toposort 是 npm 包，提供给你做 图的拓扑排序。
https://hotttao.github.io/2018/11/19/alog/graph_use2/ 来讲了 拓扑排序 在编译器领域的使用。
image.png
拓扑排序的题目：
image.png
答案：

  1. 山的那边海的那边有一群小精灵！