树的基本概念
树是n个节点组成的有限集，n为0，则称为空树。非空树有以下特点：
- 有且仅有一个根节点（root）；
- n > 1，其余节点可分为m（m>0）个互不相交的有限集，每个集合本身又是一个棵树。
其他概念
- 叶子节点（leaf）：树的末尾，没有子节点；
- 父节点
- 孩子节点
- 兄弟节点
- 树的高度/深度：树的最大层级
二叉树
这棵树的节点最多只有2个子节点，也可能为0或1。
- 左孩子
- 右孩子
两个孩子节点的顺序不可颠倒，是有序的。
两种特殊形态
-
满二叉树：除叶子节点外，其他节点都包含左右孩子；
image.png - 完全二叉树：从左到右，每一层级的节点编号，顺序相加，到最后一个节点的编号与满二叉树的编号相同。也就是虽然不满，但是不残
image.png
表现形式
-
链式结构：树的节点之间的关系是指向关系，所以跟链表中的next和prev指针非常相似，用链表来实现二叉树的结构非常直观。
image.png - 数组：将二叉树的每个节点依次在数组中存放，如果某一个节点的孩子节点为空，那在数组中也需要为其留下相应的位置。对于较为稀疏的二叉树来说，这样非常浪费内存空间。
image.png
可以得出：
- 已知父节点的索引为parent，则其左孩子索引为：2 * parent + 1；
- 已知左孩子节点索引为：child，则父节点的索引为：(child - 1) / 2。
二叉树的应用：
-
查找：
查找二叉树：- 若左子树不为空，则其值都小于根节点；
- 若右子树不为空，则其值都大于根节点；
- 左右子树也都是查找二叉树。
image.png对于一个分布相对均匀的查找二叉树来说，若节点总数n，寻找一个子节点的时间复杂度为O(logn)，和树的深度一样。
这个依靠比较大小来查找的过程与二分查找非常类似。
-
维持相对顺序：
这个特点其实就是二叉查找树的规则，左子树值小于父节点，右子树值大于父节点。
这样其实很容易出现一个问题，导致二叉树单边的深度越来越大，查找节点的时间复杂度也变为了O(n)：
image.png
这时就需要二叉树的自平衡了，具体红黑树、AVL树、树堆可以实现。
二叉树的遍历
- 深度优先遍历：
- 先序遍历：根、左、右
- 中序遍历：左、根、右
- 后序遍历：左、右、根
代码实现： - 递归：
class TreeNode { data = null; leftChild: TreeNode = null; rightChild: TreeNode = null; constructor(data) { this.data = data; } } function createTree(list: number[]) { let node: TreeNode = null; if (!list.length) { return null; } const data = list[0]; list.splice(0, 1); if (data) { node = new TreeNode(data); node.leftChild = createTree(list); node.rightChild = createTree(list); } return node; } function consoleData(node: TreeNode) { if (node) { console.log(node.data); consoleData(node.leftChild); consoleData(node.rightChild); } } function main() { const tree = createTree([3, 2, 9, null, null, 10, null, null, 8, null, 4]); /* * 深度优先遍历生成的二叉树： * 3 * / \ * 2 8 * / \ / \ * 9 10 null 4 * / \ / \ * null null null null * */ consoleData(tree); } main();- 栈（用数组实现，先序遍历为例，栈内元素入队时相当于遍历一次，从左子节点开始遍历，当一个元素左右子节点均为null，则需要回溯到该节点的父节点，再遍历右子节点，以此类推，直至栈空）：
import {createTree, TreeNode} from "./recursive"; function consoleByStack(root: TreeNode) { const stack: TreeNode[] = []; let node: TreeNode = root; while (node || stack.length) { // 遍历左子树 while (node) { console.log("遍历：", node.data); stack.push(node); node = node.leftChild; } // 开始遍历右子树 if (stack.length) { node = stack.pop(); node = node.rightChild; } } } function main() { consoleByStack(createTree([3, 2, 9, null, null, 10, null, null, 8, null, 4])) } main();也按照树的结构深度遍历出来了
image.png
- 广度优先遍历
横向优先，其中比较重要的概念是，在一层遍历中，当一个元素被遍历，其左右子节点优先准备在下一轮遍历（进入遍历队列）- 队列实现：
function consoleByQueue(root: TreeNode) { const queue: TreeNode[] = []; queue.push(root); while (queue.length) { const node = queue.shift(); console.log("遍历：", node.data); if (node.leftChild) { queue.push(node.leftChild); } if (node.rightChild) { queue.push(node.rightChild); } } }
二叉堆
什么是二叉堆
- 完全二叉树
- 最大堆：每个节点的左右子节点都小于该节点的值
- 最小堆：每个节点的左右子节点都大于该节点的值
- 堆顶：二叉堆的根节点
二叉堆的自我调整
- 插入节点（O(logn)）
二叉堆插入节点时，插入位置是完全二叉树的最后一个节点，此时需要根据是最大堆还是最小堆，移动节点的位置（对比、上浮交换节点）使其成为一个二叉堆； - 删除节点（O(logn)）
二叉堆删除节点与插入相反，是从堆顶开始删除，然后将完全二叉树的最后一个位置节点移动到堆顶，再层层对比，进行位置的调整，直至形成一个二叉堆。 - 构建二叉堆（O(n)）
一个无序二叉树，依次调节其中非叶子节点的位置，上下移动，直至形成一个二叉堆。
二叉堆的存储是顺序存储，也就是存储在数组中，通过完全二叉树的索引计算公式，知道一个父节点的索引，就能得出其左右子节点的索引，反之亦然。
优先队列
- 最大优先队列：不遵循FIFO原则，队列中每次出队都是最大的元素；
可以利用最大堆来实现，入队操作可以看成插入节点（最后位置插入），出队操作就是删除堆顶，再自我调节。 - 最小优先队列：不遵循FIFO原则，队列中每次出队都是最小的元素；
以实现最大堆为例，代码如下：
class PriorityQueue {
array: number[] = [];
public enQueue(item: number) {
this.array.push(item);
this.upAdjust();
}
public deQueue() {
this.array[0] = this.array[this.array.length - 1];
this.array.pop();
this.downAdjust();
}
public downAdjust() {
const size = this.array.length;
if (size == 0) {
return;
}
let parentIndex = 0;
const target = this.array[parentIndex];
// 最大堆应该寻找左右子节点中的较大的一方进行位置交换
// 先左
let childIndex = parentIndex * 2 + 1;
while (childIndex < size) {
// 右子节点存在，且大于左子节点
if (childIndex + 1 < size && this.array[childIndex+1] > this.array[childIndex]) {
childIndex += 1;
}
if (target >= this.array[childIndex]) {
break;
}
this.array[parentIndex] = this.array[childIndex];
parentIndex = childIndex;
// 还是默认先左子节点
childIndex = parentIndex * 2 + 1;
}
this.array[parentIndex] = target;
}
public upAdjust() {
const size = this.array.length;
let childIndex = size - 1;
// 只有一个元素
if (childIndex == 0) {
return;
}
// 目标元素
const target = this.array[childIndex];
let parentIndex = Math.floor((childIndex - 1) / 2);
while (childIndex > 0 && target > this.array[parentIndex]) {
this.array[childIndex] = this.array[parentIndex];
childIndex = parentIndex;
parentIndex = Math.floor((childIndex - 1) / 2);
}
this.array[childIndex] = target;
}
}
function main() {
const queue: PriorityQueue = new PriorityQueue();
queue.enQueue(3);
queue.enQueue(5);
queue.enQueue(10);
queue.enQueue(2);
queue.enQueue(2);
queue.enQueue(9);
queue.enQueue(7);
console.log(queue.array);
queue.deQueue();
console.log(queue.array);
queue.deQueue();
console.log(queue.array);
}
main();
输出结果：
image.png
