树
大约 14 分钟
树
二叉树
二叉树是一种非线性数据结构，代表“祖先”与“后代”之间的派生关系，体现了“一分为二”的分治逻辑。与链表类似，二叉树的基本单位是节点，每个节点包含值、左子节点、右子节点三个部分。
class TreeNode {
value; // 节点值
left; // 左子节点引用
right; // 右子节点引用
constructor(value, left, right) {
this.value = value === undefined ? 0 : value;
this.left = left === undefined ? 0 : left; // 0 表示不存在子节点
this.right = right === undefined ? 0 : right; // 0 表示不存在子节点
}
}
每个节点都有两个引用，分别指向左子节点和右子节点，该节点被称为这两个子节点的父节点。当给定一个二叉树的节点时，我们将该节点的左子节点及其以下的节点形成的树称为该节点的“左子树”，同理可得“右子树”。在二叉树中，除“叶节点外”，其他所有的节点都包含子节点和非空子树。
二叉树常见术语
- 根节点：位于二叉树顶层的节点，没有父节点。
- 叶节点：没有子节点的节点，其两个引用均指向None。
- 边：连接两个节点的线段，即节点引用。
- 节点所在的层：从顶至底递增，根节点所在层为1。
- 节点的度：节点的子节点的数量，在二叉树中，度的取值范围为0、1、2。
- 二叉树的高度：从根节点到最远叶节点所经过的边的数量。
- 节点的深度：从根节点到该节点所经过的边的数量。
- 节点是高度：从距离该节点最远的叶节点到该节点所经过的边的数量。
二叉树基本操作
1. 初始化二叉树
与链表类似，先初始化节点，然后构建引用。
// 初始化二叉树
let n1 = new TreeNode(1),
n2 = new TreeNode(2),
n3 = new TreeNode(3),
n4 = new TreeNode(4),
n5 = new TreeNode(5);
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;
2. 插入与删除节点
与链表类似，在二叉树中插入和删除节点可以通过修改指针来实现。
// 插入p到n1的左子树
let p = new TreeNode(0);
n1.left = p;
p.left = n2;
// 删除p
n1.left = n2;
删除节点，通常意味着删除该节点及其所有子树。
常见二叉树类型
完美二叉树
完美二叉树所有层的节点都被完全填满，在完美二叉树中叶节点的度为0，其余节点的度均为2.若树的高度为h，则节点总数为2^h-1，呈指数级关系，反映了细胞分裂现象。
完全二叉树
完全二叉树只有最底层的节点未被填满，且最底层节点尽量靠左填充。
完满二叉树
完满二叉树除了叶节点外，其余节点均有两个子节点。
平衡二叉树
平衡二叉树中任意节点的左子树与右字数的高度之差的绝对值不超过1。
二叉树的退化
当二叉树的每层节点都被填满时，达到“完美二叉树”，而当所有节点都偏向于一侧时，二叉树退化为“链表”。
- 完美二叉树是理想情况，可以充分发挥二叉树“分治”的优势。
- 退化为链表时，是另外的一种极端情况，各项操作都变为线性操作，时间复杂度退化为O(n)。
二叉树遍历
从物理结构的角度来看，树是一种基于链表的数据结构，因此其遍历方式是通过指针逐个访问节点。然而树是一种非线性数据结构，这就使得遍历树相对于遍历链表更加复杂，通常需要借助搜索算法来实现。
二叉树的常见遍历包括层序遍历、前序遍历、中序遍历、后序遍历。
层序遍历
层序遍历从顶部到底部逐层遍历二叉树，并在每一层按照从左到右顺序访问节点。层序遍历本质上属于广度优先搜索，体现了一圈一圈向外扩展的逐层遍历方式。
// 层序遍历
function levelOrder(root) {
// 初始化队列，加入根节点
const queue = [root];
// 初始化列表，存储节点数据
const list = [];
while (queue.length) {
let node = queue.shift(); // 取出队列头部元素
list.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
return list;
}
复杂度分析：
- 时间复杂度为O(n)：所有节点被访问一次，使用O(n)的时间，n为节点数量。
- 空间复杂度为O(n)：在最差情况下，即满二叉树时遍历到最底层之前，队列中最多存在(n+1)/2个节点，占用O(n)的空间。
前序、中序、后序遍历
前序、中序、后续遍历都属于深度优先遍历，也称为深度优先搜索，体现出了一种“先走到尽头，再回溯继续”的遍历方式。深度优先遍历就像是绕着整颗二叉树的外围走了一圈，每个节点都会遇到三个位置，分别对应前序遍历、中序遍历和后续遍历。
// 前序遍历
let list = [];
function preOrder(root) {
if (root === null) return;
// 访问顺序：根->左子树->右子树
list.push(root.val);
preOrder(root.left);
preOrder(root.right);
}
// 中序遍历
function inOrder(root) {
if (root === null) return;
// 访问顺序：左子树->根->右子树
inOrder(root.left);
list.push(root.val);
inOrder(root.right);
}
// 后序遍历
function postOrder(root) {
if (root === null) return;
// 访问顺序：左字数->右子树->根
postOrder(root.left);
postOrder(root.right);
list.push(root.val);
}
时间复杂度分析：
- 时间复杂度为O(n)：所有节点被访问一次，使用O(n)的时间。
- 空间复杂度为O(n)：再最差情况下，即树退化为链表时，递归深度达到n，系统占用空间为O(n)。
二叉树数组表示
在链表表示下，二叉树的存储单元为节点TreeNode，节点之间通过指针相连接，如何使用数组来表示二叉树呢？
表示完美二叉树
给定一颗完美二叉树，将所有节点按层序遍历的顺序存储在一个数组中，每个节点都对应唯一的数组索引。
依据层序遍历的特性，可以推导出父节点索引与子节点索引之间的映射公式：若某节点的索引为i，则该节点的左子节点索引为2i+1，右子节点的索引为2i+2。
映射公式的角色相当于链表中的节点引用（指针）。给定数组中的任意一个节点，我们都可以通过映射公式来访问它的左（右）子节点。
表示任意二叉树
完美二叉树是一个特性，在二叉树中间层通常存在众多的None，层序遍历时并不包含None，因此无法正确表示二叉树。
为了解决问题，我们在层序遍历中显式的写出所有的None，这样就可以表示唯一的二叉树了。
// 二叉树的数组表示
let tree = [1, 2, 3, 4, null, 6, 7, 8, 9, null, null, 12, null, null, 15];
完全二叉树时，None只会出现在最底层且靠右的位置，因此None一定会出现在层序遍历序列的末尾，这样就可以忽略None了。
Top-k问题
let nums = [1, 7, 6, 3, 2];
let k = 3; // 获取数组中最大的k个元素
// 方法一：k轮遍历
function topKMap(nums, k) {
let result = [];
let copy = JSON.parse(JSON.stringify(nums));
for (let i = 0; i < k; i++) {
// 将数组中最大push进去, 并在数组中删除
result.push(Math.max(...copy));
copy.splice(copy.indexOf(Math.max(...copy)), 1);
}
console.log(result);
return result;
}
topKMap(nums, k);
// 方法二：排序
function topKSort(nums, k) {
let result = [];
let copy = JSON.parse(JSON.stringify(nums));
// 从大到小排序
copy.sort((a, b) => b - a);
// 取0~k索引位置元素
result = copy.slice(0, k);
console.log(result);
return result;
}
topKSort(nums, k);
// 方法三：堆
class MaxHeap {
heap;
constructor(heap) {
this.heap = heap || []; // 初始化堆
}
/* 获取左子节点索引 */
getLeftIndex = (i) => i * 2 + 1;
/* 获取右子节点索引 */
getRightIndex = (i) => i * 2 + 2;
/* 获取父节点索引 */
getParentIndex = (i) => Math.floor((i - 1) / 2);
/* 获取堆顶元素 */
peek = () => this.heap[0];
/* 获取大小 */
size = () => this.heap.length;
/* 堆化 */
shiftUp = (i) => {
while (true) {
// 当前节点小于父节点，则交换
if (this.heap[i] <= this.heap[this.getParentIndex(i)]) {
// 交换
this.swap(i, this.getParentIndex(i));
// 继续向上堆化
i = this.getParentIndex(i);
} else {
break;
}
}
};
/* 元素入堆 */
push = (val) => {
this.heap.push(val);
// 开始堆化
this.shiftUp(this.size() - 1);
};
/* 交换元素 */
swap = (i, p) => {
[this.heap[i], this.heap[p]] = [this.heap[p], this.heap[i]];
};
// 堆顶出堆
pop = () => {
if (this.heap.length === 0) return "堆为空";
// 交换堆顶与堆底元素
this.swap(0, this.size() - 1);
// 删除堆底元素（原堆顶元素）
this.heap.pop();
};
}
function topKHeap(nums, k) {
let heap = new MaxHeap([]);
// 将前k项入堆
for (let i = 0; i < k; i++) {
// 1 7 6 建堆
heap.push(nums[i]);
}
// 从k+1项开始，若当前元素大于堆顶元素，则堆顶元素出堆，该元素入堆
for (let j = k; j < nums.length; j++) {
if (nums[j] > heap.peek()) {
// 堆顶出堆
heap.pop();
// 该元素入堆
heap.push(nums[j]);
}
}
console.log(heap.heap);
}
topKHeap(nums, k);
/**
* 以下代码实现了一棵基于数组表示的二叉树，包括以下几种操作:
* 给定某节点，获取它的值、左（右）子节点、父节点。
* 获取前序遍历、中序遍历、后序遍历、层序遍历序列。
*/
/* 数组表示下的二叉树类 */
class ArrayBinaryTree {
tree;
/* 构造方法 */
constructor(arr) {
this.tree = arr;
}
/* 列表容量 */
size() {
return this.tree.length;
}
/* 获取索引为 i 节点的值 */
val(i) {
// 若索引越界，则返回 null ，代表空位
if (i < 0 || i >= this.size()) return null;
return this.tree[i];
}
/* 获取索引为 i 节点的左子节点的索引 */
left(i) {
return 2 * i + 1;
}
/* 获取索引为 i 节点的右子节点的索引 */
right(i) {
return 2 * i + 2;
}
/* 获取索引为 i 节点的父节点的索引 */
parent(i) {
return Math.floor((i - 1) / 2); // 向下整除
}
/* 层序遍历 */
levelOrder() {
let res = [];
// 直接遍历数组
for (let i = 0; i < this.size(); i++) {
if (this.val(i) !== null) res.push(this.val(i));
}
return res;
}
/* 深度优先遍历 */
dfs(i, order, res) {
// 若为空位，则返回
if (this.val(i) === null) return;
// 前序遍历
if (order === 'pre') res.push(this.val(i));
this.dfs(this.left(i), order, res);
// 中序遍历
if (order === 'in') res.push(this.val(i));
this.dfs(this.right(i), order, res);
// 后序遍历
if (order === 'post') res.push(this.val(i));
}
/* 前序遍历 */
preOrder() {
const res = [];
this.dfs(0, 'pre', res);
return res;
}
/* 中序遍历 */
inOrder() {
const res = [];
this.dfs(0, 'in', res);
return res;
}
/* 后序遍历 */
postOrder() {
const res = [];
this.dfs(0, 'post', res);
return res;
}
}
优先与局限性
二叉树的数组表示主要有以下优点：
- 数组存储在连续的内存空间中，对缓存友好，访问与遍历速度较快。
- 不需要存储指针，比较节省空间。
- 允许随机访问节点。
一些局限性：
- 数组存储需要连续内存空间，因此不适合存储数据量过大的树。
- 增删节点需要通过数组插入与删除操作实现，效率过低。
- 当二叉树中存在大量None时，数组中包含的节点数据比重较低，空间利用率较低。
二叉搜索树
二叉搜索时满足以下条件：
- 对于根节点，左子树所有节点的值 < 根节点的值 < 右子树所有节点的值
- 任意节点的左右子树也是二叉搜索树，满足条件1。
二叉搜索树的操作
将二叉搜索树封装为一个类BinarySearchTree，并声明一个成员变量root，指向树的根节点。
- 查找节点
给定目标值num，从根节点root出发，循环比较节点值cur.val与num之间的大小关系：
- 若cur.val < num，说明目标节点在cur的右子树中，因此cur = cur.right;
- 若cur.val > num，说明目标节点在cur的左子树中，因此cur = cur.left;
- 若cur.val = num，说明找到目标节点，返回cur并跳出循环。
二叉搜索树的查找操作与二分查找算法的工作原理一致，都是每轮排除一半情况。循环次数最多为二叉树的高度，当二叉树平衡时，使用O(logn)的时间复杂度。
/* 查找节点 */
search(num) {
let cur = this.root;
// 循环查找，越过叶节点后跳出
while (cur !== null) {
// 目标节点在 cur 的右子树中
if (cur.val < num) cur = cur.right;
// 目标节点在 cur 的左子树中
else if (cur.val > num) cur = cur.left;
// 找到目标节点，跳出循环
else break;
}
// 返回目标节点
return cur;
}
- 插入节点
给定一个待插入元素num，为了保存二叉搜索树“左子树 < 根节点 < 右子树”的性质，插入操作流程如下：
- 查找插入位置：与查找操作类似，从根节点出发，根据当前节点值与num做对比，循环向下搜索，直到越过叶节点时跳出循环。
- 在该位置插入节点：初始化节点num，将该节点置于None的位置。
注意以下两点：
- 二叉搜索树不允许存在重复节点，否则将违反其定义。因此，若待插入节点在树中已存在，则不执行插入，直接返回。
- 为了实现插入节点，我们需要借助节点 pre 保存上一轮循环的节点。这样在遍历至 None 时，我们可以获取到其父节点，从而完成节点插入操作。
/* 插入节点 */
insert(num) {
// 若树为空，则初始化根节点
if (this.root === null) {
this.root = new TreeNode(num);
return;
}
let cur = this.root,
pre = null;
// 循环查找，越过叶节点后跳出
while (cur !== null) {
// 找到重复节点，直接返回
if (cur.val === num) return;
pre = cur;
// 插入位置在 cur 的右子树中
if (cur.val < num) cur = cur.right;
// 插入位置在 cur 的左子树中
else cur = cur.left;
}
// 插入节点
const node = new TreeNode(num);
if (pre.val < num) pre.right = node;
else pre.left = node;
}
- 删除节点
先从二叉树中查找到目标节点，再将其删除，因为是二叉搜索树，删除节点后还必须保持该特性，因此删除节点分为0、1、2三种情况，具体如下：
当删除节点的度为0时，表示该节点为叶节点，可以直接删除。
当删除节点的度为1时，将待删除节点替换为其子节点即可。
当删除节点的度为2时，不能直接删除该节点，而是需要一个节点替代该节点，由于需要保存二叉搜索树特性，因此这个节点可以是右子树最小节点或左子树最大节点。
/* 删除节点 */
remove(num) {
// 若树为空，直接提前返回
if (this.root === null) return;
let cur = this.root,
pre = null;
// 循环查找，越过叶节点后跳出
while (cur !== null) {
// 找到待删除节点，跳出循环
if (cur.val === num) break;
pre = cur;
// 待删除节点在 cur 的右子树中
if (cur.val < num) cur = cur.right;
// 待删除节点在 cur 的左子树中
else cur = cur.left;
}
// 若无待删除节点，则直接返回
if (cur === null) return;
// 子节点数量 = 0 or 1
if (cur.left === null || cur.right === null) {
// 当子节点数量 = 0 / 1 时， child = null / 该子节点
const child = cur.left !== null ? cur.left : cur.right;
// 删除节点 cur
if (cur !== this.root) {
if (pre.left === cur) pre.left = child;
else pre.right = child;
} else {
// 若删除节点为根节点，则重新指定根节点
this.root = child;
}
}
// 子节点数量 = 2
else {
// 获取中序遍历中 cur 的下一个节点
let tmp = cur.right;
while (tmp.left !== null) {
tmp = tmp.left;
}
// 递归删除节点 tmp
this.remove(tmp.val);
// 用 tmp 覆盖 cur
cur.val = tmp.val;
}
}
- 中序遍历有序
二叉搜索树的特性是“左子树<根<右子树”，而中序遍历顺序是“左根右”，因此中序遍历二叉搜索树时是升序的。
Loading...