二叉树遍历
深度优先遍历（递归遍历）
觉得用这几个字母表示递归遍历的三种方法不错：
D：访问根结点，L：遍历根结点的左子树，R：遍历根结点的右子树。
先序遍历：DLR
中序遍历：LDR
后序遍历：LRD
这3种遍历都属于递归遍历，或者说深度优先遍历（Depth-First Search，DFS），因为它总 是优先往深处访问。
先序遍历
var preOrder = function (node) {
if (node) {
console.log(node.value);
preOrder(node.left);
preOrder(node.right);
}
}中序遍历
var inOrder = function (node) {
if (node) {
inOrder(node.left);
console.log(node.value);
inOrder(node.right);
}
}后序遍历
var postOrder = function (node) {
if (node) {
postOrder(node.left);
postOrder(node.right);
console.log(node.value);
}
}先序遍历
广度优先遍历是从二叉树的第一层（根结点）开始，自上至下逐层遍历；在同一层中，按照从左到右的顺序对结点逐一访问。
var levelOrderTraversal = function(node) {
if(!node) {
throw new Error('Empty Tree')
}
var que = []
que.push(node)
while(que.length !== 0) {
node = que.shift()
console.log(node.value)
if(node.left) que.push(node.left)
if(node.right) que.push(node.right)
}
}中序遍历
var inOrderUnRecur = function (node) {
if (!node) {
throw new Error('Empty Tree')
}
var stack = []
while (stack.length !== 0 || node) {
if (node) {
stack.push(node)
node = node.left
} else {
node = stack.pop()
console.log(node.value)
node = node.right
}
}
}后序遍历
var posOrderUnRecur = function (node) {
if (!node) {
throw new Error('Empty Tree')
}
var stack = []
stack.push(node)
var tmp = null
while (stack.length !== 0) {
tmp = stack[stack.length - 1]
if (tmp.left && node !== tmp.left && node !== tmp.right) {
stack.push(tmp.left)
} else if (tmp.right && node !== tmp.right) {
stack.push(tmp.right)
} else {
console.log(stack.pop().value)
node = tmp
}
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-11-13，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录