  树是一种非线性表数据结构，树的基本概念如下所列。
  （1）结点高度：结点到叶子结点的最长路径（即边数）。例题：[112\. 路径总和](https://leetcode-cn.com/problems/path-sum/)。
  （2）结点深度：根结点到这个结点所经历的边的个数。例题：[104\. 二叉树的最大深度](https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/)。
  （3）结点层数：结点深度加 1。
  （4）树的高度：根结点的高度。例题：[面试题 04.02. 最小高度树](https://leetcode-cn.com/problems/minimum-height-tree-lcci/)。
  后面几张这种类型的图都来源于《[数据结构与算法之美](https://time.geekbang.org/column/126)》。
:-: 
图 2
  （5）二叉树：只包含左右两个子结点的树（编号1）。
  （6）满二叉树：所有分支结点都存在左右子树，并且所有叶子结点都在同一层上（编号2）。例题：[894\. 所有可能的满二叉树](https://leetcode-cn.com/problems/all-possible-full-binary-trees/)。
  （7）完全二叉树：叶子结点都在最底下两层，最后一层的叶子结点都靠左排列，并且除了最后一层，其余结点个数都要达到最大（编号3）。例题：[222\. 完全二叉树的结点个数](https://leetcode-cn.com/problems/count-complete-tree-nodes/)。
:-: 
图 3
## 一、二叉树
**1）实现**
  有两种方法存储一棵二叉树，第一种是基于指针的链式存储法，[如下所示](https://codepen.io/strick/pen/LYGMrVO)。
~~~
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
class TreeList {
constructor(datas) {
this.root = null;
datas.forEach((value) => {
const node = new Node(value);
if (this.root == null) {
this.root = node;
return;
}
this.insert(this.root, node);
});
}
insert(parent, child) {
if (parent.data > child.data) {
parent.left === null
? (parent.left = child)
: this.insert(parent.left, child);
return;
}
parent.right === null
? (parent.right = child)
: this.insert(parent.right, child);
}
}
~~~
  第二种是基于数组的顺序存储法。
~~~
left = 2 * index + 1; //左结点下标
right = 2 * index + 2; //右结点下标
~~~
  例题：LeetCode的[236\. 二叉树的最近公共祖先](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/)，递归的在左右子树中查找两个指定的结点，最后判断公共祖先所在的位置。在当前结点的左子树，或在其右子树，又或者它就是两种的公共祖先。
**2）遍历**
  二叉树的遍历有四种（[示例如下](https://codepen.io/strick/pen/mdVaKVz)）：
  （1）前序：先访问当前结点，然后访问左子树，再访问右子树。
~~~
preOrder(root = this.root) {
//前序
if (!root) {
return;
}
console.log(root.data);
this.preOrder(root.left);
this.preOrder(root.right);
}
~~~
:-: 
图 4
  面试题28[对称二叉树](https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/)。前序遍历的变种是先访问右结点，再访问左结点，如果其遍历结果与前序遍历结果相同，就说明是对称的。
  面试题34[二叉树中和为某一值的路径](https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/)。前序遍历首先访问根结点，在用前序遍历访问结点时，将其压入栈中，遇到叶结点，就求和判断结果是否符合要求。然后将叶结点出栈，回到父节点，继续遍历右子树，递归执行该过程。
  （2）中序：先访问左子树，然后访问当前结点，再访问右子树。
~~~
inOrder(root = this.root) {
//中序
if (!root) {
return;
}
this.midOrder(root.left);
console.log(root.data);
this.midOrder(root.right);
}
~~~
:-: 
图 5
  面试题7[重建二叉树](https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/)。前序遍历第一个数是根结点，中序遍历以根结点为界其两边分别是左右子树，递归构建左右子树。
  面试题54[BST中第 k 大的结点](https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/)。中序遍历BST，得到的序列是递增的。
  （3）后序：先访问左子树，然后访问右子树，再访问当前结点。
~~~
postOrder(root = this.root) {
//后序
if (!root) {
return;
}
this.backOrder(root.left);
this.backOrder(root.right);
console.log(root.data);
}
~~~
:-: 
图 6
  面试题33[BST的后序遍历序列](https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/)。序列的最后一个数字是根结点，左子树的结点都比根结点小，右子树的结点都比根结点大，递归执行该过程。
  （4）层序：自上而下，自左至右逐层访问树的结点。利用一个辅助队列来完成层序遍历。
~~~
levelOrder(node = this.root) {
//层序
let queue = [];
queue.push(node); // 根结点入队
while (queue.length) {
node = queue.shift(); // 出队
console.log(node.data); // 访问该结点
if (node.left) {
// 如果它的左子树不为空
queue.push(node.left); // 将左子树的根结点入队
}
if (node.right) {
// 如果它的右子树不为空
queue.push(node.right); // 将右子树的根结点入队
}
}
}
~~~
  除了层序遍历之外，其余三种都采用递归的方式来遍历二叉树。
  有两种图的搜索算法，也适用于树。
  （1）广度优先搜索算法（Breadth-First Search，BFS）会从根结点开始遍历，先访问其所有的相邻点，就像一次访问树的一层，也就是先宽后深地访问结点，之前的层序遍历就是BFS，如下图左半部分。
  （2）深度优先搜索算法（Depth-First-Search，DFS）会从根结点开始遍历，沿着路径直到这条路径最后一个叶结点被访问，接着原路回退并探索下一条路径，也就是先深度后广度地访问结点，如下图右半部分。
:-: 
  在《[算法小抄](https://labuladong.gitbook.io/algo/di-ling-zhang-bi-du-xi-lie/xue-xi-shu-ju-jie-gou-he-suan-fa-de-gao-xiao-fang-fa#san-suan-fa-shua-ti-zhi-nan)》一文中曾强调先刷二叉树的LeetCode题目，因为很多难题本质上都是基于二叉树的遍历，例如LeetCode的[124 题](https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/)（二叉树中的最大路径和）、[105 题](https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)（从前序与中序遍历序列构造二叉树）和[99 题](https://leetcode-cn.com/problems/recover-binary-search-tree/)（恢复二叉搜索树）。
**3）递归**
  递归是一种应用广泛的编程技巧，如果要使用递归，需要满足三个条件。
  （1）一个问题的解可以分解为几个子问题的解。
  （2）这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样。
  （3）存在递归终止条件，即基线条件（Base Case）。
  注意，递归的关键就是找到将大问题分解为小问题的规律（推荐画出递归树），基于此写出递推公式，然后再推敲终止条件，并且需要警惕重复计算。下面是一个递归的大致模板。
~~~
function recursion(level, param1, param2, ...) {
//递归的终止条件
if(level > MAX_LEVEL) {
console.log("result");
return;
}
//数据处理
processData(level, data1,...);
//继续递归
recursion(level + 1, p1, ...);
//收尾工作
reverseState(level);
}
~~~
  递归的数学模型就是[归纳法](https://baike.baidu.com/item/%E6%95%B0%E5%AD%A6%E5%BD%92%E7%BA%B3%E6%B3%95)，其过程如下。
  （1）基础情况：证明 P(b)语句成立，该步骤只需带入数字即可。
  （2）声明假设：假设 P(n)语句成立。
  （3）归纳步骤：证明如果 P(n)语句成立，那么 P(n+1) 语句也一定成立。
  例如设计一程序，求自然数 N 的阶乘 N!。
  （1）当 N=1 时，N!=1。
  （2）假设 P(N)=N!，P(N+1)=(N+1)!。
  （3）证明 P(N) 和 P(N+1) 的关系：
~~~
P(N+1) = (N+1)! = (N+1)×(N)×…×2×1 = (N+1)×N! = (N+1)×P(N)
~~~
  根据这个公式可构造一个递归函数：
~~~
function factorial(N) {
return N * factorial(N - 1); //递归部分
}
~~~
  在采用数学归纳法设计递归程序后，就能摆脱每一步的递推，直接根据分析就能转化为代码。
  试图想清楚整个递和归过程的做法，实际上是一种思维误区，不符合人脑平铺直叙的思维方式。
## 二、二叉查找树
  在二叉查找树（Binary Search Tree，BST）中，每个结点的值都大于左子结点，小于右子结点。当中序遍历BST时，就可在 O(n) 的时间复杂度内输出有序的结点。
  BST的时间复杂度和树的高度成正比，即 O(height)，经过推导后，完全二叉树的高度（height）小于等于 log2^n。
  平衡二叉查找树的高度接近 logn，所以插入、删除、查找等操作的时间复杂度也比较稳定，都是 O(logn)。
**1）操作**
  在BST中查找一个结点的递归算法是（[代码如下所示](https://codepen.io/strick/pen/JjGwZeZ)）：
  （1）如果被查找的结点和根结点的值相等，则查找命中，否则就递归地的在适当的子树中继续查找。
  （2）如果被查找的结点值较小就选择左子树，否则就选择右子树。
~~~
find(data) {
//查找
let node = this.root;
while (node != null) {
if (data == node.data) {
return node;
}
data < node.data ? (node = node.left) : (node = node.right);
}
return null;
}
~~~
  BST插入结点的过程和查找差不多，依次比较结点值和左右子树的大小。
~~~
insert(parent, child) {
//插入
if (parent.data > child.data) {
parent.left === null
? (parent.left = child)
: this.insert(parent.left, child);
return;
}
parent.right === null
? (parent.right = child)
: this.insert(parent.right, child);
}
~~~
  在BST中查找最大和最小的结点，以最小值为例，如果根结点的左链接为空，那么一棵BST中的最小值就是根结点；如果左链接非空，那么最小值就是左子树中的最小值。
~~~
min(node = this.root) {
//最小值
if (node.left == null) return node;
return this.min(node.left);
}
~~~
**2）删除**
  针对删除结点的子结点个数的不同，需要分类讨论（[代码如下所示](https://codepen.io/strick/pen/oNbJMoK)）：
  （1）如果没有子结点，那么只需将父结点中，链接删除结点的指针置为 null。
  （2）如果只有一个子结点，那么只需更新父结点中，链接删除结点的指针指向其子结点即可。
  （3）如果包含两个子结点，那么需要先找到该结点右子树中的最小结点，替换要删除的结点；然后再删除该最小结点，由于最小结点肯定没有左子结点，因此可以使用上面两条规则删除它。
:-: 
图 7
~~~
del(data) {
//删除
let p = this.root, //p指向要删除的结点，初始化指向根结点
parent = null; //父结点
while (p != null && p.data != data) {
parent = p;
data > p.data ? (p = p.right) : (p = p.left);
}
if (p == null) return; //没有找到
// 要删除的结点有两个子结点
if (p.left != null && p.right != null) {
//查找右子树中最小结点
let minP = p.right,
minParent = p; //minParent表示minP的父结点
while (minP.left != null) {
minParent = minP;
minP = minP.left;
}
p.data = minP.data; //将minP的数据替换到p中
p = minP; //下面就变成了删除minP了
parent = minParent;
}
// 删除结点是叶子结点或者仅有一个子结点
let child; //p的子结点
if (p.left != null) child = p.left;
else if (p.right != null) child = p.right;
else child = null;
if (parent == null) this.root = child;
// 删除的是根结点
else if (parent.left == p) parent.left = child;
else parent.right = child;
}
~~~
**3）数据重复**
  要让BST支持重复数据，可以有两种处理方式。
  （1）在每个结点中增加一个链表，把相同的值存储到链表中。
  （2）将相同的值插入到结点的右子树中，作为大于这个结点来处理。
**4）平衡二叉查找树**
  平衡二叉树是指任意一个结点的左右子树的高度相差不能大于 1，让整棵树左右看起来比较对称和平衡，不要出现左子树很高、右子树很矮的情况。
  在下面的[示例](https://codepen.io/strick/pen/eYJbLmo)中，height()函数会自顶向下递归的计算结点的高度，isBalanced()函数会判断左右子树的高度差。
~~~
function isBalanced(root) {
if (root == null) return true;
if (Math.abs(height(root.left) - height(root.right)) > 1) {
return false;
}
return isBalanced(root.left) && isBalanced(root.right);
}
function height(root) {
if (root == null) return 0;
return Math.max(height(root.left) + 1, height(root.right) + 1);
}
~~~
## 三、堆
  堆（heap）是一种特殊的树形数据结构，它有两个特性：
  （1）必须是一棵完全二叉树。
  （2）结点的值要大于等于或小于等于两个子结点的值。
  当结点的值小于等于两个子结点的值，称之为小顶堆；当结点的值大于等于两个子结点的值，称之为大顶堆。
**1）实现**
  往堆中插入一个元素后，需要继续满足堆的两个特性，这个过程叫做堆化（heapify），下面的[示例](https://codepen.io/strick/pen/bGEOxLm)在构建一个大顶堆。
~~~
function heapify(arr, x, len) {
let l = 2 * x + 1, //左结点
r = 2 * x + 2, //右结点
largest = x,
temp;
if (l < len && arr[l] > arr[largest]) {
largest = l;
}
if (r < len && arr[r] > arr[largest]) {
largest = r;
}
if (largest != x) { //交换位置
temp = arr[x];
arr[x] = arr[largest];
arr[largest] = temp;
heapify(arr, largest, len);
}
}
const tree = [4, 5, 1, 2, 3, 6],
heapSize = tree.length;
for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
heapify(tree, i, heapSize);
}
~~~
**2）堆排序**
  堆排序是一种原地的、时间复杂度为 O(nlogn) 的不稳定排序算法。排序主要分为两个过程：一是构建堆；二是交换堆顶元素与最后一个元素的位置，[如下所示](https://codepen.io/strick/pen/pogqOMo)。
~~~
function heapSort(arr) {
let heapSize = arr.length,
temp;
//建堆
for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
heapify(arr, i, heapSize);
}
//堆排序
for (let j = heapSize - 1; j >= 1; j--) {
temp = arr[0];
arr[0] = arr[j];
arr[j] = temp;
heapify(arr, 0, --heapSize);
}
return arr;
}
~~~
**3）应用**
  堆有几个非常重要的应用，例如优先级队列、求Top K和求中位数。例题：[703\. 数据流中的第K大元素](https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/)，[剑指 Offer 41. 数据流中的中位数](https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/)。
  其中求中位数的方法很巧妙，会维护两个堆：大顶堆和小顶堆。大顶堆中存储前半部分数据，小顶堆中存储后半部分数据，且小顶堆中的数据都大于大顶堆中的数据。如果有 n 个数据：
  （1）当 n 是偶数时，前 2/n 个数据存储在大顶堆中，后 2/n 个数据存储在小顶堆中。
  （2）当 n 是奇数时，大顶堆就存储 2/n+1 个数据，小顶堆中就存储 2n 个数据。
  这样，大顶堆中的堆顶元素就是要找的中位数。
*****
> 原文出处：
[博客园-数据结构和算法躬行记](https://www.cnblogs.com/strick/category/1809992.html)
已建立一个微信前端交流群，如要进群，请先加微信号freedom20180706或扫描下面的二维码，请求中需注明“看云加群”，在通过请求后就会把你拉进来。还搜集整理了一套[面试资料](https://github.com/pwstrick/daily)，欢迎阅读。
推荐一款前端监控脚本：[shin-monitor](https://github.com/pwstrick/shin-monitor)，不仅能监控前端的错误、通信、打印等行为，还能计算各类性能参数，包括 FMP、LCP、FP 等。
- ES6
- 1、let和const
- 2、扩展运算符和剩余参数
- 3、解构
- 4、模板字面量
- 5、对象字面量的扩展
- 6、Symbol
- 7、代码模块化
- 8、数字
- 9、字符串
- 10、正则表达式
- 11、对象
- 12、数组
- 13、类型化数组
- 14、函数
- 15、箭头函数和尾调用优化
- 16、Set
- 17、Map
- 18、迭代器
- 19、生成器
- 20、类
- 21、类的继承
- 22、Promise
- 23、Promise的静态方法和应用
- 24、代理和反射
- HTML
- 1、SVG
- 2、WebRTC基础实践
- 3、WebRTC视频通话
- 4、Web音视频基础
- CSS进阶
- 1、CSS基础拾遗
- 2、伪类和伪元素
- 3、CSS属性拾遗
- 4、浮动形状
- 5、渐变
- 6、滤镜
- 7、合成
- 8、裁剪和遮罩
- 9、网格布局
- 10、CSS方法论
- 11、管理后台响应式改造
- React
- 1、函数式编程
- 2、JSX
- 3、组件
- 4、生命周期
- 5、React和DOM
- 6、事件
- 7、表单
- 8、样式
- 9、组件通信
- 10、高阶组件
- 11、Redux基础
- 12、Redux中间件
- 13、React Router
- 14、测试框架
- 15、React Hooks
- 16、React源码分析
- 利器
- 1、npm
- 2、Babel
- 3、webpack基础
- 4、webpack进阶
- 5、Git
- 6、Fiddler
- 7、自制脚手架
- 8、VSCode插件研发
- 9、WebView中的页面调试方法
- Vue.js
- 1、数据绑定
- 2、指令
- 3、样式和表单
- 4、组件
- 5、组件通信
- 6、内容分发
- 7、渲染函数和JSX
- 8、Vue Router
- 9、Vuex
- TypeScript
- 1、数据类型
- 2、接口
- 3、类
- 4、泛型
- 5、类型兼容性
- 6、高级类型
- 7、命名空间
- 8、装饰器
- Node.js
- 1、Buffer、流和EventEmitter
- 2、文件系统和网络
- 3、命令行工具
- 4、自建前端监控系统
- 5、定时任务的调试
- 6、自制短链系统
- 7、定时任务的进化史
- 8、通用接口
- 9、微前端实践
- 10、接口日志查询
- 11、E2E测试
- 12、BFF
- 13、MySQL归档
- 14、压力测试
- 15、活动规则引擎
- 16、活动配置化
- 17、UmiJS版本升级
- 18、半吊子的可视化搭建系统
- 19、KOA源码分析（上）
- 20、KOA源码分析（下）
- 21、花10分钟入门Node.js
- 22、Node环境升级日志
- 23、Worker threads
- 24、低代码
- 25、Web自动化测试
- 26、接口拦截和页面回放实验
- 27、接口管理
- 28、Cypress自动化测试实践
- 29、基于Electron的开播助手
- Node.js精进
- 1、模块化
- 2、异步编程
- 3、流
- 4、事件触发器
- 5、HTTP
- 6、文件
- 7、日志
- 8、错误处理
- 9、性能监控（上）
- 10、性能监控（下）
- 11、Socket.IO
- 12、ElasticSearch
- 监控系统
- 1、SDK
- 2、存储和分析
- 3、性能监控
- 4、内存泄漏
- 5、小程序
- 6、较长的白屏时间
- 7、页面奔溃
- 8、shin-monitor源码分析
- 前端性能精进
- 1、优化方法论之测量
- 2、优化方法论之分析
- 3、浏览器之图像
- 4、浏览器之呈现
- 5、浏览器之JavaScript
- 6、网络
- 7、构建
- 前端体验优化
- 1、概述
- 2、基建
- 3、后端
- 4、数据
- Web优化
- 1、CSS优化
- 2、JavaScript优化
- 3、图像和网络
- 4、用户体验和工具
- 5、网站优化
- 6、优化闭环实践
- 数据结构与算法
- 1、链表
- 2、栈、队列、散列表和位运算
- 3、二叉树
- 4、二分查找
- 5、回溯算法
- 6、贪心算法
- 7、分治算法
- 8、动态规划
- 程序员之路
- 大学
- 2011年
- 2012年
- 2013年
- 2014年
- 项目反思
- 前端基础学习分享
- 2015年
- 再一次项目反思
- 然并卵
- PC网站CSS分享
- 2016年
- 制造自己的榫卯
- PrimusUI
- 2017年
- 工匠精神
- 2018年
- 2019年
- 前端学习之路分享
- 2020年
- 2021年
- 2022年
- 日志
- 2020