二叉树的深度广度遍历
Liuyi 2020-10-17 数据结构, 二叉树
# JS 中的二叉树的深度遍历与广度遍历
栈,队列,链表等数据结构都是顺序数据结构。而数是分顺序数据结构。树形结构是一类非线性结构。直观地,树型结构是以分支关系定义的层次结构。
# 树的简介
- 树有两种储存结构,一种是顺序储存,一种是链式储存。
- 树的节点拥有的字树数成为结点的度,度为0的节点称为叶子(Leaf)合作和终端结点,树的度是树内各结点的最大值。
- 结点的层次(Level)从跟开始定义起,根为第一层,根的孩子为第二层。若某结点在第l层,则其子树在第l+1层。树中节点的最大层次称为树的深度或高度。
- 如果树的结点的各子树从左至右是有次序的(既不能交换),则称改树为有序树,否则称为无序树。
- 森林(Forest)是m(m >= 0)棵互不相交的树的集合。对树中每个结点而言,其子树的集合即为森林
- 二叉树(Binary Tree) 是另一种树形结构,它的特点是每个节点至多只有两棵子树,并且二叉树子树有左右之分其次序不能颠倒
# 二叉树
- 在二叉树的第i层上至多有$2^i-1$
- 深度为k的二叉树至多有2^k-1个结点
- 对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0 = n2 + 1;
- 一棵深度为k且有2^k - 1个结点的二叉树称为满二叉树。
- 深度为k的,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称之为完全二叉树。
# 完全二叉树
- 具有n个结点的完全二叉树的深度为
Math.floor($\log_2 10$)+1
; - …
# 二叉树的遍历
- 深度遍历
- 先序遍历: 访问根根结点 -> 访问左子树 -> 访问右子树。 前序遍历适合用来显示目录结构
- 中序遍历: 访问左子树 -> 访问根节点 -> 访问右子树。 可以用来实现表达式书在编译器底层很有用
- 后续遍历: 访问左子树 -> 访问右子树 -> 访问根结点。 可以用来实现计算机内的文件及其信息
- 广度遍历 按照层次一层层遍历
先序遍历
递归遍历
var res = []
function dfs(nodes) {
if(nodes) {
res.push(nodes.value)
dfs(nodes.left)
dfs(nodes.right)
}
}
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
非递归遍历
function dfs(node) {
let res = []
let stack = []
stack.push(node)
while(stack.length) {
let node = stack.pop()
res.push(node.value)
if(node.right) stack.push(node.right)
if(node.left) stack.push(node.left)
}
return res
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
中序遍历
递归遍历:
var res = []
function dfs(nodes) {
if(nodes) {
dfs(nodes.left)
res.push(nodes.value)
dfs(nodes.right)
}
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
非递归遍历:
function dfs(node) {
let res = []
let stack = []
while(stack.length || node) {
if(node) {
stack.push(node)
node = node.left
} else {
node = stack.pop()
res.push(node.value)
node = node.right
}
}
return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
后序遍历
递归遍历
var res = []
function dfs(nodes) {
if(nodes) {
dfs(nodes.left)
dfs(nodes.right)
res.push(nodes.value)
}
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
非递归遍历:
unction dfs(node) {
let result = [];
let stack = [];
stack.push(node);
while(stack.length) {
// 不能用node.touched !== ‘left’ 标记‘left’做判断,
// 因为回溯到该结点时,遍历右子树已经完成,该结点标记被更改为‘right’ 若用标记‘left’判断该if语句会一直生效导致死循环
if(node.left && !node.touched) { // 不要写成if(node.left && node.touched !== ‘left’)
// 遍历结点左子树时,对该结点做 ‘left’标记;为了子结点回溯到该(双亲)结点时,便不再访问左子树
node.touched = ‘left’;
node = node.left;
stack.push(node);
continue;
}
if(node.right && node.touched !== ‘right’) { // 右子树同上
node.touched = ‘right’;
node = node.right;
stack.push(node);
continue;
}
node = stack.pop(); // 该结点无左右子树时,从栈中取出一个结点,访问(并清理标记)
node.touched && delete node.touched; // 可以不清理不影响结果 只是第二次对同一颗树再执行该后序遍历方法时,结果就会出错啦因为你对这棵树做的标记还留在这棵树上
result.push(node.value);
node = stack.length ? stack[stack.length - 1] : null;
//node = stack.pop(); 这时当前结点不再从栈中取(弹出),而是不改变栈数据直接访问栈中最后一个结点
//如果这时当前结点去栈中取(弹出)会导致回溯时当该结点左右子树都被标记过时 当前结点又变成从栈中取会漏掉对结点的访问(存入结果数组中)
}
return result; // 返回值
}
dfs(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
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
广度优先遍历
递归遍历:
let result = [];
let stack = [tree]; // 先将要遍历的树压入栈
let count = 0; // 用来记录执行到第一层
let bfs = function () {
let node = stack[count];
if(node) {
result.push(node.value);
if(node.left) stack.push(node.left);
if(node.right) stack.push(node.right);
count++;
bfs();
}
}
dfc();
console.log(result);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
非递归遍历:
1.
function bfs(node) {
let result = [];
let queue = [];
queue.push(node);
let pointer = 0;
while(pointer < queue.length) {
let node = queue[pointer++]; // // 这里不使用 shift 方法(复杂度高),用一个指针代替
result.push(node.value);
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
return result;
}
bfs(tree);
2.
function bfs(node) {
let result = [];
let queue = [];
queue.push(node);
let pointer = 0;
while(pointer < queue.length) {
let node = queue[pointer++]; // // 这里不使用 shift 方法(复杂度高),用一个指针代替
result.push(node.value);
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
return result;
}
bfs(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
35
36
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