二叉树的先中后序遍历(递归+非递归 JS 实现)
JavaScript 中没有树这种数据结构,但可以用 Object 和 Array 来构建树。二叉树是指,树中每个节点最多只能有两个子节点,分别为左节点、右节点,通常使用 Object 模拟二叉树。二叉树的先中后序遍历一般可以用递归来完成,也可以利用栈实现非递归的方式实现。
数据源:
const bt = {
val: 1,
left: {
val: 2,
left: {
val: 4,
left: null,
right: null
},
right: {
val: 5,
left: null,
right: null
}
},
right: {
val: 3,
left: {
val: 6,
left: null,
right: null
},
right: {
val: 7,
left: null,
right: null
}
}
};
先序遍历
根-左-右:先访问根节点,再对根节点的左子树进行先序遍历,最后对根节点的右子树进行先序遍历
- 递归
const preorder = (root) => {
if (!root) return;
preorder(root.left);
preorder(root.right);
};
preorder(bt);
- 非递归
const preorder = (root) => {
if (!root) return;
const stack = [root];
while (stack.length) {
const n = stack.pop();
console.log(n.val);
// 由于栈先进后出的特性,所有先 push right,再 push left
if (n.right) stack.push(n.right);
if (n.left) stack.push(n.left);
}
};
preorder(bt);
output: 1 2 4 5 3 6 7
中序遍历
左-根-右:先对根节点的左子树进行中序遍历,再访问根节点,最后对根节点的右子树中序遍历
- 递归
const inorder = (root) => {
if (!root) return;
inorder(root.left);
console.log(root.val);
inorder(root.right);
};
inorder(bt);
- 非递归
const inorder = (root) => {
if (!root) return;
const stack = [];
let p = root;
while (stack.length || p) {
// 类似于遍历链表,把当前根节点的所有左节点 push 到 stack 中
while (p) {
stack.push(p);
p = p.left;
}
// 访问最底层的左节点
const n = stack.pop();
console.log(n.val);
// 然后将指针指向当前根节点的右节点,以该右节点作为根节点继续下轮的遍历
p = n.right;
}
};
inorder(bt);
output: 4 2 5 1 6 3 7
后序遍历
左-右-根:先对根节点的左子树进行后序遍历,再对根节点的右子树进行后序遍历,最后访问根节点
- 递归
const postorder = (root) => {
if (!root) return;
postorder(root.left);
postorder(root.right);
console.log(root.val);
};
postorder(bt);
- 非递归
// 先将后序遍历取反变为类似于先序遍历,即:左-右-根 => 根-右-左
// 再利用栈先进后出特性,把先序遍历的结果取反,遍历访问就是后序遍历的结果
const postorder = (root) => {
if (!root) return;
const outputStack = []; // 最终用来倒序输出的栈
const stack = [root]; // 用来先序遍历的栈
while (stack.length) {
const n = stack.pop();
// 将 n push 到 outputStack 中
outputStack.push(n);
// 因为和现需遍历不完全一样,先序遍历:根-左-右,此时为:根-右-左
// 所以此时先 push left,再 push right
if (n.left) stack.push(n.left);
if (n.right) stack.push(n.right);
}
// 最终遍历 pop outputStack 的所有元素输出,即为后序遍历的结果
while (outputStack.length) {
const n = outputStack.pop();
console.log(n.val);
}
};
postorder(bt);
output: 4 5 2 6 7 3 1