data structure - tree using javascript/typescript
npm i @share-code/ds-tree
const dsTree = new DsTree({
name: 'hello0',
children: [{ name: 'hello0-0' }, { name: 'hello0-1' }, { name: 'hello1' }]
})
// Mutate your tree in here
dsTree.export()
You can find a node which satisfy the condition. This method use DFS algorithm to find node.
DFS algorithm will be stopped if satisfied condition node is founded.
If you use this method with dsTreeNode, it will traverse from current node
Return type: DsTreeNode | null
const dsTree = new DsTree({ name: 'hello0' })
dsTree.search((node) => node.getValue().name === 'hello0') // default algorithm is 'preorder'
dsTree.search((node) => node.getValue().name === 'hello0', {
algorithm: 'preorder'
})
dsTree.search((node) => node.getValue().name === 'hello0', {
algorithm: 'postorder'
})
You can find nodes which satisfy the condition. This method use DFS algorithm to find node.
If you use this method with dsTreeNode, it will traverse from current node
Return type: DsTreeNode[]
const dsTree = new DsTree({ name: 'hello0' })
dsTree.searchAll((node) => node.getValue().name === 'hello0') // default algorithm is 'preorder'
dsTree.searchAll((node) => node.getValue().name === 'hello0', {
algorithm: 'preorder'
})
dsTree.searchAll((node) => node.getValue().name === 'hello0', {
algorithm: 'postorder'
})
You can check the whole nodes in the tree with this method.
This method was maded to get the information. Not for mutation.
If you use this method with dsTreeNode, it will traverse from current node
Return type: void
const dsTree = new DsTree({
name: 'hello0',
children: [{ name: 'hello0-0' }, { name: 'hello0-1' }, { name: 'hello1' }]
})
// default algorithm is 'preorder'
dsTree.walk((node) => {
console.log('depth: ' + node.getDepth())
})
// depth: 0
// depth: 1
// depth: 1
// depth: 1
dsTree.walk(
(node) => {
console.log('depth: ' + node.getDepth())
},
{ algorithm: 'preorder' }
)
// depth: 0
// depth: 1
// depth: 1
// depth: 1
dsTree.walk(
(node) => {
console.log('depth: ' + node.getDepth())
},
{ algorithm: 'postorder' }
)
// depth: 1
// depth: 1
// depth: 1
// depth: 0
You can get root node.
Return type: DsTreeNode
const dsTree = new DsTree({ name: 'hello0' })
dsTree.getRootNode()
You can parse tree form into dsTree form. This is useful when you add new child.
Return type: DsTreeNode
const dsTree = new DsTree({ name: 'hello0' })
dsTree.parse({ name: 'hello1', children: [] })
After finish your mutation with your tree, you can make original tree structure.
Return type: object
const dsTree = new DsTree({ name: 'hello0' })
dsTree.export() // return: { name: 'hello0', children: [] }
Check node is root node.
Return type: boolean
const dsTree = new DsTree({ name: 'hello0' })
const rootNode = dsTree.getRootNode()
rootNode.isRootNode() // true
Get depth of node. Root node is 0.
Return type: number
const dsTree = new DsTree({ name: 'hello0' })
const rootNode = dsTree.getRootNode()
rootNode.getDepth() // 0
get current node path
Return type: DsTreeNode[]
const dsTree = new DsTree({
name: 'hello0',
children: [
{
name: 'hello0-0'
},
{
name: 'hello0-1',
children: [{ name: 'hello0-1-0' }, { name: 'hello0-1-1' }]
},
{
name: 'hello0-2'
}
]
})
const searchedNode = dsTree.search(
(node) => node.getValue().name === 'hello0-1-0'
)
searchedNode.getPath().forEach((node) => {
console.log('node: ' + node.getValue().name)
})
// hello0-1-0
// hello0-1
// hello0
searchedNode.getPath(true).forEach((node) => {
console.log('node: ' + node.getValue().name)
})
// hello0
// hello0-1
// hello0-1-0
Get node value
I recommend not to change children values!
Return type: object
const dsTree = new DsTree({ name: 'hello0' })
const rootNode = dsTree.getRootNode()
rootNode.getValue() // { name: 'hello0' }
Set node value
I recommend not to change children values!
Return type: object
const dsTree = new DsTree({ name: 'hello0' })
const rootNode = dsTree.getRootNode()
// case 01
rootNode.setValue({ name: 'hello7' })
rootNode.getValue() // { name: 'hello7' }
// case 02
rootNode.setValue((prev) => ({ ...prev, name: 'hello77' }))
rootNode.getValue() // { name: 'hello77' }
Get parent node
Return type: DsTreeNode | null
const dsTree = new DsTree({
name: 'hello0',
children: [{ name: 'hello0-0' }, { name: 'hello0-1' }]
})
const rootNode = dsTree.getRootNode()
rootNode.getParentNode() // null
rootNode.getChildren()[0].getParentNode() // it's going to return rootNode
Get node siblings
Return type: DsTreeNode[]
const dsTree = new DsTree({
name: 'hello0',
children: [{ name: 'hello0-0' }, { name: 'hello0-1' }, { name: 'hello0-2' }]
})
const rootNode = dsTree.getRootNode()
rootNode
.getChildren()[0]
.getSiblings()
.forEach((node) => {
console.log('node value: ', node.getValue())
})
// node value: { name: 'hello0-1' }
// node value: { name: 'hello0-2' }
rootNode
.getChildren()[0]
.getSiblings(true)
.forEach((node) => {
console.log('node value: ', node.getValue())
})
// node value: { name: 'hello0-0' }
// node value: { name: 'hello0-1' }
// node value: { name: 'hello0-2' }
Get node index among siblings
Return type: number
const dsTree = new DsTree({
name: 'hello0',
children: [{ name: 'hello0-0' }, { name: 'hello0-1' }, { name: 'hello0-2' }]
})
const rootNode = dsTree.getRootNode()
rootNode.getChildren()[1].getIndex() // 1
rootNode.getChildren()[2].getIndex() // 2
Get node index among siblings
Return type: void
const dsTree = new DsTree({
name: 'hello0',
children: [{ name: 'hello0-0' }, { name: 'hello0-1' }, { name: 'hello0-2' }]
})
const rootNode = dsTree.getRootNode()
rootNode.getChildren()[1].setIndex(0)
console.log(dsTree.export())
/*
{
name: 'hello0',
children: [{
{ name: 'hello0-1', children: [] },
{ name: 'hello0-0', children: [] },
{ name: 'hello0-2', children: [] }
}]
}
*/
Check node is first child or not
Return type: boolean
const dsTree = new DsTree({
name: 'hello0',
children: [{ name: 'hello0-0' }, { name: 'hello0-1' }, { name: 'hello0-2' }]
})
const searchedNode00 = dsTree.search(
(node) => node.getValue().name === 'hello0-0'
)
searchedNode00!.isFirstChild() // true
const searchedNode01 = dsTree.search(
(node) => node.getValue().name === 'hello0-1'
)
searchedNode01!.isFirstChild() // false
Check node is last child or not
Return type: boolean
const dsTree = new DsTree({
name: 'hello0',
children: [{ name: 'hello0-0' }, { name: 'hello0-1' }, { name: 'hello0-2' }]
})
const searchedNode00 = dsTree.search(
(node) => node.getValue().name === 'hello0-2'
)
searchedNode00!.isLastChild() // true
const searchedNode01 = dsTree.search(
(node) => node.getValue().name === 'hello0-1'
)
searchedNode01!.isLastChild() // false
Get node's children nodes
Return type: DsTreeNode[] | undefined | null
const dsTree = new DsTree({
name: 'hello0',
children: [{ name: 'hello0-0' }, { name: 'hello0-1' }, { name: 'hello0-2' }]
})
const rootNode = dsTree.getRootNode()
rootNode.getChildren().forEach((node) => {
console.log('node name: ' + node.getValue().name)
})
// node name: 'hello0-0'
// node name: 'hello0-1'
// node name: 'hello0-2'
add child at the very end of child index
Return type: void
const dsTree = new DsTree({
name: 'hello0',
children: [{ name: 'hello0-0' }, { name: 'hello0-1' }, { name: 'hello0-2' }]
})
const rootNode = dsTree.getRootNode()
rootNode.addChild({ name: 'hello0-3', children: [] })
rootNode.getChildren().forEach((node) => {
console.log('node name: ' + node.getValue().name)
})
// node name: 'hello0-0'
// node name: 'hello0-1'
// node name: 'hello0-2'
// node name: 'hello0-3'
add child at the user specified index
Return type: void
const dsTree = new DsTree({
name: 'hello0',
children: [{ name: 'hello0-0' }, { name: 'hello0-1' }, { name: 'hello0-2' }]
})
const rootNode = dsTree.getRootNode()
rootNode.addChildAtIndex({ name: 'hello0-3', children: [] }, 1)
rootNode.getChildren().forEach((node) => {
console.log('node name: ' + node.getValue().name)
})
// node name: 'hello0-0'
// node name: 'hello0-3'
// node name: 'hello0-1'
// node name: 'hello0-2'
Drop node
Return type: DsTreeNode
const dsTree = new DsTree({
name: 'hello0',
children: [
{
name: 'hello0-0'
},
{
name: 'hello0-1',
children: [{ name: 'hello0-1-0' }, { name: 'hello0-1-1' }]
},
{
name: 'hello0-2'
}
]
})
const rootNode = dsTree.getRootNode()
const secondChild = rootNode.getChildren()![1].drop()
console.log('secondChild parentNode: ', secondChild.getParentNode())
// secondChild parentNode: null
console.log('secondChild name: ', secondChild.getValue().name)
// secondChild name: hello0-1
secondChild.getChildren()!.forEach((node) => {
console.log('node name: ', node.getValue().name)
})
// node name: hello0-1-0
// node name: hello0-1-1
rootNode.getChildren()!.forEach((node) => {
console.log('node name: ', node.getValue().name)
})
// node name: 'hello0-0'
// node name: 'hello0-2'