最近在复习二叉树的一些概念，二叉树的遍历可以通过递归实现，递归的问题在于如果数据量过大，会造成函数的执行栈溢出，chrome v8引擎下执行栈大概超出10000次就会提示报错。下面是利用栈先进先出的概念，模拟递归的思想，简单记录，温故而知新。
创建节点Class
1
2
3
4
5
6
7
| class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
|
生成二叉树逻辑
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 defaultCompare(next, pre) {
return next - pre;
}
class binarySearchTree {
constructor(compareFn = defaultCompare) {
this.compareFn = compareFn;
this.root = null;
}
insert(value) {
if (this.root === null) {
this.root = new Node(value)
}else {
this.insertNode(value, this.root)
}
}
insertNode(value, node) {
if (this.compareFn(value, node.value) < 0) {
if (node.left === null) {
node.left = new Node(value)
}else {
this.insertNode(value, node.left)
}
}else {
if (node.right === null) {
node.right = new Node(value)
}else {
this.insertNode(value, node.right)
}
}
}
}
|
创建二叉树实例
1
2
3
4
5
6
|
const tree = new binarySearchTree();
tree.insert(1);
tree.insert(5)
|
先序遍历
根-左-右：先访问根节点，再对根节点的左子树进行先序遍历，最后对根节点的右子树进行先序遍历（应用：打印结构文档）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
preOrderTraverse(root = this.root, callback = (n) => console.log(n)) {
if (!root) return;
const stack = [root];
while (stack.length) {
const cur = stack.pop();
callback(cur.value);
if (cur.right) stack.push(cur.right);
if (cur.left) stack.push(cur.left);
}
}
|
中序遍历
左-根-右：先对根节点的左子树进行中序遍历，再访问根节点，最后对根节点的右子树中序遍历（应用：排序，从小到大）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
inOrderTraverse(root = this.root, callback = (n) => console.log(n)) {
if (!root) return;
const stack = [];
let p = root;
while(stack.length || p) {
while(p) {
stack.push(p)
p = p.left
}
const cur = stack.pop();
callback(cur.value);
p = cur.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
|
postOrderTraverse(root = this.root, callback = (n) => console.log(n)) {
if (!root) return;
const stack = [root];
const list = [];
while(stack.length) {
const node = stack.pop();
list.unshift(node.value);
node.left && stack.push(node.left);
node.right && stack.push(node.right);
}
while(list.length) {
const target = list.pop();
callbacl(target.value)
}
}
|