0%

二叉树学习笔记

二叉树数据结构的学习与笔记。

二叉树的储存结构

二叉树有两种储存方式,一种是顺序储存结构,一种是链式储存结构。

顺序储存结构就是二叉树从上至下,每层从左到右给树中节点进行编号:

1
[0,1,2,3,4,5,6]

0 是根节点,1 是根的左节点,2 是根的右节点,3 是根的左节点的左节点,4 是根的左节点的右节点…… 依照这个顺序排列下去。设 i 为顺序表中节点的索引, Qi 代表顺序表上储存的节点, n 为顺序表的长度,则可知:

  1. i = 0Qi 节点是根节点
  2. 2i+1 < n, 则索引 2i+1 上储存的是 Qi 的左节点。反之,则没有节点。
  3. 2i+2 < n, 则索引 2i+2 上储存的是 Qi 的右节点。反之,则没有节点。
  4. **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. 左右子树各是一颗二叉排序树。

以下为创建二叉排序树的代码:

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。
「请笔者喝杯奶茶鼓励一下」

欢迎关注我的其它发布渠道