二叉树数据结构的学习与笔记。
目录
二叉树的储存结构
二叉树有两种储存方式，一种是顺序储存结构，一种是链式储存结构。
顺序储存结构就是二叉树从上至下，每层从左到右给树中节点进行编号:
0 是根节点，1 是根的左节点，2 是根的右节点，3 是根的左节点的左节点，4 是根的左节点的右节点…… 依照这个顺序排列下去。设 i 为顺序表中节点的索引, Qi 代表顺序表上储存的节点, n 为顺序表的长度，则可知:
i = 0，Qi 节点是根节点- 若
2i+1 < n, 则索引 2i+1 上储存的是 Qi 的左节点。反之，则没有节点。 - 若
2i+2 < n, 则索引 2i+2 上储存的是 Qi 的右节点。反之，则没有节点。 - **
Qi 的双亲节点的索引为 (i-1)/2**。比如 i=4, (i-1)/2 向下取整等于 1, 索引为 4 的双亲节点为 1。
链式储存的结构大致如下:
1
2
3
4
5
6
7
8
9
10
| class TreeNode {
val: number
left: TreeNode | null
right: TreeNode | null
constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
}
|
顺序结构转链式结构
利用二叉树的性质，可以将顺序储存方式转换为对应的链式结构:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| 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 toLinkedListBinaryTree(list) {
// 临时用于储存被转换为链表的节点
const nodelist = [];
for (let i = 0; i < list.length; i++) {
const node = new TreeNode(list[i]);
nodelist.push(node);
// 根节点没有双亲节点
if (i > 0) {
// 由结论 4 可得双亲节点的索引
const parentIdx = Math.floor((i - 1) / 2);
const parent = nodelist[parentIdx];
// 当前层从左向右赋值，若左节点被赋值，则剩下右节点没有被赋值
if (parent.left) {
parent.right = node;
} else {
parent.left = node;
}
}
}
return nodelist.shift()
}
// 在 console 进行测试
cnsole.log(toLinkedListBinaryTree([0,1,2,3,4,5,6,7,8,9]));
|
二叉树的遍历
遍历二叉树是指沿着某条搜索路径周游二叉树，依次对树中的每个节点访问且仅访问一次。
二叉树的遍历方式可以分为递归和非递归方式。遍历算法也可以分为**深度优先搜索 (Depth-First-Search，DFS)和广度优先搜索 (Breadth-First Search)**。
根据二叉树的递归定义，遍历一颗非空二叉树的问题可分为三个子问题: 访问根节点 (D)，遍历左子树 (L)，遍历右子树 (R)。遍历的顺序可分为: DLR (前序)、LDR (中序)、LRD (后序) 和 DRL (前序)、RDL (中序)、RLD (后序)。前三种是先左后右，后三种是先右后左。一般没有提别指明的话，我们谈论二叉树的遍历，都是在讲前三种。
二叉树的前序遍历、中序遍历、后序遍历都可以通过递归方式和非递归方式实现。
前序序遍历
递归形式:
1
2
3
4
5
6
7
8
9
10
11
12
13
| function preorderTraversal(root: TreeNode | null): number[] {
return postorder(root, [])
};
function postorder(root?: TreeNode, result = []): number[] {
if (!root) return result;
result.push(root.val);
postorder(root.left, result);
postorder(root.right, result);
return result;
}
|
中序遍历
递归形式:
1
2
3
4
5
6
7
8
9
10
11
12
13
| function inorderTraversal(root: TreeNode | null): number[] {
return inorder(root, [])
};
function inorder(root?: TreeNode, result = []): number[] {
if (!root) return result;
inorder(root.left, result);
result.push(root.val);
inorder(root.right, result);
return result;
}
|
后序遍历
递归形式:
1
2
3
4
5
6
7
8
9
10
11
12
13
| function postorderTraversal(root: TreeNode | null): number[] {
return postorder(root, [])
};
function postorder(root?: TreeNode, result = []): number[] {
if (!root) return result;
postorder(root.left, result);
postorder(root.right, result);
result.push(root.val);
return result;
}
|
层序遍历
层序遍历就是把二叉树分层，然后每一层从左到右遍历：
![]()
层序遍历二叉树很自然就能想到使用 BFS(广度优先搜索) 来遍历每层。
该算法采用一个队列来缓存二叉树的节点，若树不为空，先将二叉树根节点输出，先将根节点入队，再到循环体内出队。若根节点还有左孩子，则将左孩子也添加到队列中。若有右孩子，也将右孩子也添加到队列中。如此下去，直到队列为空:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| // 按层输出二叉树的值
function levelOrder(root: TreeNode | null) {
if (!root) return;
// 队列，先进先出
const queue = [root];
while (queue.length) {
// 取队首的元素
const node = queue.shift();
console.log('node --> ', node.val)
// 若有左右节点，则添加至队列
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
};
|
若想将每一层的值都存入数组中，则可以采用二维数组进行储存:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| function levelOrder(root: TreeNode | null): number[][] {
if (!root) return [];
// 最终会返回的结果
const result = [];
// 队列，先进先出
const queue = [root];
while (queue.length) {
// 当前层级
const level = [];
// 当前队列的长度
const n = queue.length;
for (let i = 0; i < n; i += 1) {
const node = queue.shift();
level.push(node.val);
// 若有左右节点，则添加至队列
// 由于已经储存上一轮的节点数，因此这里不会影响 n 的值
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(level);
}
return result;
};
|
不考虑副作用的话，可以直接将 root1 作为结果，修改 root1 的值即可。
1
2
3
4
5
6
7
8
9
| function mergeTrees(root1?: TreeNode, root2?: TreeNode): TreeNode | null {
if (!root1 || !root2) return root1 || root2;
root1.val += root2.val;
root1.left = mergeTrees(root1.left, root2.left);
root1.right = mergeTrees(root1.right, root2.right);
return root1;
};
|
二叉排序树 (BST)
二叉排序树(Binary Sort Tree)又称二叉查找树，它是一种特殊的二叉树，它或为空树，或具有以下性质的二叉树:
- 它的右子树非空，则右子树上所有节点的值都大于根节点的值。
- 它的左子树非空，则左子树上所有节点的值都小于根节点的值。
- 左右子树各是一颗二叉排序树。
以下为创建二叉排序树的代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| function sortedArrayToBST(nums: number[]): TreeNode | null {
let tree = null, node;
while(nums.length) {
node = new TreeNode(nums.shift())
tree = insertBST(tree, node)
}
return tree;
};
function insertBST(tree: TreeNode, node: TreeNode) {
let parent, p = tree;
while(p) {
// parent 指向 p 的双亲
parent = p;
// 要插入的节点的值小于 p 的值，赋值为左节点
// 要插入的节点的值大于 p 的值，赋值为右节点
p = node.val < p.val ? p.left : p.right;
}
if (tree == null) return node;
// console.log('p',parent.val, node.val)
if(node.val < parent.val) {
parent.left = node;
} else {
parent.right = node;
}
return tree;
}
|
高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1」的二叉树。
Q: 给定已按升序排序的整数数组，将其构建为二叉树。
A: 因为数组已经排过序了，因此可以直接采用二分法进行构建。先去中间的元素，再向两侧递归构建:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| function sortedArrayToBST(nums: number[]): TreeNode | null {
return dfs(nums, 0, nums.length - 1)
};
function dfs(nums: number[], min: number, max: number): TreeNode | null {
if (min > max) return null;
// 取中间的索引，先减后加的方式可以避免索引值溢出
const mid = min + Math.floor((max - min) / 2);
// 由于是采用二分法，因此左右子树的高度差不会超过 1
const root = new TreeNode(
nums[mid],
dfs(nums, min, mid - 1),
dfs(nums, mid + 1, max)
);
return root;
}
|
判断指定树是否是平衡树
可以采用自底向上进行遍历，该遍历方法类似于后序遍历:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| function isBalanced(root: TreeNode | null): boolean {
return height(root) !== -1;
};
function height(root?: TreeNode) {
if (!root) return 0;
const left = height(root.left);
if (left == -1) return -1;
const right = height(root.right);
if (right == -1) return -1;
// 高度差超过 1
if (Math.abs(left - right) > 1) return -1;
// 当前层 + 1
return Math.max(left, right) + 1;
}
|
- 时间复杂度：O(n)O(n)，其中 nn 是二叉树中的节点个数。使用自底向上的递归，每个节点的计算高度和判断是否平衡都只需要处理一次，最坏情况下需要遍历二叉树中的所有节点，因此时间复杂度是 O(n)O(n)。
- 空间复杂度：O(n)O(n)，其中 nn 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 nn。
登录
