JS中的二叉树遍历详解
8 浏览量
2020-11-23
11:49:46
上传
评论
收藏 54KB PDF 举报
JS中的二叉树遍历详解中的二叉树遍历详解
二叉树是由根节点，左子树，右子树组成，左子树和友子树分别是一个二叉树。
这篇文章主要在JS中实现二叉树的遍历。
一个二叉树的例子一个二叉树的例子
var tree = {
value: 1,
left: {
value: 2,
left: {
value: 4
}
},
right: {
value: 3,
left: {
value: 5,
left: {
value: 7
},
right: {
value: 8
}
},
right: {
value: 6
}
}
}
广度优先遍历广度优先遍历
广度优先遍历是从二叉树的第一层（根结点）开始，自上至下逐层遍历；在同一层中，按照从左到右的顺序对结点逐一访问。
实现：
<!–more–>
使用数组模拟队列。首先将根节点归入队列。当队列不为空的时候，执行循环：取出队列的一个节点，如果该结点的左子树为
非空，则将该结点的左子树入队列；如果该结点的右子树为非空，则将该结点的右子树入队列。
（描述有点不清楚，直接看代码吧。）
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)
}
}
递归遍历递归遍历
觉得用这几个字母表示递归遍历的三种方法不错：
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);
}
}
评论0