n-ary tree(also known as k-ary or k-way tree) implementation in JavaScript(TypeScript).
- Using npm
$ npm i n-ary-tree- Using yarn
$ yarn add n-ary-treeUser-defined tree node fields have supported by all available methods. Just keep the last parameter is a structure like:
type TreeNodeFields<N> = Partial<{
value: keyof N
children: keyof N
}>{
value: 'value',
children: 'children'
}By default, we will use value field as the value of tree node, children field as the children of tree node.
{
value: 'val', // or other field string in the tree node
children: 'descendants' // or other field string in the tree node
}val field will be regarded as node actual value, descendants field in the tree node will be regraded as node children field.
Get all matched nodes.
export function findNodes<N extends Record<string, any>, V = any>(
root: N,
targets: V[],
fields?: TreeNodeFields<N>
): FindNodesResult<N, V>import { findNodes } from 'n-ary-tree'
interface DefaultTreeNode {
value: number
children?: DefaultTreeNode[]
}
const tree: DefaultTreeNode = {
value: 1,
children: [
{
value: 11,
children: [
{
value: 111
}
]
},
{
value: 12,
children: [
{
value: 121
}
]
}
]
}
findNodes(tree, [111])
// -> {
// nodes: [{ value: 111 }],
// values: [111]
// }
findNodes(tree, [111], { value: 'value', children: 'children' })
// Equivalent to findNodes(tree, [111]), { value: 'value', children: 'children' }
// is default preset.Get nodes sequences if tree path exist.
import { findPathNodes } from 'n-ary-tree'
findPathNodes(tree, [1, 11, 111])
/**
* [
* { value: 1, children: ... },
* { value: 11, children: ... },
* { value: 111, children: ...}
* ]
*/
findPathNodes(tree, [1, 9])
/**
* [
* { value: 1, children: ... }
* ]
*/Find the latest matched path.
import { findPath } from 'n-ary-tree'
findPath(tree, 121)
/**
* [
* { value: 1, children: ... },
* { value: 12, children: ... },
* { value: 121, children: ...}
* ]
*/
findPath(tree, 22) // []Find all matched paths.
import { findAllPaths } from 'n-ary-tree'
const tree = {
value: 1,
children: [
{
value: 111
},
{
value: 11,
children: [
{
value: 111
}
]
},
{
value: 12,
children: [
{
value: 121
}
]
}
]
}
findAllPaths(tree, [111])
/**
* [
* [
* { value: 1, children: ... },
* { value: 111, children: ... },
* ],
* [
* { value: 1, children: ... },
* { value: 11, children: ... },
* { value: 111, children: ...}
* ]
* ]
*/We have support 3 kinds of common tree traversal methods: level-order(BFS), pre-order(DFS), post-order(DFS).
const tree = {
val: 1,
children: [
{
val: 2
}
]
}
levelorder(tree, { value: 'val' })
// [[1], [2]]const tree = {
value: 1,
descendants: [
{
value: 2
}
]
}
preorder(tree, { children: 'descendants' })
// [1, 2]const tree = {
val: 1,
descendants: [
{
val: 2
}
]
}
postorder(tree, { value: 'val', children: 'descendants' })
// [2, 1]