树的概念
-
树是一种非线性数据结构，根据子节点数量可分为 「二叉树」 和 「多叉树」，最顶层的节点称为「根节点 root」；
-
以二叉树为例，每个节点包含三个成员变量：「值 val」、「左子节点 left」、「右子节点 right」；
-
普通二叉树由于结构不规则，不适合使用顺序存储，为了记录节点间的关系，可使用链式存储方式；
分类
二叉搜索树
二叉搜索树 也称为 二叉查找树、二叉排序树，顾名思义是二叉树的特种树，专注于检索，特点是让节点按照数据的一定的规律摆放，从而让搜索某个节点>特别的高效；
特点：
- 左子树上所有结点的值均 小于等于 它的根结点的值；
- 右子树上所有结点的值均 大于等于 它的根结点的值；
- 二叉搜索树的 中序遍历 序列是一个 递增 的序列；
优缺点
- 优点：增删查速度快，平均时间复杂度均为
O(logn)；- 缺点：可能出现类似线性链表的结构，查找的时间复杂度会变成
O(n)；
二叉搜索树的建立
给定一个序列，对序列的每一个元素插入到二叉搜索树（默认二叉搜索树中不存在重复元素）：
- 如果二叉搜索树为空，则该元素即为根结点；
- 如二叉搜索树为非空，该元素值小于根结点值，插入左子树，否则插入右子树；
递归调用，即可建立一棵二叉搜索树；
let insert = function (root, val) {
if (root === null)
root = new TreeNode(val); // 如果根结点为空，则元素为根结点
else if (val < root.val)
insert(root.left, val); // 元素小于根结点值，插入左子树
else
insert(root.right, val); // 如果元素大于根结点值，插入右子树
}
二叉搜索树中查找元素
如果二叉搜索树为空，查找失败；
如给定值与根结点比较，如相等则查找成功，否则继续比较：
- 若给定值小于根结点，则在左子树中继续查找；
- 若给定值大于等于根结点，在右子树中继续查找；
let searchBST = function (root, val) {
// 终止条件
if (root == null) return false;
if (val == root.val)
return true; // 如果查找值与当前结点相等，返回真
else if (val < root.val)
return searchBST(root.left, val); // 如果查找值小于根结点值，在左子树中查找
else
return searchBST(root.right, val); // 如果查找值大于等于根结点值，在右子树中查找
}
二叉搜索平衡树
-
以二叉搜索树为基础，增加平衡的规定：左子树和右子树的高度差不得超过 1 ，并且左右两个子树都是一棵平衡二叉树；通过左旋或右旋两种方法实现平衡二叉树；
-
优点：解决了二叉查找树退化为近似链表的缺点，最坏的查找时间复杂度也为
O(logn)； -
缺点：因为平衡树要求每个节点的左子树和右子树的高度差至多等于 1 ，导致每次进行 插入/删除 节点的时候，很容易会破坏平衡树的平衡的规则，进而需要频繁地通过 左旋 和 右旋 来进行调整，使之再次成为一颗符合要求的平衡树；显然，如果在那种插入、删除很频繁的场景中，平衡树需要频繁进行调整，这会使平衡树的性能大打折扣；
完全二叉树
-
定义：一棵二叉树的深度为 k ，除第 k 层外，其它各层的结点数都达到最大个数，第 k 层所有的结点都连续集中在最左边；
![]( "完全二叉树")
-
节点计算：
层级 节点数 1 2^0 2 2^1 3 2^2 … … k 2^(k-1) -
根据等比数列公式
Sn = a * (1 - r^n) / (1-r)可知深度为 k 的完全二叉树，最多有2^k - 1个节点，最少有(2^k - 1) - 2^(k-1) + 1 => 2^(k-1)个节点（第 k 层只有一个节点）； -
由于完全二叉树的结构连续，有迹可循，可采用顺序存储方式，按照从上到下，从左往右的顺序将节点存储在数组中；
满二叉树
-
一棵二叉树深度为 k 且第 k 层有
2^(k-1)个节点的树是满二叉树（总数为2^k - 1个节点）；
![]( "满二叉树")
-
一颗完全二叉树是可以用数组来存储的，不会浪费内存空间；
- 如下数组，根节点 A 的下标是 0 ，那么它的左孩子就是
(2 * 0 + 1)，右孩子就是(2 * 0 + 2)；const tree = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J']; - 以此类推，0 替换为变量 i 后，就可以推导每个节点的左右孩子，而不需要特别定义节点类，使用两个左右指针去指向左右孩子，这也是一种更高效的存储方案；
- 此处可以延伸到二叉堆，它无论何时都是一颗符合堆的性质的完全二叉树，所以它的最优存储方案就是用数组；
- 如下数组，根节点 A 的下标是 0 ，那么它的左孩子就是
字典树
-
字典树又叫做 trie 树 或 前缀树 ，是一种有序的、用于统计、排序和存储字符串的数据结构；
- 关键字不直接保存在结点中，而是由结点在树中的位置决定，每个结点代表一个字符；
- 根结点代表空字符串，第一层孩子结点到某个标记的结点代表了存储的字符串；
- 一个结点及其所有子孙结点都有相同的前缀，也就是这个结点对应的字符串；
- 只有叶子结点和某些被标记的内部结点，才存储了字符串；
![]( "字典树")
-
优点：
- 字典树最大优点是利用字符串的公共前缀来减少存储空间和查询时间，从而最大限度的减少无谓的字符串比较，是非常高效的字符串查找结构；
- 插入和查找的时间复杂度都可以达到
O(1)；
-
缺点：
- 在工程中，不考虑前缀匹配的话，基本上使用 hash 就能满足；
- 如果考虑前缀匹配的话，工程也不会使用 字典树 ，一旦字符集大小很大的话，字典树 将会带来很大的空间浪费；对于个别的超长字符 字典树 会进一步变深；这时候如果 字典树 是存储在硬盘中，字典树 结构过深带来的影响是多次随机 IO ，随机 IO 是成本很高的操作；
遍历方式
深度优先遍历 DFS
- 前序遍历（先根遍历）
- 中序遍历（中根遍历）
- 后序遍历（后根遍历）
广度优先遍历 BFS
- 层序遍历
构建一颗二叉树
// 新建树节点类
class TreeNode {
constructor(val, left, right) {
this.val = (val === undefined ? 0 : val);
this.left = (left === undefined ? null : left);
this.right = (right === undefined ? null : right);
}
}
// 入参一个数组，生成二叉树
function buildTree(arr) {
// 若没有参数或数组长度为0，则视为空树
if (!arr || arr.length === 0) {
return null;
}
// 先将数组第一个元素 设置为根结点
let root = new TreeNode(arr.shift());
// 节点队列 陆续从数组中为节点添加左右叶子
let nodeQueue = [root];
// 当数组剩余仍有元素，则持续为最近的节点添加叶子
while (arr.length > 0) {
// 从节点数组头部取出节点 为了添加叶子备用
let node = nodeQueue.shift();
// 若数组中无元素，则视为无叶子可添加,返回即可
if (!arr.length) {
break;
}
// 先从节点数组中取一个元素 转化为节点 拼接为左叶子
let left = new TreeNode(arr.shift());
node.left = left;
nodeQueue.push(left);
// 每拼接一片叶子节点 重新判断剩余叶子数量 若无剩余视为拼接完毕
if (!arr.length) {
break;
}
// 左侧叶子拼完，右边一样的操作
let right = new TreeNode(arr.shift());
node.right = right;
nodeQueue.push(right);
}
// 最后返回根结点，通过根结点就能得到整个二叉树的结构
return root;
}
// 测试
let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
console.log(buildTree(arr));
参考资料
算法基础🔮 队列
上一篇
