javascript实现二叉树遍历思想跟C，Java等语言是一样的，不过写起来，因为javascript没有链表，指针一说，(通常用链接来表示二叉树),只能大概表达一下意思。
构造二叉树
//构建二叉树
function Node(data) {
this.left = null
this.right = null
this.data = data
}
生成二叉树
//以前序遍历的顺序创建二叉树
function createTree(data) {
let node_data = data.shift()
let p = null
if (node_data != 0) {
p = new Node(node_data)
p.left = createTree(data)
p.right = createTree(data)
}
return p
}
调用createTree生成一棵二叉树,节点值为0的节点，表示子树为空
const arr = [1, 2, 4, 8, 0, 0, 5, 0, 0, 6, 0, 0, 3, 7, 10, 0, 0, 11, 0, 0, 9, 12, 0, 0, 13, 0, 14, 0, 0]
const root = createTree(arr)
前序遍历（递归）
//前序遍历（递归）
function prevTraverse(node) {
if (node == null) return
console.log(node.data)
prevTraverse(node.left)
prevTraverse(node.right)
}
中序遍历（递归）
//中序遍历（递归）
function middleTraverse(node) {
if (node == null) return
middleTraverse(node.left)
console.log(node.data)
middleTraverse(node.right)
}
后序遍历（递归）
function lastTraverse(node) {
if (node == null) return
lastTraverse(node.left)
lastTraverse(node.right)
console.log(node.data)
}
javascript递归实现代码简洁，递归其实也是借助栈来实现的，递归调用是把函数及函数的参数压栈，然后再一步步回溯，下边用javascript的数组来表示栈，利用栈的后进先出特性来实现二叉树的前，中，后序遍历，其中前序，中序遍历稍微简单一些，看其它大神有几种实现思路，我只用其中自己感觉比较好理解的思路实现了一下，后序遍历比较复杂一些，我暂时放了一个比较巧的方法，即是正常二叉树的前序遍历：根-->左子树-->右子树，变为 根 --> 右子树 --> 左子树，然后再逆序输出
注：用数组表示栈可以在栈顶操作，也可以在栈底操作，在栈顶: push加入数据，pop弹出数据，在栈底: unshift加入数据，shift弹出数据
前序遍历（非递归，借助栈）
function prevTraverseWithStack(node) {
const stack = []
let p = node
while (p != null || stack.length > 0) {
//处理左子树
while (p != null) {
//stack.unshift(p)
stack.push(p)
console.log(p.data)
p = p.left
}
//处理右子树
if (stack.length > 0) {
//p = stack.shift()
p = stack.pop()
//console.log('stack length: ' + stack.length)
p = p.right
}
}
}
前序遍历二，便于跟中序遍历比较（非递归，借助栈）
function prevTraverseWithStack2(node) {
const stack = []
let p = node
while (p != null || stack.length > 0) {
if (p != null) {
stack.push(p)
console.log(p.data)
p = p.left
} else {
p = stack.pop()
p = p.right
}
}
}
前序遍历三（非递归，借助栈）
function prevTraverseWithStack3(node) {
const stack = []
let p = null
stack.unshift(node)
while (stack.length > 0) {
//p = stack.shift()
p = stack.pop()
//console.log('stack length: ' + stack.length)
console.log(p.data)
if (p.right != null) {
//stack.unshift(p.right)
stack.push(p.right)
}
if (p.left != null) {
//stack.unshift(p.left)
stack.push(p.left)
}
}
}
中序遍历（非递归，借助栈）
先上一版，我蒙头写的，反正是可以运行的，方法就是把输出结果摆在那里，然后一点点试错，stack.push(p.right)这一句就是为了有一个bug而来的，但最后分析一下，逻辑也是对的，感觉用栈来实现的核心就是 每个节点都要访问它的左节点，右节点，然后再看情况进行回溯
function middleTraverseWithStack(node) {
let p = node
let stack = []
while(p !== null || stack.length > 0){
if(p.left !== null) {
stack.push(p)
p = p.left
}else{
console.log(p.data)
if(p.right) {
stack.push(p.right)
}
let t = stack.pop()
console.log(t.data)
p = t.right
}
}
}
书上的
function middleTraverseWithStack(node) {
const stack = []
let p = node
while (stack.length > 0 || p != null) {
if (p === null) {
//p = stack.shift()
p = stack.pop()
console.log(p.data)
p = p.right
} else {
//stack.unshift(p)
stack.push(p)
p = p.left
}
}
}
后序遍历一（非递归，借助栈）
相比前，中序遍历，多定义一个 result 栈来实现逆序输出结果
左-->右-->根 ----- reverse --- 根-->右-->左 ------- 根-->左-->右 前序遍历翻版
function lastTraverseWithStack(node) {
let stack = [], p = node, result = []
while (stack.length > 0 || p !== null) {
if (p !== null) {
stack.push(p)
result.unshift(p.data)
//console.log(p.data)
p = p.right
} else {
p = stack.pop()
p = p.left
}
}
console.log(result)
//return result
}
后序遍历二（非递归，借助栈）
相比前，中序遍历，多定义一个 tag 来标记是否已经访问过，目前还是不太懂
function lastTraverseWithStack1(node) {
let stack = [], p = node, tag
while (p !== null || stack.length > 0) {
if (p !== null) {
stack.push(p)
p = p.left
}
else {
p = stack[stack.length - 1];
if (p.right && tag != p.right) {
p = p.right;
}
else {
stack.pop();
console.log(p.data);
tag = p;
p = null;
}
}
}
}
层序遍历（非递归，借助队列）
层序遍历用递归实现比较绕，需要先求出二叉树的深度，再进行递归
//层序遍历 push与shift结合，将数组当作队列使用
function floorPrintWithQuene(node) {
const quene = []
quene.push(node)
while (quene.length > 0) {
node = quene.shift()
console.log(node.data)
if (node.left != null) {
quene.push(node.left)
}
if (node.right != null) {
quene.push(node.right)
}
}
}
其它非递归实现思想可参考：
本文由 dealdot ＜dealdot＃163.com＞ 创作, Full Stack Developer @ DeepBlue
本文最后编辑时间为: Jun 10, 2021 at 17:43 pm
转载请注明来源