一种分层数据的模型
前端工作中常见包括：DOM树，级联选择，树形控件
JS中没有树，但是可以用Object和Array构建树
树的常用操作：深度/广度优先遍历，先中后序遍历
1. 常用操作
DFS实现
- 访问根节点
- 对根节点的children挨个进行深度优先遍历
const tree = { val: 'a', children: [ { val: 'b', children: [ { val: 'c', children: [] }, { val: 'd', children: [] } ] }, { val: 'e', children: [ { val: 'f', children: [] }, { val: 'g', children: [] } ] } ] } const dfs = (root) => { console.log(root.val) root.children.forEach(dfs) } dfs(tree)
BFS实现
- 新建一个队列，把根节点入队
- 把对头出队并访问
- 把对头的children挨个入队
- 重复第二三步，直到队列为空
const tree = { val: 'a', children: [ { val: 'b', children: [ { val: 'c', children: [] }, { val: 'd', children: [] } ] }, { val: 'e', children: [ { val: 'f', children: [] }, { val: 'g', children: [] } ] } ] } const bfs = (root) => { const q = [root] while(q.length > 0) { const r = q.shift() console.log(r) r.children.forEach(item => q.push(item)) } } bfs(tree)
二叉树的先中后序遍历（递归）
const bt = { val: 1, left: { val: 2, left: { val: 4, left: null, right: null }, right: { val: 5, left: null, right: null, } }, right: { val: 3, left: { val: 6, left: null, right: null, }, right: { val: 7, left: null, right: null, } } } // 先序遍历 const preorder = (root) => { if(!root) { return } console.log(root.val) preorder(root.left) preorder(root.right) } // 中序遍历 const inorder = (root) => { if(!root) { return } inorder(root.left) console.log(root.val) inorder(root.right) } // 后序遍历 const postorder = (root) => { if(!root) { return } postorder(root.left) postorder(root.right) console.log(root.val) }
二叉树的先中后序遍历（非递归）
// 先序遍历 const preorder = (root) => { if(!root) { return } const stack = [root] while(stack.length) { const n = stack.pop() console.log(n.val) if( n.right ) stack.push(n.right) if( n.left ) stack.push(n.left) } } // 中序遍历 const inorder = (root) => { if(!root) { return } const stack = [] let p = root while(stack.length || p) { while(p) { stack.push(p) p = p.left } const n = stack.pop() console.log(n.val) p = n.right } } // 后续遍历 const postorder = (root) => { if(!root) { return } const outputStack = [] const stack = [root] while(stack.length) { const n = stack.pop() outputStack.push(n) if(n.left) stack.push(n.left) if(n.right) stack.push(n.right) } while(outputStack.length) { const n = outputStack.pop() console.log(n.val) } }
