x-note
Search…
二叉树的遍历
二叉树的遍历
二叉树(Binary Tree)每个节点最多有两个子节点的树型数据结构。
1
class TreeNode {
2
constructor(val, left = null, right = null) {
3
this.val = val;
4
this.left = left;
5
this.right = right;
6
}
7
}
Copied!
二叉树的遍历方式主要分为 深度优先(Deep-first Search, DFS)广度优先(Breadth-first Search,BFS)
其中深度优先遍历有以下几种方法
  1. 1.
    前序遍历
  2. 2.
    中序遍历
  3. 3.
    后序遍历

深度优先

深度优先顾名思义就是先纵向搜索,在进入下一个兄弟节点之前,尽可能的向下搜索每一个子节点。 该算法从根节点开始(在图的情况下选择一些任意节点作为根节点)并在回溯之前尽可能地沿着每个分支进行探索。

前序遍历

前序遍历(pre-order)的访问顺序是 DLR
L 为左子树,R 为右子树,D 为根节点
Could not load image
上图的前序遍历顺序为: ABDGHCEIF

前序遍历的递归方式

1
function preOrder(root) {
2
if (!root) {
3
return;
4
}
5
// do something
6
// console.log(root.val)
7
preOrder(root.left);
8
preOrder(root.right);
9
}
Copied!

前序遍历的非递归方式

对于任一结点 P
  1. 1.
    访问结点 P,并将结点 P 入栈;
  2. 2.
    判断结点 P 的左孩子是否为空,若为空,则取栈顶结点并进行出栈操作,并将栈顶结点的右孩子置为当前的结点 P,循环至 1; 若不为空,则将 P 的左孩子置为当前的结点 P;
  3. 3.
    直到 Pnull 并且栈为空,则遍历结束。
1
function preOrderWithoutRecursion(root) {
2
const stack = [];
3
let node = root;
4
while (node || stack.length > 0) {
5
if (node) {
6
// do something
7
// console.log(node.val);
8
stack.push(node);
9
node = node.left;
10
} else {
11
node = stack.pop().right;
12
}
13
}
14
}
Copied!

中序遍历

中序遍历(in-order)的顺序是 LDR
Could not load image
上图的中序遍历顺序为: GDHBAEICF

中序遍历的递归方式

1
function inOrder(root) {
2
if (!root) {
3
return;
4
}
5
inOrder(root.left);
6
// do something
7
// console.log(root.val);
8
inOrder(root.right);
9
}
Copied!

中序遍历的非递归方式

对于任一结点 P
  1. 1.
    若其左孩子不为空,则将 P 入栈并将 P 的左孩子置为当前的 P,然后对当前结点 P 再进行相同的处理;
  2. 2.
    若其左孩子为空,则取栈顶元素并进行出栈操作,访问该栈顶结点,然后将当前的 P 置为栈顶结点的右孩子;
  3. 3.
    直到 Pnull 并且栈为空则遍历结束
1
function inOrderWithoutRecursion(root) {
2
const stack = [];
3
let node = root;
4
while (node || stack.length > 0) {
5
if (node) {
6
stack.push(node);
7
node = node.left;
8
} else {
9
const lastNode = stack.pop();
10
// do something
11
// console.log(lastNode.val);
12
node = lastNode.right;
13
}
14
}
15
}
Copied!

后序遍历

后序遍历(post order)的顺序是 LRD
Could not load image
上图的后序遍历顺序为: GHDBIEFCA

后序遍历的递归方式

1
function postOrder(root) {
2
if (!root) {
3
return;
4
}
5
6
postOrder(root.left);
7
postOrder(root.right);
8
// do something
9
// console.log(root.val);
10
}
Copied!

后序遍历的非递归方式

1
function postOrderWithoutRecursion(root) {
2
if (!root) {
3
return;
4
}
5
const stack = [];
6
let node = root;
7
let last = node;
8
stack.push(node);
9
while (stack.length > 0) {
10
node = stack[stack.length - 1];
11
if (
12
(!node.left && !node.right) ||
13
(!node.right && last === node.left) ||
14
last === node.right
15
) {
16
// doing something
17
// console.log(node.val);
18
last = node;
19
stack.pop();
20
} else {
21
if (node.right) {
22
stack.push(node.right);
23
}
24
if (node.left) {
25
stack.push(node.left);
26
}
27
}
28
}
29
}
Copied!

广度优先遍历

广度优先遍历,也可以称之为层级遍历,先访问兄弟节点,再访问子节点。
Could not load image
上图的后序遍历顺序为: FBGADICEH
1
function bfs(root) {
2
if (!root) {
3
return;
4
}
5
const queue = [root];
6
7
while (queue.length > 0) {
8
const node = queue.shift();
9
// do something
10
// console.log(node.val)
11
if (node.left) {
12
queue.push(node.left);
13
}
14
if (node.right) {
15
queue.push(node.right);
16
}
17
}
18
}
Copied!
Last modified 2yr ago