二叉树:每个节点最多只有两个字节点
JS中通常用 Object来模拟二叉树
(val: 1, left: 0, right: 0)
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,
},
},
};
先序遍历算法(preorder)「根左右」
1:访问根节点
2:对根节点的左子树进行先序遍历
3:对根节点的右子树进行先序遍历
递归遍历
非递归(利用栈)
const preorder = (root) => {
if (!root) { return; }
const stack = [root];
while (stack.length) {
const n = stack.pop();
console.log(n.val);
if (n.right) stack.push(n.right);
if (n.left) stack.push(n.left);
}
};preorder(bt);
中序遍历算法(inorder): 「左根右」
1:对根节点的左子树进行中序遍历
2:访问根节点
3:对根节点的右了树进行中序遍历
const inorder = (root) => {
if (!root) { return; }
const stack = [];
let p = root;
while (stack.length || p) {
while (p) {
stack.push(p);
p = p.left;
}
const n = stack.pop();
console.log(n.val);
p = n.right;
}
};
inorder(bt);
后序遍历算法(postorder):「左右根」
1:对根节点的左子树进行后序遍历
2:对根节点的右子树进行后序遍历
3:访问根节点
const postorder = (root) => {
if (!root) { return; }
const outputStack = [];
const stack = [root];
while (stack.length) {
const n = stack.pop();
outputStack.push(n);
if (n.left) stack.push(n.left);
if (n.right) stack.push(n.right);
}
while(outputStack.length){
const n = outputStack.pop();
console.log(n.val);
}
};postorder(bt);标签：遍历,const,val,right,二叉树,先中,stack,left From： https://blog.51cto.com/u_15765713/5983355