# 一、简介
# 1. 基础概念
# 节点高度
节点到叶子节点的最长路径
# 节点深度
根节点到这个节点所经历的边的个数
# 节点的层数
节点深度+1
# 树的高度
根节点的高度
# 2. 类型
# 二叉树
每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点
# 满二叉树
叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点
# 完全二叉树
叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大
# 3. 存储方法
# 二叉链式存储法
该方法基于指针更常用，每个节点有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针。我们只要拎住根节点，就可以通过左右子节点的指针，把整棵树都串起来。
# 顺序存储法
该方法基于数组基于数组
# 4. 遍历方法
# 前序遍历
对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
# 中序遍历
对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。
# 后序遍历
对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。
# 二、思考题
# 1. BFS广度优先
// 依次遍历根节点，然后是左孩子和右孩子,先进先出
// 广度优先遍历的递归写法
function wideTraversal(node) {
let nodes = [];
let i = 0
if (node != null) {
nodes.push(node)
wideTraversal(node.nextElementSibling)
node = nodes[i++]
wideTraversal(node.firstElementChild)
}
return nodes
}
// 广度优先遍历的非递归写法
function wideTraversal1(node) {
let nodes = [];
let i = 0
while (node != null) {
nodes.push(node)
node = nodes[i++]
let childrens = node.children
for (let i = 0; i < childrens.length; i++) {
nodes.push(childrens[i])
}
}
return nodes
}
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
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
# 2. DFS深度优先
// 不撞南墙不回头
// 1.深度优先遍历的递归写法
function deepTraversal(node) {
let nodes = []
if (node != null) {
nodes.push(node)
let childrens = node.children
for (let i = 0; i < childrens.length; i++) {
deepTraversal(childrens[i])
}
}
return nodes
}
// 2.深度优先遍历的非递归写法
function deepTraversal1(node) {
let nodes = []
if (node != null) {
let stack = [] // 同来存放将来要访问的节点
stack.push(node)
while (stack.length !== 0) {
let item = stack.pop() // 正在访问的节点
nodes.push(item)
let childrens = item.children
for (let i = childrens.length - 1; i >= 0; i--) { // 将现在访问点的节点的子节点存入stack，供将来访问
stack.push(childrens[i])
}
}
}
return nodes
}
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
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