二叉树的遍历
二叉树的遍历
二叉树(Binary Tree)每个节点最多有两个子节点的树型数据结构。
class TreeNode {
constructor(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
二叉树的遍历方式主要分为 深度优先(Deep-first Search, DFS) 和 广度优先(Breadth-first Search,BFS)。
其中深度优先遍历有以下几种方法
前序遍历
中序遍历
后序遍历
深度优先
深度优先顾名思义就是先纵向搜索,在进入下一个兄弟节点之前,尽可能的向下搜索每一个子节点。 该算法从根节点开始(在图的情况下选择一些任意节点作为根节点)并在回溯之前尽可能地沿着每个分支进行探索。
前序遍历
前序遍历(pre-order)的访问顺序是 DLR
L 为左子树,R 为右子树,D 为根节点
上图的前序遍历顺序为: ABDGHCEIF
前序遍历的递归方式
function preOrder(root) {
if (!root) {
return;
}
// do something
// console.log(root.val)
preOrder(root.left);
preOrder(root.right);
}
前序遍历的非递归方式
对于任一结点 P
:
访问结点
P
,并将结点P
入栈;判断结点
P
的左孩子是否为空,若为空,则取栈顶结点并进行出栈操作,并将栈顶结点的右孩子置为当前的结点P
,循环至 1; 若不为空,则将P
的左孩子置为当前的结点P
;直到
P
为null
并且栈为空,则遍历结束。
function preOrderWithoutRecursion(root) {
const stack = [];
let node = root;
while (node || stack.length > 0) {
if (node) {
// do something
// console.log(node.val);
stack.push(node);
node = node.left;
} else {
node = stack.pop().right;
}
}
}
中序遍历
中序遍历(in-order)的顺序是 LDR
上图的中序遍历顺序为: GDHBAEICF
中序遍历的递归方式
function inOrder(root) {
if (!root) {
return;
}
inOrder(root.left);
// do something
// console.log(root.val);
inOrder(root.right);
}
中序遍历的非递归方式
对于任一结点 P
:
若其左孩子不为空,则将
P
入栈并将P
的左孩子置为当前的P
,然后对当前结点P
再进行相同的处理;若其左孩子为空,则取栈顶元素并进行出栈操作,访问该栈顶结点,然后将当前的
P
置为栈顶结点的右孩子;直到
P
为null
并且栈为空则遍历结束
function inOrderWithoutRecursion(root) {
const stack = [];
let node = root;
while (node || stack.length > 0) {
if (node) {
stack.push(node);
node = node.left;
} else {
const lastNode = stack.pop();
// do something
// console.log(lastNode.val);
node = lastNode.right;
}
}
}
后序遍历
后序遍历(post order)的顺序是 LRD
上图的后序遍历顺序为: GHDBIEFCA
后序遍历的递归方式
function postOrder(root) {
if (!root) {
return;
}
postOrder(root.left);
postOrder(root.right);
// do something
// console.log(root.val);
}
后序遍历的非递归方式
function postOrderWithoutRecursion(root) {
if (!root) {
return;
}
const stack = [];
let node = root;
let last = node;
stack.push(node);
while (stack.length > 0) {
node = stack[stack.length - 1];
if (
(!node.left && !node.right) ||
(!node.right && last === node.left) ||
last === node.right
) {
// doing something
// console.log(node.val);
last = node;
stack.pop();
} else {
if (node.right) {
stack.push(node.right);
}
if (node.left) {
stack.push(node.left);
}
}
}
}
广度优先遍历
广度优先遍历,也可以称之为层级遍历,先访问兄弟节点,再访问子节点。

上图的后序遍历顺序为: FBGADICEH
function bfs(root) {
if (!root) {
return;
}
const queue = [root];
while (queue.length > 0) {
const node = queue.shift();
// do something
// console.log(node.val)
if (node.left) {
queue.push(node.left);
}
if (node.right) {
queue.push(node.right);
}
}
}
最后更新于