树,包括图,在遍历时都存在两种方式:深度优先遍历和广度优先遍历。
树,一定有一个根节点,而图,没有根节点,但图中的任意节点都可以作为根节点使用(当然该节点一定要有边,否则没有意义)
深度优先遍历
- 访问当前节点
- 将当前节点的children作为子树的根节点递归访问
使用递归的方式
// 传入树的根节点,开始深度优先遍历
function dfs(root) {
// 访问节点数据
console.log(root.val);
if (root.children.length > 0) {
for(let i = 0; i < root.children.length; i ++) {
dfs(root.children[i]);
}
// 或者使用root.children.forEach(dfs)来替换上面的for循环
}
}
广度优先遍历
- 新建队列,将根节点入队
- 队列出队,访问出队节点
- 将出队节点的children依次入队
- 重复2和3,直到队列为空
使用队列的方式
// 传入树的根节点,开始深度优先遍历
function bfs(root) {
const queue = [];
queue.push(root);
while(queue.length > 0) {
const node = queue.shift();
console.log(node.val);
node.children && node.children.forEach(child => queue.push(child))
}
}
在打包模块时,可以使用广度优先遍历从入口文件触发,构建模块的依赖图谱。
二叉树的先中后序遍历
先、中、后指的是根节点的访问顺序
先序遍历
- 访问根节点
- 对左子树先序遍历
- 对右子树先序遍历
// 先序遍历
function preOrder(root) {
// 递归终止条件
if (!root) return;
console.log(root.val);
preOrder(root.left);
preOrder(root.right);
}
中序遍历
- 对左子树中序遍历
- 访问根节点
- 对右子树中序遍历
// 中序遍历
function inOrder(root) {
if (!root) return;
inOrder(root.left);
console.log(root.val);
inOrder(root.right);
}
后序遍历
- 对左子树后序遍历
- 对右子树后序遍历
- 访问根节点
// 后序遍历
function postOrder(root) {
if (!root) return;
postOrder(root.left);
postOrder(root.right);
console.log(root.val)
}
非递归型的遍历
所有的递归都可以用栈来代替,因为递归函数底层就是使用栈来实现的。
先序遍历
- 访问根节点
- 对左子树先序遍历
- 对右子树先序遍历
function preOrder(root) {
if (!root) {return;}
const stack = [];
stack.push(root);
while(stack.length > 0) {
// 出栈
const node = stack.pop();
console.log(node.val);
// 将左右子树入栈, 先让右子树入栈,再让左子树入栈
if (node.right) {
stack.push(node.right);
}
if (node.left) {
stack.push(node.left);
}
}
}
中序遍历
- 对左子树中序遍历
- 访问根节点
- 对右子树中序遍历
// 中序遍历
function inOrder(root) {
if (!root) {return;}
const stack = [];
let p = root;
while(p || stack.length > 0) {
while(p) {
// 先将左子树不断入栈
stack.push(p);
p = p.left;
}
// 所有左子树都入栈后,开始出栈访问
const node = stack.pop();
console.log(node.val);
// 将右子树入栈
p = node.right;
}
}
后序遍历
- 对左子树后序遍历
- 对右子树后序遍历
- 访问根节点
// 后序遍历
function postOrder(root) {
if (!root) {return;}
const stack = [];
const outPutStack = [];
stack.push(root);
// 对前序遍历进行改造,前序遍历是 根 -> 左 -> 右,后续遍历是左 -> 右 -> 根,
// 将前序遍历改造成 根 -> 右 -> 左,然后逆序输出访问即可
while(stack.length > 0) {
// 出栈
const node = stack.pop();
outPutStack.push(node)
// 前序遍历改造,先将左子树入栈,再将右子树入栈
if (node.left) {
stack.push(node.left);
}
if (node.right) {
stack.push(node.right);
}
}
while(outPutStack.length > 0) {
const node = outPutStack.pop();
console.log(node.val);
}
}