@moyuyc/walk-tree

Enhanced and multifunctional tree walker

Installation

npm install @moyuyc/walk-tree
# or use yarn
yarn add @moyuyc/walk-tree

Usage

const walkTree = require('@moyuyc/walk-tree')

walkTree(
  {
    name: 'root',
    children: [{ name: 'c1' }, { name: 'c2' }, { name: 'c3', children: { name: 'c31' } }]
  },
  node => {
    console.log(node.name)
  }
)
// prints
// root / c1 / c2 / c3 / c31
// by order

API

walk

index.js:54-138

Parameters

• tree {T} - Type T should extends Object
• walker {(node, ctx: Context) => {}} - Iterator for each node by order
• opts Object {object}
  • opts.path {string} - The child's path on recursive struction (optional, default 'children')
  • opts.order {'pre' | 'post' | 'bfs'}
    pre means walking the node before walking it's children node by dfs
    post means walking the node after walking it's children node by dfs
    bfs means walking the node by bfs
    (optional, default 'pre')
  • opts.skipVisited {boolean} Should skip the node which has been visited. (optional, default true)
  • opts.uniquePath {Function | string | null} The unique's path for determining the node has been visited (same node) (optional, default node=>node)
  • opts.state {any} Inject in context.state on customized way

Returns any walkedTree {T}

Context

A traversal context.

Four operations are available. Note that depending on the traversal order, some operations have no effects.

remove

walk(rootNode, (node, ctx) => {
  if (node.name === 'remove-me') {
    return ctx.remove()
  }
})

replace

walk(rootNode, (node, ctx) => {
  if (node.name === 'replace-me') {
    return ctx.replace({ name: 'new-me' })
  }
})

break

Stop traversal now.

walk(rootNode, (node, ctx) => {
  if (node.name === 'stop') {
    return ctx.break()
  }
})

skip

Skip current node, children won't be visited.

walk(rootNode, (node, ctx) => {
  if (node.name === 'skip') {
    return ctx.skip()
  }
})

parent

Get the parent of the current node.

depth

Get the depth of the current node. The depth is the number of ancestors the current node has.

level

Get the level of current node. The level is the number of ancestors+1 the current node has.

index

Get the index of the current node.

FAQ

How can I get the path of the current node tree-crawl#37?

tl;dr It's easy for DFS, less easy for BFS

If you are using DFS you can use the following utility function:

const getPath = context =>
  (context.cursor.stack.xs || []).reduce((path, item) => {
    if (item.node) {
      path.push(item.node)
    }
    return path
  }, [])

If you are really concerned about performance, you could read items from the stack directly. Each item has a node and index property that you can use. The first item in the stack can be discarded and will have a node set to null. Be aware that you should not mutate the stack, or it will break the traversal.

If you are using BFS, things gets more complex. A simple hacky way to do so is to traverse the tree using DFS first. You can ad a path property to your nodes using the method above. And then do your regular BFS traversal using that path property.

Credit

The core algorithm of traverse credits to tree-crawl

walk-tree has the different with tree-crawl

Because tree-crawl has no idea about the intrinsic structure of your tree, you have to remove the node yourself. Context#remove only notifies the traversal code that the structure of the tree has changed.

Otherwise walk-tree would infers your tree by option path so don't requires additional remove action.

Authors

This library is written and maintained by imcuttle, mailto:moyuyc95@gmail.com.

License

MIT