<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>JS 二叉树的遍历</title>
</head>
<body>
<script>
const root = {
value: 'root-1',
left: {
value: 'l-1',
left: {
value: 'l-1-1',
left: {
value: 'l-1-1-1',
left: null,
right: null
},
right: {
value: 'l-1-1-2',
left: null,
right: null
}
},
right: {
value: 'l-1-2',
left: {
value: 'l-1-2-1',
left: null,
right: null
},
right: {
value: 'l-1-2-2',
left: null,
right: null
}
}
},
right: {
value: 'l-2',
left: {
value: 'l-2-1',
left: {
value: 'l-2-1-1',
left: null,
right: null
},
right: {
value: 'l-2-1-2',
left: null,
right: null
}
},
right: {
value: 'l-2-2',
left: {
value: 'l-2-2-1',
left: null,
right: null
},
right: {
value: 'l-2-2-2',
left: null,
right: null
}
}
}
}
/**
* 二叉树遍历分为前序遍历、中序遍历(左中右)、后序遍历（左右中）
* 前序遍历：1. 先访问根节点
* 2. 先对当前节点的左节点进行前序遍历，如果有子节点，则继续进行前序遍历
* 3. 对右节点进行前序遍历，如果有子节点，则继续进行前序遍历
*/
function preorder(root) {
if (!root) return
console.log(root.value)
preorder(root.left)
preorder(root.right)
}
// 非递归版本，先root， 后left 在right，主要是pop尾部截取，执行栈内先插入right 在插入left，保证先left 后 right的顺序
function preorder2(root) {
if (!root) return
const stack = [root]
while(stack.length) {
const item = stack.pop()
console.log(item.value)
if (item.right) {
stack.push(item.right)
}
if (item.left) {
stack.push(item.left)
}
}
}
// preorder(root)
/**
* 中序遍历
* 原理：先访问left节点，如果有子节点继续中序遍历，在访问根节点，最后访问right节点，如果存在子节点则继续中序遍历
*/
function inorder(root) {
if (!root) return
inorder(root.left)
console.log(root.value)
inorder(root.right)
}
function inorder2(root) {
if (!root) return
const stack = []
let p = root
while(p || stack.length) {
while(p) {
stack.push(p)
p = p.left
}
const n = stack.pop()
console.log(n.value)
p = n.right
}
}
// inorder2(root)
/**
* 后序遍历
* 先遍历left，如果有子节点则继续后序遍历，再遍历right节点，如果有子节点，则继续中序遍历，最后访问root
*/
function nextorder(root) {
if (!root) return
nextorder(root.left)
nextorder(root.right)
console.log(root.value)
}
// 非递归版本
function nextorder2(root) {
if (!root) return
const stack = [root]
let outStack = []
while(stack.length) {
const n = stack.pop()
outStack.push(n)
/**
* 1. 首先outStack放入的是root
* 2. 然后再放入left right
* 3. 由于stack是pop尾部删除，所以每次先取出来的一定是right
* 4. 那么在outStack的顺序就是root -> right -> left
* 5. 那么outStack通过pop尾部取出就是 left -> right -> root的顺序
*/
if (n.left) stack.push(n.left)
if (n.right) stack.push(n.right)
}
while(outStack.length) {
const n = outStack.pop()
console.log(n.value)
}
}
// nextorder2(root)
/**
* 层序遍历，
* 按照二叉树结构一层层打印, 先左后右
* 有点类似深度优先算法
*/
function deepOrder(root) {
if (!root) return
const stack = [root]
const res = []
while (stack.length) {
const len = stack.length
const child = []
for (let i = 0; i < len; i++) {
// 因为先push left 再push right，所以取的时候需要反续
const n = stack.shift()
child.push(n.value)
if (n.left) stack.push(n.left)
if (n.right) stack.push(n.right)
}
res.push(child)
}
console.log(res)
}
// 层序遍历测试
// deepOrder(root)
</script>
</body>
</html>
前端面试题整理：Nginx、webpack、Html&Css、Vue、JavaScript.zip
版权申诉
152 浏览量
2023-10-19
18:38:35
上传
评论
收藏 29.04MB ZIP 举报
前端面试题整理：Nginx、webpack、Html&Css、Vue、JavaScript.zip （41个子文件） 
interview-main .vscode 
settings.json 509B extensions.json 39B ss.md 0B JS常见的手写题 
JS 二叉树的遍历.html 6KB JS 防抖与节流.html 2KB JS_eventBus.html 2KB JS实现new.html 1009B JS 二叉树路径、最大、最小和.html 5KB JS 深拷贝.html 887B JS 数组扁平化.html 1KB JS 数组和树结构相互转换.html 3KB JS_setInterval_setTimeout.html 670B JS 手写数组原型链方法.html 316B JS 继承方式.html 3KB JS 实现函数柯里化.html 2KB JS 实现Promise.html 3KB index.html 277B JS实现bind、call、apply.html 3KB JS 排序算法.html 3KB JS 实现异步并发器.html 2KB JS 深度优先广度优先算法.html 5KB JS_爬楼梯.html 625B JS 手写reduce.html 742B JS 数组去重.html 1KB 思维导图 webpack相关面试题.xmind 368KB typeScript面试题.xmind 2.45MB 微前端qiankunJs.xmind 2.03MB JS相关面试题.xmind 6.84MB 前端知识体系.xmind 5.71MB Vue面试.xmind 1.24MB 前端算法.xmind 7.51MB HTML&CSS相关知识.xmind 722KB es6面试题.xmind 1.65MB vuex&vue-router面试题.xmind 1.14MB ReactJS面试题.xmind 289KB Http相关面试题.xmind 831KB 前端SEO优化.xmind 507KB git相关面试题.xmind 479KB h5开发以及angular补充.xmind 434KB NODEJS相关知识.xmind 51KB .gitignore 10B资源评论
