共计 2491 个字符,预计需要花费 7 分钟才能阅读完成。
1、二叉树的层级遍历
- 创建一个二叉树
class Binary{constructor(data,left,right){
this.data = data
this.left = left
this.right = right
}
}
- 输出函数
function Output(){const left = new Binary(1, new Binary(2),new Binary(3))
const right = new Binary(4,new Binary(5),new Binary(6))
const root = new Binary(0,left,right)
//console.log(root)
/*
0
/ \
1 4
/ \ / \
2 3 5 6
*/
inOrder(root) // 2 1 3 0 5 4 6
preOrder(root) //0 1 2 3 4 5 6
postOrder(root) //2,3,1,5,6,4,0
levelOrder(root) // 0,1,4,2,3,5,6
}()
- 先访问左子树,再访问自身,再访问右子树
function inOrder(root){if(root){inOrder(root.left)
console.log(root.data)
inOrder(root.right)
}
}
- 先访问自身,再访问左子树,再访问右子树
function preOrder(root){if(root){console.log(root.data)
preOrder(root.left)
preOrder(root.right)
}
}
- 先访问左子树,再访问右子树再访问自身
function postOrder(root){if(root){postOrder(root.left)
postOrder(root.right)
console.log(root.data)
}
}
- 层级遍历
function levelOrder(root){var queue = []
queue.unshift(root)
while(queue.length){var current = queue.pop()
console.log(current.data)
if(current.left){queue.unshift(current.left)
}
if(current.right){queue.unshift(current.right)
}
}
}
2、多叉树的层级遍历
- 创建一个多叉树
class TreeNode {constructor(data){
this.data = data
this.children = []}
}
- 输出函数
function main(){const root = new TreeNode(0)
const node2 = new TreeNode(2)
cosnt node2.children.push(new TreeNode(7))
const node2.chilfren.push(new TreeNode(8))
const node2.children.push(new TreeNode(9))
const node4 = new TreeNode(4)
const node3 = new TreeNode(3)
const node3.children.push(new TreeNode(6))
const node3.children.push(new TreeNode(5))
root.children.push(node2)
root.children.push(node4)
root.children.push(node3)
//console.log(root)
/*
0
/ | \
2 4 3
/ | \ / \
7 8 9 6 5
*/
traverse1(root)
traverse2(traverse2[root])
var result = []
traverse3([root],result)
console.log(result)
levelOrder(root)
}()
递归遍历每个节点
- 方法 1
function traverse1(node){if(!node){return []
}
var result = []
result.push(node.data)
if(node.children){for(var i = 0;i<=node.children.length-1;i++){result = result.concat(traverse1(node.children[i]))
}
return result
}
}
- 方法 2
function tranverse2(nodeList){if(!nodeList){return []
}
var result = []
for(var i=0;i<=nodeList.length-1;i++){result.push(nodeList[i].data)
if(nodeList[i].children){result = result.concat(traverse2(nodeList[i].children))
}
}
return result
}
- 方法 3
function traverse3(nodeList,result){if(!nodeList){return false}
for(var i=0;i<=nodeList.length-1;i++){resule.push(nodeList[i].data)
if(nodeList[i].childern){traverse3(nodeList[i].children,result)
}
}
}
层级遍历每个节点
funciton levelOrder(root){var queue = []
queue.unshift(root)
var result = []
while(quue.length){var current = queue.pop()
result.push(current.data)
for(var i =0;i<=current.children.length-1;i++){if(current.children[i]){queue.unshift(current.children[i])
}
}
}
console.log(result)
}
正文完
发表至: javascript
2019-05-28